Skip to main content

5. Merge Sorted Array

easyAsked at Freshworks

Merge two sorted ticket buffers in place, mirroring how Freshdesk consolidates queues from primary and replica shards.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given two sorted arrays nums1 and nums2 of length m and n. nums1 has length m + n with the last n slots reserved. Merge nums2 into nums1 as one sorted array, in place.

Constraints

  • 0 <= m, n <= 200
  • nums1.length == m + n
  • Both arrays sorted non-decreasing

Examples

Example 1

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

Example 2

Input
nums1 = [1], m = 1, nums2 = [], n = 0
Output
[1]

Approaches

1. Brute force

Copy nums2 into the tail of nums1 then sort the whole thing.

Time
O((m+n) log (m+n))
Space
O(1)
for (let i = 0; i < n; i++) nums1[m + i] = nums2[i];
nums1.sort((a,b) => a-b);

Tradeoff:

2. Three pointers from the back

Walk both arrays from their largest values and write the bigger one into nums1's tail. No overwrite hazard because tail is empty.

Time
O(m+n)
Space
O(1)
function merge(nums1, m, nums2, n) {
  let i = m - 1, j = n - 1, k = m + n - 1;
  while (j >= 0) {
    if (i >= 0 && nums1[i] > nums2[j]) {
      nums1[k--] = nums1[i--];
    } else {
      nums1[k--] = nums2[j--];
    }
  }
}

Tradeoff:

Freshworks-specific tips

Freshworks values the in-place merge because their multi-tenant ticket pipeline can't afford O(n) scratch buffers per shard — narrate the back-pointer trick before you code.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Merge Sorted Array and other Freshworks interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →