Backend interview prep

Start

Merge Sorted Array (LeetCode

Learn how to solve the Merge Sorted Array problem using temporary storage and the optimal backward Three Pointer technique. Includes intuition, dry run, Java code, complexity analysis, edge cases, interview tips, and production applications.

Introduction

Merge Sorted Array is a popular array and pointer-based coding interview problem.

It is frequently asked by companies such as:

  • Amazon
  • Google
  • Microsoft
  • Meta
  • Apple
  • Oracle
  • Adobe
  • Goldman Sachs
  • JPMorgan Chase

This problem tests your understanding of:

  • Sorted arrays
  • Two-pointer and three-pointer techniques
  • In-place array modification
  • Backward traversal
  • Time and space optimization
  • Boundary-condition handling

The most important insight is that the destination array has extra space at the end.

Instead of merging from the beginning and overwriting useful values, we merge from the end of the array.

Problem Statement

You are given two integer arrays, nums1 and nums2, sorted in non-decreasing order.

You are also given two integers:

  • m — number of valid elements in nums1
  • n — number of valid elements in nums2

The nums1 array has a total length of m + n.

Its final n positions contain zeroes and should be ignored initially.

Merge nums2 into nums1 so that nums1 becomes one sorted array.

The result must be stored inside nums1.

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:

Valid nums1 values = [1,2,3]

nums2 values = [2,5,6]

Merged result = [1,2,2,3,5,6]

Example 2

Input

nums1 = [1]
m = 1

nums2 = []
n = 0

Output

[1]

Example 3

Input

nums1 = [0]
m = 0

nums2 = [1]
n = 1

Output

[1]

The initial zero in nums1 is only reserved capacity.

It is not a valid input element because m = 0.

Important Observation

The extra space is already available at the end of nums1.

nums1 = [1,2,3,0,0,0]
                    ↑
             Available space

If we start writing from index 0, we may overwrite valid values that have not yet been compared.

Instead, compare the largest remaining elements and write the larger value into the last available position.

Approach 1 — Merge Using a Temporary Array

Idea

Create a temporary array of size m + n.

Use two pointers:

  • One pointer for nums1
  • One pointer for nums2

Compare the current values and copy the smaller value into the temporary array.

Finally, copy the temporary array back into nums1.

Temporary Array Flow

graph TD
    nums1_1_2_3["nums1 = (1,2,3)"] --> nums2_2_5_6["nums2 = (2,5,6)"]
    nums2_2_5_6["nums2 = (2,5,6)"] --> Compare_both_arrays["Compare both arrays"]
    Compare_both_arrays["Compare both arrays"] --> Temporary_Array["Temporary Array"]
    Temporary_Array["Temporary Array"] --> N_1_2_2_3_5_6["(1,2,2,3,5,6)"]
    N_1_2_2_3_5_6["(1,2,2,3,5,6)"] --> Copy_into_nums1["Copy into nums1"]

Java Code — Temporary Array

public class MergeSortedArraysUsingExtraSpace {

    public void merge(
            int[] nums1,
            int m,
            int[] nums2,
            int n) {

        int[] merged = new int[m + n];

        int first = 0;
        int second = 0;
        int write = 0;

        while (first < m && second < n) {

            if (nums1[first] <= nums2[second]) {

                merged[write] = nums1[first];
                first++;

            } else {

                merged[write] = nums2[second];
                second++;

            }

            write++;

        }

        while (first < m) {

            merged[write] = nums1[first];

            first++;
            write++;

        }

        while (second < n) {

            merged[write] = nums2[second];

            second++;
            write++;

        }

        System.arraycopy(
                merged,
                0,
                nums1,
                0,
                merged.length);

    }

}

Complexity of Temporary Array Approach

Complexity Value
Time O(m + n)
Space O(m + n)

The time complexity is optimal, but the solution uses additional memory.

The problem expects an in-place solution.

Approach 2 — Optimal Backward Three Pointer Technique

Core Idea

Use three pointers:

  • first points to the last valid element in nums1
  • second points to the last element in nums2
  • write points to the last position in nums1

Initial positions:

nums1 = [1,2,3,0,0,0]
             ↑     ↑
           first  write

nums2 = [2,5,6]
             ↑
           second

Compare nums1[first] and nums2[second].

Place the larger value at nums1[write].

Then move the corresponding pointer backward.

Why Merge from the End?

Suppose we merge from the beginning:

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

When inserting values near the beginning, we may overwrite 2 or 3 before processing them.

Merging from the end avoids this problem because the final positions are unused.

graph TD
    Largest_values["Largest values"] --> Placed_at_the_end["Placed at the end"]
    Placed_at_the_end["Placed at the end"] --> No_valid_value_overwritten["No valid value overwritten"]

Pointer Initialization

int first = m - 1;
int second = n - 1;
int write = m + n - 1;

For the input:

nums1 = [1,2,3,0,0,0]
m = 3

nums2 = [2,5,6]
n = 3

Pointers begin at:

first = 2
second = 2
write = 5

Dry Run

Input

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

m = 3
n = 3

Initial State

nums1 = [1,2,3,0,0,0]
              ↑     ↑
            first  write

nums2 = [2,5,6]
              ↑
            second

Values:

nums1[first] = 3
nums2[second] = 6

Since 6 > 3, place 6 at write.

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

Move:

second--
write--

Step 2

nums1[first] = 3
nums2[second] = 5

Since 5 > 3, place 5.

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

Step 3

nums1[first] = 3
nums2[second] = 2

Since 3 > 2, place 3.

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

Move first backward.

Step 4

nums1[first] = 2
nums2[second] = 2

Either value may be placed first.

Place the value from nums2.

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

Step 5

nums2 is now fully processed.

The remaining values already present in nums1 are correctly positioned.

Final result:

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

Java Code — Optimal Solution

public class MergeSortedArrays {

    public void merge(
            int[] nums1,
            int m,
            int[] nums2,
            int n) {

        int first = m - 1;
        int second = n - 1;
        int write = m + n - 1;

        while (first >= 0 && second >= 0) {

            if (nums1[first] > nums2[second]) {

                nums1[write] = nums1[first];
                first--;

            } else {

                nums1[write] = nums2[second];
                second--;

            }

            write--;

        }

        while (second >= 0) {

            nums1[write] = nums2[second];

            second--;
            write--;

        }

    }

}

Why Is There No Loop for Remaining nums1 Values?

Suppose nums2 becomes empty first.

The unprocessed values in nums1 are already in their correct positions.

Example:

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

After placing 6, 5, and 4:

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

The existing values 1, 2, and 3 do not need to move.

However, when values remain in nums2, they must be copied into nums1.

Example:

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

The remaining nums2 values belong at the beginning.

Complexity Analysis

Complexity Value
Time O(m + n)
Space O(1)

Each valid element is processed at most once.

No additional array is created.

Why the Algorithm Works

At every step:

  1. nums1[first] is the largest unprocessed element in nums1.
  2. nums2[second] is the largest unprocessed element in nums2.
  3. The larger of these two values must be the largest remaining element overall.
  4. Therefore, it belongs at nums1[write].

This greedy choice is always correct because both arrays are sorted.

Visual Explanation

graph TD
    nums1["nums1"] --> N_1_2_3_0_0_0["(1,2,3,0,0,0)"]
    N_1_2_3_0_0_0["(1,2,3,0,0,0)"] --> nums2["nums2"]
    nums2["nums2"] --> N_2_5_6["(2,5,6)"]
    N_2_5_6["(2,5,6)"] --> Compare_from_the_end["Compare from the end"]
    Compare_from_the_end["Compare from the end"] --> N_3_vs_6["3 vs 6"]
    N_3_vs_6["3 vs 6"] --> Place_6["Place 6"]
    Place_6["Place 6"] --> N_1_2_3_0_0_6["(1,2,3,0,0,6)"]
    N_1_2_3_0_0_6["(1,2,3,0,0,6)"] --> N_3_vs_5["3 vs 5"]
    N_3_vs_5["3 vs 5"] --> Place_5["Place 5"]
    Place_5["Place 5"] --> N_1_2_3_0_5_6["(1,2,3,0,5,6)"]
    N_1_2_3_0_5_6["(1,2,3,0,5,6)"] --> N_3_vs_2["3 vs 2"]
    N_3_vs_2["3 vs 2"] --> Place_3["Place 3"]
    Place_3["Place 3"] --> N_1_2_3_3_5_6["(1,2,3,3,5,6)"]
    N_1_2_3_3_5_6["(1,2,3,3,5,6)"] --> N_2_vs_2["2 vs 2"]
    N_2_vs_2["2 vs 2"] --> Place_2["Place 2"]
    Place_2["Place 2"] --> N_1_2_2_3_5_6["(1,2,2,3,5,6)"]

Alternative Clean Java Implementation

public class Solution {

    public void merge(
            int[] nums1,
            int m,
            int[] nums2,
            int n) {

        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        while (j >= 0) {

            if (i >= 0 && nums1[i] > nums2[j]) {

                nums1[k--] = nums1[i--];

            } else {

                nums1[k--] = nums2[j--];

            }

        }

    }

}

This version uses a single loop because processing continues only until every value from nums2 has been copied.

Edge Cases

nums2 Is Empty

nums1 = [1,2,3]
m = 3

nums2 = []
n = 0

Output:

[1,2,3]

No changes are required.

nums1 Has No Valid Elements

nums1 = [0,0,0]
m = 0

nums2 = [1,2,3]
n = 3

Output:

[1,2,3]

Every value from nums2 is copied.

All nums2 Values Are Smaller

nums1 = [4,5,6,0,0,0]
m = 3

nums2 = [1,2,3]
n = 3

Output:

[1,2,3,4,5,6]

The remaining nums2 values must be copied to the beginning.

All nums2 Values Are Larger

nums1 = [1,2,3,0,0,0]
m = 3

nums2 = [4,5,6]
n = 3

Output:

[1,2,3,4,5,6]

The original nums1 values remain in place.

Duplicate Values

nums1 = [1,2,2,0,0,0]
m = 3

nums2 = [2,2,3]
n = 3

Output:

[1,2,2,2,2,3]

The algorithm correctly preserves duplicate values.

Negative Numbers

nums1 = [-5,-2,0,0,0]
m = 2

nums2 = [-4,-1,3]
n = 3

Output:

[-5,-4,-2,-1,3]

The algorithm works for any sorted integer values.

Common Interview Mistakes

Mistake 1 — Merging from the Beginning

Writing from index 0 can overwrite valid values in nums1.

Mistake 2 — Treating Trailing Zeroes as Valid Data

Only the first m values in nums1 are valid.

The final n positions are reserved capacity.

Mistake 3 — Forgetting Remaining nums2 Values

If nums1 becomes empty first, the remaining elements from nums2 must be copied.

Mistake 4 — Creating Another Array

A temporary array works, but it does not satisfy the optimal constant-space requirement.

Mistake 5 — Using Incorrect Pointer Positions

Correct initialization:

int first = m - 1;
int second = n - 1;
int write = m + n - 1;

Mistake 6 — Sorting After Copying

A solution such as:

System.arraycopy(nums2, 0, nums1, m, n);
Arrays.sort(nums1);

works functionally, but its time complexity is:

O((m + n) log(m + n))

It ignores the fact that both input sections are already sorted.

Comparison of Approaches

Approach Time Space Recommended
Copy and sort O((m+n) log(m+n)) O(1) or sorting-dependent No
Temporary merged array O(m+n) O(m+n) Acceptable explanation
Backward three pointers O(m+n) O(1) Best

Production Applications

The same merge technique is used in real-world systems such as:

  • Merging sorted transaction records
  • Combining timestamped event streams
  • Consolidating financial data
  • Search-result aggregation
  • Log-file merging
  • External merge sort
  • Database merge operations
  • Time-series data processing
  • Batch reconciliation
  • Distributed data pipelines

Real-World Example — Transaction Reconciliation

Suppose two systems provide sorted transaction timestamps.

System A

[09:00, 09:15, 10:30]

System B

[09:05, 09:45, 11:00]

The merge process produces:

[09:00, 09:05, 09:15, 09:45, 10:30, 11:00]

Because both inputs are already sorted, the result can be generated in linear time.

Follow-Up Questions

What if nums1 Does Not Have Extra Space?

Create a result array of size m + n.

Time:

O(m + n)

Space:

O(m + n)

What if We Need to Merge Multiple Sorted Arrays?

Possible approaches include:

  • Merge arrays one at a time
  • Use divide and conquer
  • Use a min heap

For k sorted arrays, a min-heap solution commonly requires:

O(N log k)

where N is the total number of elements.

What if the Arrays Are Very Large and Stored on Disk?

Use an external merge process.

Read smaller chunks sequentially instead of loading all data into memory.

This technique is used in external merge sort and large-scale data processing.

Can We Merge from the Beginning?

Yes, but only if we use an additional array or shift values repeatedly.

Shifting values may produce:

O(m × n)

behavior in the worst case.

Backward merging is cleaner and more efficient.

Is the Algorithm Stable?

Yes.

Equal values remain correctly grouped.

If the objects contain additional metadata and stability matters between sources, define which source should win when values compare equally.

Interview Explanation

A strong interview explanation could be:

Since both arrays are sorted and nums1 contains extra capacity at the end, I compare the largest unprocessed elements from both arrays. I place the larger value at the last available position in nums1 and move backward. This avoids overwriting valid values and gives O(m+n) time with O(1) extra space.

Interview Tips

Interviewers commonly ask:

  • Why merge from the end?
  • Why are three pointers required?
  • Why is the solution O(m + n)?
  • Why is no extra array needed?
  • Why do we only copy remaining values from nums2?
  • What happens when m = 0?
  • What happens when n = 0?
  • Can the problem be solved using sorting?
  • How would you merge multiple sorted arrays?
  • How would the solution change if there were no extra capacity?

Explain the overwrite problem before writing the optimal code.

Unit Tests

import static org.junit.jupiter.api.Assertions.assertArrayEquals;

import org.junit.jupiter.api.Test;

class MergeSortedArraysTest {

    private final MergeSortedArrays solution =
            new MergeSortedArrays();

    @Test
    void shouldMergeTypicalArrays() {

        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int[] nums2 = {2, 5, 6};

        solution.merge(nums1, 3, nums2, 3);

        assertArrayEquals(
                new int[]{1, 2, 2, 3, 5, 6},
                nums1);

    }

    @Test
    void shouldHandleEmptySecondArray() {

        int[] nums1 = {1};
        int[] nums2 = {};

        solution.merge(nums1, 1, nums2, 0);

        assertArrayEquals(
                new int[]{1},
                nums1);

    }

    @Test
    void shouldHandleEmptyFirstArray() {

        int[] nums1 = {0};
        int[] nums2 = {1};

        solution.merge(nums1, 0, nums2, 1);

        assertArrayEquals(
                new int[]{1},
                nums1);

    }

    @Test
    void shouldHandleSmallerSecondArrayValues() {

        int[] nums1 = {4, 5, 6, 0, 0, 0};
        int[] nums2 = {1, 2, 3};

        solution.merge(nums1, 3, nums2, 3);

        assertArrayEquals(
                new int[]{1, 2, 3, 4, 5, 6},
                nums1);

    }

}

Summary

The Merge Sorted Array problem demonstrates how sorted input and unused capacity can be used to create an optimal in-place solution.

The temporary-array approach achieves linear time but uses additional memory.

The optimal approach uses three pointers and merges backward, achieving:

Time: O(m + n)

Space: O(1)

This pattern is important for coding interviews and real-world data-processing systems that merge ordered datasets efficiently.

Key Takeaways

  • Recognize that both input arrays are sorted.
  • Ignore the reserved zero positions in nums1.
  • Merge from the end to prevent overwriting.
  • Track the last valid element in both arrays.
  • Track the final write position.
  • Place the larger value first.
  • Copy remaining nums2 values when necessary.
  • Achieve O(m + n) time complexity.
  • Use O(1) additional space.
  • Explain the overwrite risk clearly during interviews.
  • Handle empty arrays and duplicate values.
  • Connect the technique to real-world sorted-data merging.