Merge Sorted Array Solution for Accenture

Company: Accenture · Difficulty: Easy · Topics: Array, Two Pointers, Sorting

Problem Statement

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order. Merge nums1 and nums2 into a single array sorted in non-decreasing order.

Key Understanding:

Both input arrays are already sorted in non-decreasing order
nums1 has enough space to hold all elements (length = m + n)
We need to merge the arrays in-place into nums1
The first m elements of nums1 contain valid data, the rest are zeros
We need to maintain the sorted order in the final result

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:

nums1 has 3 valid elements: [1,2,3] and 3 zeros: [0,0,0]
nums2 has 3 elements: [2,5,6]
After merging: [1,2,2,3,5,6] (sorted order)
Visual representation: [1,2,3,_,_,_] + [2,5,6] → [1,2,2,3,5,6]

Example 2:

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

Output: [1]

Explanation:

nums1 has 1 valid element: [1]
nums2 is empty: []
After merging: [1] (no change needed)

Example 3:

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

Output: [1]

Explanation:

nums1 has 0 valid elements: [] (only zeros)
nums2 has 1 element: [1]
After merging: [1] (copy from nums2)

Example 4:

Input: nums1 = [2,0], m = 1, nums2 = [1], n = 1

Output: [1,2]

Explanation:

nums1 has 1 valid element: [2] and 1 zero: [0]
nums2 has 1 element: [1]
After merging: [1,2] (sorted order)

Intuition

The key insight is that since nums1 has enough space to hold all elements and both arrays are sorted, we can merge them efficiently by comparing elements from the end and placing larger elements at the end of nums1.

Core Concept:

Since both arrays are sorted, we can use a merge-like approach
We need to avoid overwriting elements in nums1 that we still need
By working from the end, we can place elements in their final positions without losing data
The largest elements should go at the end of the merged array

Why Working from End Works:

The end of nums1 contains zeros (unused space)
We can safely overwrite these zeros
By placing larger elements first, we ensure proper ordering
We avoid the problem of overwriting elements we still need to use

Approach

Approach 1: Three Pointers from End (Optimal)

Algorithm:

1. Initialize three pointers:

p1: points to the last valid element in nums1 (m-1)
p2: points to the last element in nums2 (n-1)
p: points to the last position in the merged array (m+n-1)

2. While p1 >= 0 and p2 >= 0:

Compare nums1[p1] and nums2[p2]
Place the larger element at position p
Decrement the corresponding pointer and p

3. If p2 >= 0, copy remaining elements from nums2

4. If p1 >= 0, remaining elements are already in place

Why This Works:

We work from the end to avoid overwriting elements we need
Since both arrays are sorted, we can compare elements directly
The larger element should go at the end of the merged array
We maintain the sorted order by placing elements in reverse order

Complexity Analysis:

Time: O(m + n) - Single pass through both arrays
Space: O(1) - Only constant variables needed

Approach 2: Using Extra Array

Algorithm:

1. Create a temporary array of size m + n

2. Merge both arrays into the temporary array using two pointers

3. Copy the result back to nums1

Why This Works:

We avoid the problem of overwriting elements in nums1
Simple and straightforward merge process
Guaranteed to work correctly

Complexity Analysis:

Time: O(m + n) - We traverse both arrays once
Space: O(m + n) - We need extra array

Approach 3: Simple Copy and Sort

Algorithm:

1. Copy all elements from nums2 to the end of nums1

2. Sort the entire nums1 array

Why This Works:

Simple approach that doesn't require careful pointer management
Works for any input arrays (not just sorted ones)

Complexity Analysis:

Time: O((m + n) log(m + n)) - Due to sorting
Space: O(1) if in-place sorting, O(m + n) if not

Dry Run

Let's trace through Example 1: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Three Pointers Approach:

Initial State: p1 = 2, p2 = 2, p = 5, nums1 = [1,2,3,0,0,0]

Step 1: p1 = 2, p2 = 2, p = 5

Compare: nums1[2] = 3 vs nums2[2] = 6
3 < 6, so place 6 at position 5
nums1 = [1,2,3,0,0,6]
Update: p1 = 2, p2 = 1, p = 4

Step 2: p1 = 2, p2 = 1, p = 4

Compare: nums1[2] = 3 vs nums2[1] = 5
3 < 5, so place 5 at position 4
nums1 = [1,2,3,0,5,6]
Update: p1 = 2, p2 = 0, p = 3

Step 3: p1 = 2, p2 = 0, p = 3

Compare: nums1[2] = 3 vs nums2[0] = 2
3 > 2, so place 3 at position 3
nums1 = [1,2,3,3,5,6]
Update: p1 = 1, p2 = 0, p = 2

Step 4: p1 = 1, p2 = 0, p = 2

Compare: nums1[1] = 2 vs nums2[0] = 2
2 = 2, so place 2 at position 2 (from nums2)
nums1 = [1,2,2,3,5,6]
Update: p1 = 1, p2 = -1, p = 1

Step 5: p2 = -1 (nums2 exhausted)

Stop the main loop
Remaining elements in nums1 are already in place

Final Result: [1,2,2,3,5,6]

Extra Array Approach:

Step 1: Create temp array of size 6

Step 2: Merge [1,2,3] and [2,5,6] into temp

temp = [1,2,2,3,5,6]

Step 3: Copy temp back to nums1

nums1 = [1,2,2,3,5,6]

Key Insights

1. In-Place Merging: Working from the end avoids overwriting needed elements

2. Sorted Arrays: Since both arrays are sorted, we can compare elements directly

3. Pointer Management: Careful pointer management is crucial for in-place merging

4. Space Efficiency: In-place approach uses O(1) extra space

5. Edge Cases: Handle cases where one array is empty or all elements are in one array

Edge Cases

1. Empty nums2: nums1 already contains the result

2. Empty nums1: Copy all elements from nums2

3. All elements in nums1: No additional work needed

4. All elements in nums2: Copy all elements from nums2

5. Equal elements: Can place from either array (stable sorting considerations)

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Three Pointers from End (Optimal)

Time Complexity: O(m + n) - We traverse both arrays once

Space Complexity: O(1) - We use only constant extra space

Advantages:

Most space-efficient solution
In-place merging
Single pass through arrays
Handles all edge cases

Disadvantages:

Requires careful pointer management
May be less intuitive than extra array approach

Solution 2: Using Extra Array

Time Complexity: O(m + n) - We traverse both arrays once

Space Complexity: O(m + n) - We need extra array

Advantages:

Simple and straightforward
Easy to understand and implement
No risk of overwriting elements

Disadvantages:

Uses extra space
Requires two passes (merge + copy)

Solution 3: Simple Copy and Sort

Time Complexity: O((m + n) log(m + n)) - Due to sorting

Space Complexity: O(1) - If in-place sorting

Advantages:

Very simple implementation
Works for any input arrays

Disadvantages:

Less efficient than merge approaches
Doesn't take advantage of sorted input
Higher time complexity