← Back to Index

📚 Merge Sorted Array – Java Cheat Sheet

📌 What Is It?

The problem involves merging two sorted arrays into one sorted array in-place. The first array has enough space to hold the elements of both arrays.

This is a classic two-pointer problem where we start merging from the end of the arrays to avoid overwriting elements in the first array.

🧱 Pattern Template

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1; // Pointer for nums1
        int j = n - 1; // Pointer for nums2
        int k = m + n - 1; // Pointer for the merged array

        // Merge nums1 and nums2 from the end
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

        // Copy remaining elements from nums2, if any
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

📊 Time Complexity

• Time Complexity: O(m + n) – We iterate through both arrays once.
• Space Complexity: O(1) – The merge is done in-place.

✅ Use Cases

• Merging two sorted arrays in-place
• Efficiently combining sorted data streams
• Applications in external sorting and database systems

📘 Common LeetCode Problems

• 88. Merge Sorted Array [Easy] Two Pointers

🧪 Example: Merge Sorted Array

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

Explanation:
- Start merging from the end of nums1 and nums2.
- Compare elements and place the larger one at the end of nums1.
- Continue until all elements are merged.

💡 Pro Tips

• Start merging from the end to avoid overwriting elements in nums1.
• Handle edge cases: empty nums2, nums1 with extra space but no elements.
• Use two pointers to efficiently merge the arrays.