88. Merge Sorted Array - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You are given two sorted integer arrays nums1 and nums2, along with two integers m and n that represent the number of valid elements in nums1 and nums2 respectively. The array nums1 has a length of m + n, where the first m entries are the sorted elements to consider, and the last n entries are set to 0 (acting as placeholders). The task is to merge the elements of nums2 into nums1 so that nums1 becomes one sorted array in non-decreasing order. The merged result should be stored in-place in nums1 (do not return a new array).

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]
Explanation: We merge the arrays [1,2,3] and [2,5,6]. The result is [1,2,2,3,5,6]. (The underlined elements in the output would come from nums1 in this case.)
Example 2:
Input: nums1 = [1], m = 1; nums2 = [], n = 0
Output: [1]
Explanation: Merging [1] and [] yields [1] . Since nums2 is empty, nums1 remains unchanged.
Example 3:
Input: nums1 = [0], m = 0; nums2 = [1], n = 1
Output: [1]
Explanation: We are merging [] (no valid elements in nums1) and [1]. The result is [1]. The 0 in nums1 was just a placeholder to ensure it has size m+n.

Constraints:

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200 (there is at least one element between the two arrays)
-10^9 <= nums1[i], nums2[j] <= 10^9

The problem guarantees that both nums1 and nums2 are initially sorted in non-decreasing order. An efficient solution is expected to run in linear time, i.e. O(m + n).

Hints

Use Sorted Order: Take advantage of the fact that both arrays are already sorted. This property is a big hint that you can merge without needing to re-sort the entire array from scratch. Consider how you might merge two sorted lists efficiently (similar to the merge step in merge sort).
Extra Space in nums1: Remember that nums1 has additional space at the end to accommodate all of nums2's elements. This means you can use that space to avoid creating a completely new array. How might you fill that space strategically?
Think from the End: Ask yourself where the largest element should go in the merged array. Since the final array should be sorted, the largest element will end up at the end of nums1. Can you place elements starting from the back of the array to avoid unnecessary shifts? (Hint: Two-pointer technique.)
Edge Situations: Consider what happens when one of the arrays is exhausted (runs out of elements) before the other. How will you handle any remaining elements from the other array? Ensuring you handle this will cover edge cases.

Solution Approaches

There are multiple ways to solve this problem, ranging from a simple brute-force method to a more optimal in-place technique. We’ll discuss a couple of approaches:

1. Brute Force Approach – Merge and Sort

Idea: The most straightforward solution is to simply combine the two arrays and then sort the result. Since nums1 has extra capacity at the end, we can copy all elements of nums2 into nums1 (starting at index m where the first array’s valid elements end), and then sort nums1. This will yield the merged sorted array in nums1. This approach is easy to implement but not the most efficient in terms of time complexity due to the sorting step.

Steps:

Copy Elements: Append all elements of nums2 into the back of nums1 (starting from index m). After this step, nums1 will contain the combined elements of both arrays, but not necessarily in sorted order. For example, if nums1 = [1,2,3,0,0,0] and nums2 = [2,5,6], after copying you get nums1 = [1,2,3,2,5,6] (just placing 2,5,6 after the original [1,2,3]).
Sort the Array: Use a sorting method to sort the entire nums1 array in non-decreasing order. In our example, sorting [1,2,3,2,5,6] yields [1,2,2,3,5,6], which is the desired result.

Analysis: This method works correctly and is simple. However, its time complexity is dominated by the sorting step. Sorting the combined array of size m+n takes O((m+n) * log(m+n)) time in the worst case. The space complexity is O(1) extra if we sort in place (though sorting algorithms typically use some auxiliary space internally). If you were to explicitly use a separate array for merging or sorting, that would take O(m+n) additional space. Under the problem’s size constraints (maximum 200 elements total), this brute-force approach runs efficiently, but for larger inputs it’s not optimal.

Alternative Brute Force: Another brute force variant is to create a new array of size m+n, copy all elements from nums1 (first m elements) and nums2 into it, sort this new array, then copy the sorted elements back into nums1. This achieves the same end result and has the same complexity, but uses additional space for the new array (O(m+n) space). In an interview, the interviewer might point out that this is not in-place and ask for a more space-efficient approach.

2. Optimal Two-Pointer Approach – In-Place Merge from the End

Idea: We can utilize the fact that the arrays are sorted to merge them in linear time O(m+n) without extra space. The key is to avoid overwriting useful data in nums1. To do this, we can fill nums1 from the back forward, placing the largest elements first. This way, we use the unused space at the end of nums1 as we merge, and we won't have to move elements around once placed.

Think of it like having two pointers, one at the end of the valid portion of nums1 (at index m-1) and one at the end of nums2 (index n-1). We also have a mergePos pointer at index m+n-1 (end of the total length of nums1). We compare the elements pointed by these two pointers and whichever is larger, we copy that element into the position at mergePos in nums1. Then we move the pointer (and mergePos) backwards by one. We repeat this step, always placing the next largest element into the next free slot from the end of nums1. This way, we preserve the sorted order without needing an intermediate array.

Steps:

Initialize Pointers:
Let i = m - 1 (pointing to the last valid element in nums1), j = n - 1 (pointing to the last element in nums2), and k = m + n - 1 (pointing to the last position in nums1, which is initially a placeholder slot). This setup prepares us to fill nums1 from the back.
Merge in Reverse:
While both i and j are within their array bounds (i.e., i >= 0 and j >= 0), do the following:
1. Look at nums1[i] and nums2[j] – these are the current largest candidates in each array (since the arrays are sorted in non-decreasing order, the largest elements are at the end).
2. Compare these two values. Whichever is larger is truly the next largest element overall. Place that value into nums1[k] (the current last free position in nums1).
3. If the value came from nums1[i], decrement i; if it came from nums2[j], decrement j. In either case, decrement k (we've filled that slot and move left to the next slot).
This loop ensures that at each step, the highest remaining element among both arrays is placed at the end of the merged array, working backwards.
Copy Remaining Elements:
If one of the arrays is exhausted, we might still have elements left in the other. Notably, if nums2 still has elements left (meaning j hasn’t gone below 0), then all those remaining elements are smaller or equal to all elements already placed (because we always took the larger of the two arrays’ elements first). In this case, we simply copy all remaining elements from nums2 into the front part of nums1. (If nums1 has remaining elements, we actually don’t need to do anything – they’re already in place in the correct order at the front of nums1.) Copying the leftover nums2 elements is straightforward since they are already sorted.

Using the two-pointer method, we effectively merge the arrays in one pass. We never have to shift large portions of the array or do any full-array sorts after the initial setup. We directly place each element into its correct position.

Analysis: The two-pointer approach runs in O(m + n) time because we do at most m+n comparisons/moves – each element from either array is processed exactly once. There is no significant additional memory usage; we are only using a few integer variables for indices (so auxiliary space is O(1)). This meets the optimal requirements of the problem (linear time and constant extra space). This approach intelligently uses the provided extra space in nums1 and leverages the sorted order of the input arrays. It’s the approach an interviewer would typically be looking for in terms of efficiency and in-place operation.

3. Other Approaches and Discussion

Two-Pointer with Extra Array: If the in-place requirement weren’t there, a slight modification of the two-pointer approach could be to merge into a new array. You could initialize a result array of size m+n and use two pointers (starting from the beginning of nums1 and nums2) to fill it in sorted order, then copy back to nums1. This would also take O(m+n) time but uses O(m+n) extra space for the new array. It’s essentially how the merge step of merge sort works with two sorted subarrays. This isn’t needed for this problem due to the in-place requirement (and extra space in nums1), but it’s good to know as a concept.
Front-Merge by Shifting: One could attempt to merge starting from the front of nums1, inserting elements from nums2 into the correct position in nums1 one by one. However, doing this in-place would be quite inefficient, because each insertion in the front or middle of an array can require shifting many elements to the right to make space. In the worst case (e.g., inserting an element that belongs at the very start of nums1), you’d shift m elements. Doing this for all n elements leads to a time complexity of O(m * n), which can be much worse than the other approaches for large arrays. This is generally not a recommended approach, but it’s worth mentioning as a naive method and understanding why it’s suboptimal.

Code Implementations

Below are implementations of the optimal two-pointer approach in both Python and Java. (The brute force approach is simpler to code, but due to its inefficiency we focus on the optimal solution here. The brute force could be implemented by copying and sorting as described above.)

Python Solution

Python3

. . . .

Java Solution

Java

. . . .

Both implementations use the same logic: we iterate from the back of the arrays, placing the larger of the two current elements into nums1's back, and move the pointers accordingly. After the loop, if nums2 still has elements left (meaning all of its elements are smaller than all those we already placed from nums1), we copy the rest of nums2 into the front of nums1. If nums1 has leftover elements, they are already in place.

Complexity Analysis

Let’s analyze the time and space complexity of the approaches discussed:

Brute Force (Copy and Sort):
- Time Complexity: O((m+n) log(m+n)). Combining the arrays is O(m+n), but the dominant operation is sorting the combined array, which takes O((m+n) * log(m+n)) in the worst case. For example, if there are 100 elements total, sorting would take on the order of 100 * log(100) ≈ 100 * 6.64 ≈ 664 operations (constant factors aside).
- Space Complexity: O(1) extra if you do the merge in place (using the existing nums1 array’s buffer) and use an in-place sorting algorithm. However, most sorting implementations (like Python’s Timsort or Java’s Dual-Pivot Quicksort) use O(k) auxiliary space in the worst case for recursion or merging, where k = m+n. If you explicitly use a new array to merge or sort, that would be O(m+n) additional space. In any case, the input itself occupies O(m+n) space.
Optimal Two-Pointer (In-Place from End):
- Time Complexity: O(m + n). We perform at most m+n comparisons and moves – each element from both arrays is handled exactly once in the merging loop or the final copying of leftovers. There are no heavy operations like sorting; it’s purely linear scan and comparisons. This is asymptotically optimal because any algorithm must at least look at all elements to merge them.
- Space Complexity: O(1) extra. Aside from a few integer indices, we do not allocate additional data structures proportional to the input size. We’re modifying nums1 in-place. The total space used by the input and output is still O(m+n) (since nums1 holds the result and has length m+n), but the algorithm itself doesn't need extra arrays. This meets the in-place requirement.
Two-Pointer with Extra Array (Alternate Merge):
- Time Complexity: O(m + n). Merging two sorted arrays by traversing them with two pointers (like the merge step in merge sort) touches each element once, so it's linear.
- Space Complexity: O(m + n) extra. This approach would use a new array of size m+n to store the merged result before copying back. This is fine for functional correctness but uses additional memory. In the given problem, since nums1 has space, using extra array isn’t necessary.
Naive Insertion (Front-Merge by Shifting):
- Time Complexity: O(m * n) in the worst case. Each insertion from nums2 into nums1 could take O(m) time for shifting elements, and doing that n times leads to quadratic time in the worst scenario. For instance, if nums1 elements are all larger than those of nums2, each new element from nums2 would be inserted at the start of nums1, causing all existing elements in nums1 to shift right. This is highly inefficient for large arrays.
- Space Complexity: O(1) extra (it’s in-place), but the time cost makes it impractical except for very small inputs.

In summary, the optimal two-pointer solution is O(m+n) time and O(1) extra space, which is the best possible for this problem. The brute force works in a pinch or under small constraints but would become slow for large inputs due to the sorting step.

Step-by-Step Visual Walkthrough

To solidify how the merging works, let's walk through a detailed example visually. Consider the first example:

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

Initially, nums1 has the elements [1,2,3] and then three 0 placeholders, and nums2 has [2,5,6]. The goal is to merge them into a sorted array [1,2,2,3,5,6].

Initial configuration of the arrays and the expected merged result. Purple boxes represent initial elements of nums1, orange boxes are elements of nums2, and the dashed outline shows the final merged array.

Let's visualize the process for both approaches:

Brute Force Merge & Sort Process:
If we follow the brute force approach (copy and sort), the process would look like this:

Copy nums2 into nums1’s tail: Start placing elements of nums2 into the trailing empty slots of nums1. After each insertion, the array looks like:
- After inserting 2: nums1 = [1, 2, 3, 2, 0, 0]
- After inserting 5: nums1 = [1, 2, 3, 2, 5, 0]
- After inserting 6: nums1 = [1, 2, 3, 2, 5, 6]
  (Now nums1 contains all elements but is unsorted.)
Sort nums1: Sorting [1,2,3,2,5,6] will rearrange it into [1,2,2,3,5,6].

Illustration of the brute force approach. We first copy all elements from nums2 into nums1 (left side shows nums1 after each insertion). Then we sort the combined array to get the final answer (shown in green).

Two-Pointer In-Place Merge Process:
Now, let's do the same example using the optimal two-pointer strategy:

Initial Pointers: i = m-1 = 2 (pointing to the 3 in nums1), j = n-1 = 2 (pointing to the 6 in nums2), and k = m+n-1 = 5 (pointing to the last index of nums1). At the start, we have:
nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]
i -> 3 (nums1[2]), j -> 6 (nums2[2]), k -> end of nums1.
Iteration 1: Compare nums1[i] = 3 and nums2[j] = 6. The larger is 6.
Place 6 at nums1[k] (end of nums1).
Now nums1 becomes [1, 2, 3, 0, 0, 6].
Decrement j to 1 (next comparison will use 5 from nums2), and decrement k to 4 (next fill position). i stays at 2.
Iteration 2: Compare nums1[i] = 3 and nums2[j] = 5. Larger is 5.
Place 5 at nums1[k] (position 4).
Now nums1 becomes [1, 2, 3, 0, 5, 6].
Decrement j to 0 (now pointing at 2 in nums2), and decrement k to 3. i is still 2.
Iteration 3: Compare nums1[i] = 3 and nums2[j] = 2. Larger is 3.
Place 3 at nums1[k] (position 3).
Now nums1 becomes [1, 2, 3, 3, 5, 6].
Decrement i to 1 (now pointing at 2 in nums1), and decrement k to 2. j remains 0.
Iteration 4: Compare nums1[i] = 2 and nums2[j] = 2. They are equal, so it doesn’t matter which one we choose – to keep things simple, we’ll take the element from nums2 in this case.
Place that 2 at nums1[k] (position 2).
Now nums1 becomes [1, 2, 2, 3, 5, 6].
Decrement j to -1 (now nums2 is exhausted), and decrement k to 1. i remains 1.
End of Loop: We stop the main loop because j < 0 (no more elements in nums2 to compare). At this point, nums1 is [1, 2, 2, 3, 5, 6]. The remaining elements in nums1 (if any) are already in place. If nums2 had any elements left (i.e., if j was still ≥ 0), we would copy them into nums1[0...j]. In this example, nums2 is fully merged. The array nums1 is now completely sorted and merged.

Each iteration placed the correct largest remaining element into its final position in nums1. Notice that we never had to move an element twice – each element from nums2 went directly into its sorted position, and the original nums1 elements either stayed where they were or were moved once to an open spot at the end. This in-place process is efficient and uses the array’s empty space as we go.

Common Mistakes

When solving this problem, watch out for these common pitfalls:

Forgetting to Handle Leftover Elements: A frequent mistake is to merge until one array is exhausted and then forget to handle the remaining elements of the other array. For example, if you exit the main loop when i or j becomes negative, you must ensure the remaining elements (especially if j is still ≥ 0, meaning nums2 had smaller elements that haven’t been placed yet) are copied over. Not doing so will leave the result incorrect (missing some elements). Always check for leftovers in nums2 after the main loop and copy them.
Overwriting Data in nums1: If you try to merge from the front of the array, you might overwrite elements of nums1 that you still need to compare. This typically happens if one tries a naive approach of inserting nums2's elements into nums1 and shifting. It’s tricky to do in-place without losing data. The two-pointer from the end approach avoids this by writing into the empty slots from the back. Make sure if you ever write into nums1, you're writing to a position that won’t be needed later for comparisons (hence writing from the end where slots were empty).
Misinterpreting the Problem Setup: Remember that nums1 has length m+n but only the first m elements are valid data. The rest are just placeholders and should be ignored during the merge comparison process. A mistake here is to consider those 0s as actual zeros that need to be sorted in. They are not part of the input sets; you should not treat them as initial values (except in the case m=0, where there is no valid nums1 data). Always use m and n to delimit the valid portions of the arrays.
Off-by-One Errors with Indices: Managing three indices (for nums1, nums2, and the merge position) can be error-prone. It’s easy to get an index wrong (for example, using m instead of m-1 for the last index of nums1 data, or miscalculating the final index position). Carefully initialize i = m-1, j = n-1, and k = m+n-1. Also, ensure your loop conditions and index decrements are correct (e.g., when copying remaining elements from nums2, use while j >= 0, not > 0). Off-by-one mistakes can lead to out-of-bounds errors or missed placements.
Using Too Much Extra Space Unnecessarily: Some might jump straight to creating a new array or using high-level functions that do the job in one line (like Python’s sorted or Java’s Arrays.sort) which is fine for getting a correct answer, but in an interview, it may be considered a mistake if you don’t at least acknowledge the in-place requirement. Make sure to clarify the expected constraints – since this problem explicitly hints at an O(1) space solution, not attempting it could be seen as a missed opportunity. It’s okay to start with a simple solution, but you should improve it if asked for optimal.

Edge Cases

Be sure to consider and handle these edge cases in your solution:

Empty Second Array (n = 0): If nums2 is empty, then nums1 should remain as is (since there’s nothing to merge). Your code should ideally handle this naturally (the merge loop will simply never run if n=0, or you check and skip merging). Ensure that you don’t mistakenly try to copy placeholders or go out of bounds. (Example: nums1 = [1,2,3], nums2 = [] should output [1,2,3] with no changes.)
Empty First Array (m = 0): If m = 0, it means nums1 has no initial valid elements, and we are essentially just copying nums2 into nums1. After the operation, nums1 should exactly match nums2. This should be handled by the "copy remaining elements" part of your algorithm. (Example: nums1 = [0,0,0] (placeholders only), nums2 = [2,5,7] should result in nums1 = [2,5,7].)
All Elements Go to One Side: Consider scenarios where all elements of one array are either all smaller or all larger than the elements of the other. For instance:
- If all elements of nums2 are greater than all elements of nums1 (e.g., nums1=[1,2,3], nums2=[10,11,12]), then after merging, nums1 should end with the contents of nums2. The two-pointer method will handle this by exhausting nums1 first and then copying all of nums2.
- Conversely, if all elements of nums2 are smaller than those in nums1 (e.g., nums1=[5,6,7,0,0,0] with m=3, nums2=[1,2,3]), the result should be [1,2,3,5,6,7]. The two-pointer method will handle this by placing smaller elements (from nums2) at the end first, and then eventually copying the remaining ones to the front. Make sure the logic correctly places all those smaller nums2 elements into the front of nums1 at the end.
Arrays with Duplicate Values: If there are duplicate numbers across nums1 and nums2, the algorithm should handle it gracefully (they will simply be adjacent in the final sorted order). For example, merging nums1=[1,2,4,0,0,0] and nums2=[2,2,3] should yield [1,2,2,2,3,4]. The condition in code if nums1[i] > nums2[j] often takes care of this – if values are equal, it falls to the else case, typically taking from nums2 (or it could take from nums1; either is fine as long as one is decremented). The end result will have the correct number of each duplicate.
Negative Numbers: The presence of negative values doesn’t change the approach at all, but it’s an edge case to test. If both arrays contain negative numbers (still sorted), the logic remains the same (the smallest values might be negative, but the comparison and placement works no differently). Just ensure your code doesn’t assume non-negativity anywhere. For example, merging nums1=[-7,-4,0,0,0] (m=2) and nums2=[-3,-1,-1] (n=3) should properly yield [-7,-4,-3,-1,-1] after merging.

In summary, make sure your solution doesn’t break when one array is empty, when values are all at one extreme, or in the presence of duplicates and negative numbers. Proper use of the indices and loop conditions usually handles these cases.

Alternative Variations

This problem is a specific instance of merging sorted sequences. There are several variations and related scenarios where a similar merging strategy is useful or where requirements might differ:

Merging Sorted Linked Lists: Instead of arrays, you might be asked to merge two sorted linked lists into one sorted list (a classic problem on its own). The concept is analogous – you use two pointers to traverse each list and stitch them together in sorted order. The difference is that instead of array indices and direct assignment, you deal with node pointers and changing references. LeetCode Merge Two Sorted Lists (Problem 21) is exactly this variation. The approach uses the same two-pointer idea (often with a dummy head to simplify list manipulation).
Merge k Sorted Arrays/Lists: You might encounter a problem where more than two sorted sequences need to be merged (for example, merging k sorted linked lists, which is LeetCode Problem 23). The two-pointer method merges two at a time; with multiple lists, you can extend the idea by repeatedly merging lists or using a min-heap to efficiently pick the smallest among the heads of all lists. The fundamental merge operation between any two lists is still the same process described here. For merging many arrays, an optimal approach might use a heap/priority queue or divide-and-conquer merging pairs of lists.
In-Place Merge Without Extra Buffer: Imagine a scenario similar to this problem but where nums1 doesn’t have the extra space at the end (or say you have two separate arrays and you want to do it strictly in place without a third array). If the total size is fixed and you can’t have an output array, one would have to make room by shifting elements (which, as discussed, is inefficient). Typically, true in-place merging without a buffer is tricky and not done because it can degrade time complexity. Most variations will allow either extra space in one of the inputs (like this problem) or using an output array.
Different Order (Descending sort): If the arrays were sorted in decreasing order and you needed to merge into decreasing order, you could apply a similar two-pointer approach but you’d pick the larger element to put in front (or equivalently pick the smaller element to put at the back). Essentially, you’d just reverse the comparison – if you want descending result, you place the larger element first (or equivalently, place the smaller element at the end). The logic is symmetric.
Merging Streams of Data: In practical applications, you might be merging sorted data from two sources (files, streams, etc.). The concept remains to compare the fronts and output in order. If the data is too large to all fit in memory, you would output the merged result incrementally (this is how merge sort works in external sorting on disk, or how merging sorted log files might be implemented). The problem at hand is essentially the in-memory version with the twist of writing into one of the input arrays.
Related String Problems: Interestingly, merging logic can apply to strings as well. For example, a problem like Merge Strings Alternately (LeetCode) asks you to merge two strings by alternating characters (not sorted order, but a merging procedure nonetheless). Another harder one, Largest Merge Of Two Strings, asks for a lexicographically largest result by repeatedly choosing from the front of two strings – this is conceptually a merge where you always pick the "larger" front (somewhat analogous to picking the larger of two numbers in our array merge). While these are string problems and not about sorted numeric order, they share the idea of merging two sequences with a rule. The approach in those varies (greedy comparisons in the case of lexicographical merges), but the two-pointer idea (one pointer per sequence) is present there too.

In all these variations, the core idea is comparing two sequences and merging based on some criterion (smallest first for sorting, or some custom rule for other problems). The two-pointer technique is a common thread.

Merging sorted arrays and using two-pointer techniques is a fundamental concept. To further strengthen your understanding, you can practice the following related LeetCode problems:

Merge Two Sorted Lists (LeetCode 21): Merge two sorted linked lists into one sorted linked list. This is the linked-list counterpart to this problem and uses a very similar two-pointer strategy (iterating through two lists).
Merge k Sorted Lists (LeetCode 23): Merge k sorted linked lists into one sorted list. This generalizes the two-list merge. It can be solved by successive merging or using a min-heap for efficiency. It practices both merging logic and other data structures (if using a heap).
Squares of a Sorted Array (LeetCode 977): Given a sorted array of integers (which can be negative), return an array of the squares of each number also sorted. This can be solved using two pointers from each end of the input array (since the largest squares might come from the large negative or large positive). It’s a different scenario but reinforces two-pointer technique in sorted contexts.
Interval List Intersections (LeetCode 986): Given two sorted lists of intervals, find their intersections. This is another two-pointer problem where you advance pointers in two lists based on interval comparisons. It’s not about merging into one list, but it requires scanning through two sorted sequences simultaneously, which is a similar logic structure.
Median of Two Sorted Arrays (LeetCode 4): This is a harder problem, where you need to find the median of two sorted arrays. A brute-force way to do it is actually to merge the two arrays (like we do here) until you reach the median position. However, that would be O(m+n); the problem expects a more optimal solution (O(log(m+n))) using binary search. Still, understanding how to merge helps understand the brute force approach for it.