Merge two sorted logs
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
Two servers each write a log of event times, in seconds, sorted from earliest to latest.
Return one list with every time from both logs, sorted from earliest to latest. Keep duplicates: two events at the same second are two events.
- 0 ≤ a.length, b.length ≤ 200,000
- a and b are each sorted, non-decreasing
Examples
mergeLogs([1, 4, 9], [2, 3, 10, 11])returns[1, 2, 3, 4, 9, 10, 11]mergeLogs([5, 5], [5])returns[5, 5, 5]mergeLogs([], [7])returns[7]
Hints
Hint 1 of 2
Keep a position in each log. The next time in the merged log is the smaller of the two times at those positions.
Hint 2 of 2
When one log runs out, everything left in the other log comes next, in its order.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
Both logs are already sorted, so the earliest time not yet taken is always at the front of one of them. Compare the two fronts, take the smaller, and move that log's pointer on. Each time is looked at once.
The loop stops as soon as one log is empty, and the rest of the other log still has to be copied. Forgetting that tail is the classic merge bug.
Joining the lists and sorting them also works if you sort numerically, at O(n log n). Plain .sort() compares as text, so 10 sorts before 2.
function mergeLogs(a, b) {
const out = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);
while (i < a.length) out.push(a[i++]);
while (j < b.length) out.push(b[j++]);
return out;
}Complexity. O(n + m) time; the output is the only extra space.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.