merge-sorted-array

Difficulty: Easy  ·  Topic: Two Pointers  ·  Practice it on parikshan: /practice/merge-sorted-array/start

The story

Snowflake's storage layer keeps each table partition as an immutable sorted micro-partition. When the warehouse compactor merges two micro-partitions to reduce file count, it reads two sorted runs and produces a third, also sorted, also immutable. The output buffer is pre-sized to hold both inputs combined and the compactor writes into it directly to avoid a second copy. Reading both inputs front-to-back into the same buffer is dangerous: any value you write at the front may overwrite a value you still need to read. The standard trick is to write from the back.

That is merge-sorted-array. The variant you see in interviews places nums1 at size m + n with the first m entries valid and the last n zero-padded as the merge destination; nums2 provides the second sorted run. The "back-to-front merge" is the canonical answer.

What's actually being asked

You are given two sorted integer arrays nums1 (size m + n, first m are real, last n are placeholder zeros) and nums2 (size n). Merge nums2 into nums1 so the full array is sorted in non-decreasing order. Print the result.

The naive approach

Concatenate and sort: nums1[m:] = nums2; nums1.sort(). O((m + n) log(m + n)) time. Correct, simple, throws away the sortedness of both inputs.

Forward merge with an extra buffer: walk two pointers i and j through the meaningful prefix of nums1 and nums2, write into a fresh result of size m + n, copy back. O(m + n) time, O(m + n) space. Linear time, but wasteful, the placeholder tail of nums1 is right there.

The key insight

The placeholder tail is the entire reason for the problem's specific layout. Slots m, m + 1, ..., m + n - 1 of nums1 are free real estate. If you walk the merge from the back, you write into those free slots first and never collide with values you still need to read.

Three pointers:

• i = m - 1, the last real value of nums1.
• j = n - 1, the last value of nums2.
• k = m + n - 1, the slot to write into.

At each step, the larger of nums1[i] and nums2[j] goes into slot k, then the corresponding source pointer decrements and k decrements.

Why writes never clobber unread reads: after t steps, k = m + n - 1 - t and you have consumed t values from the inputs combined, so i + j + 2 >= (m - 1) + (n - 1) + 2 - t = m + n - t. The values still to be read live at positions <= i in nums1 and <= j in nums2; the next write slot k is strictly greater than i because k = m + n - 1 - t and i + 1 + (used from nums2) = m - t + (used from nums2). Working it out, k > i always, so the write never lands on an unread nums1 value. (nums2 lives in its own array, so there is no collision there.)

The loop ends when j < 0: at that point any remaining values in nums1[0..i] are already in their correct positions, no extra work needed.

Step-by-step approach

1. Set i = m - 1, j = n - 1, k = m + n - 1.
2. While j >= 0:
   • If i >= 0 and nums1[i] > nums2[j]:
     • nums1[k] = nums1[i]; i -= 1.
   • Else:
     • nums1[k] = nums2[j]; j -= 1.
   • k -= 1.
3. Print nums1 as space-separated values.

Worked example

m = 3, n = 3
nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]

Output: 1 2 2 3 5 6.

Complexity

• Time: O(m + n). Each value is written once.
• Space: O(1) extra. The result is built in place.

Compare to concat-then-sort (O((m+n) log(m+n))) and forward-merge-with-buffer (O(m+n) time, O(m+n) space). Backward merge dominates on both axes.

Common pitfalls

• Forward merge in place with i = 0, j = 0, k = 0, collisions are immediate; you destroy the values of nums1[1..m-1] on the first wave of writes.
• Forgetting to handle i < 0. When you have used up the real prefix of nums1 but nums2 still has values, the > comparison must short-circuit. The guard i >= 0 and nums1[i] > nums2[j] covers it.
• Using >= instead of >. Either works for correctness here because equal values get the same write, but > is the convention for keeping the relative ordering of nums2 ahead of nums1 on ties, irrelevant to this problem, important to stable merges generally.
• Not exiting when j < 0. The loop guard is j >= 0. If you also loop on i >= 0 you do redundant writes that copy nums1[i] onto itself, harmless but wasteful.
• Forgetting m == 0 or n == 0. Both are valid inputs; the loop handles them naturally.

Where this shows up in the enterprise

• Snowflake / Databricks compaction: merging two sorted micro-partitions in place during background optimisation.
• PostgreSQL btree page splits: merging two sorted halves during a rebalance.
• Kafka log compaction: merging segments that are already in offset order.
• GitHub's "git merge": three-way merge of sorted-by-line file representations; the merge phase is exactly this pattern.
• Spotify playlist merging: combining two sorted-by-popularity tracklists into one without re-sorting.
• Stripe payout aggregation: merging two sorted-by-timestamp ledger streams into a single ledger.
• AWS Glacier retrieval: merging restored objects, already sorted, back into hot storage in a fixed-size destination.

The pattern is "two sorted runs, fixed destination, no extra buffer". Backward merge is the standard production technique.

Variants you'll see elsewhere

• merge-k-sorted-arrays: same idea with a min-heap to pick the next source.
• merge-k-sorted-lists: linked-list cousin solved with a heap.
• merge-intervals: pre-sorted by start, sweep and merge overlaps.
• kth-smallest-in-two-sorted-arrays: binary-search instead of merge.
• insertion-sort (in place, sorted left, unsorted right) is morally the same back-to-front shift.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

1. The editor runs your code against public tests for instant feedback and against per-session dynamic private tests (generated freshly per session). Synthetic cases hammer m == 0, n == 0, identical arrays, fully-interleaved inputs, and arrays with heavy duplicates at the seam.
2. Hints are graduated. Level 2 specifically nudges you to "walk from the back". Level 4 hands you the full three-pointer recipe at the highest penalty.
3. The AI training assistant in exam mode offers Explain, Review, Find Bugs, Add Comments, Optimise, each costs integrity. In practice mode AI chat is free and free-form.
4. The dispute flow runs after the verdict. The most common dispute is "my forward merge with a temp array is correct", yes, it's correct, but it ignores the placeholder tail that is the whole point.

Read this concept first, attempt the problem in practice mode with the back-to-front approach, then redo it in exam mode without notes. When you can defend "why writes never clobber unread reads" in two sentences, the pattern is yours.

In the AI-integrated workspace

In your future job, the agent writes the code. Your job is to:

1. Recognise that "two sorted runs, destination has a placeholder tail" is the back-to-front merge pattern. The recognition saves you O(n) memory in production.
2. Tell the agent precisely: "three pointers, walk from the back, write the larger value into the tail slot". Not "merge two sorted arrays", that gets you a fresh buffer.
3. Read the generated code and verify three things: the loop condition is on j >= 0 (not on i), the comparison is guarded by i >= 0, and nums1 is mutated in place (not reassigned).
4. Push the edge cases the agent will miss: m == 0 (copy all of nums2), n == 0 (no-op), interleaved with ties, and arrays where one side is entirely smaller than the other.

Candidates who can name "walk from the back" within five seconds are the ones who turn AI into leverage. Candidates who can't end up approving an O(n)-extra-space merge that is correct but blows the memory budget on large-table compaction. parikshan is built to train the first kind.