Merge Sorted Array - LeetCode Java Solution

👋 Introduction

Welcome to my LeetCode Solutions in Java series! In each post, I’ll break down one LeetCode problem with a clear explanation, Java code, and a complexity analysis.
Today, let's solve the problem Merge Sorted Array. This problem tests your understanding of arrays, pointers and in-place operations.

---

🔍 Problem Statement

Given: Two integer arrays nums1 and nums2 sorted in non-decreasing order, m as number of elements in nums1 and n as number of elements in nums2

Task: Merge nums1 and nums2 into single array sorted in non-decreasing order.

Return: void, the result should be stored in nums1 which has capacity to accomodate both nums1 and nums2.

🧪 Example:

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

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

→ View on LeetCode

---

💡 Approach

The brute-force way to solve this is by creating a new array, comparing elements of both arrays one by one, and storing them in the new array. Finally, we copy the merged result back into nums1. But this requires extra space and time.

Another inefficient way is to start comparing from the beginning. But every time we insert an element from nums2 into nums1, we’ll have to shift the remaining elements to the right to avoid overwriting them. That’s inefficient too.

So, the optimal solution is to start merging from the end of the arrays, where the free space is. This allows us to perform the merge in-place with no shifting.

We use three pointers:

i = m - 1: last valid element in nums1

j = n - 1: last element in nums2

k = m + n - 1: last position in nums1 (end of the allocated space)

Steps:

1. Initialize i = m - 1, j = n - 1 & k = nums.length - 1

2. Iterate on nums2 while j >= 0

3. If i < 0 || nums2[j] >= nums1[i]

   • set nums1[k] = nums2[j]

   • decrement k

   • decrement j

4. Else

   • set nums1[k] = nums1[i]

   • decrement k

   • decrement i

---

🧠 Java Code

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // initialize variables
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        // covers all the elemets in nums2
        while (j >= 0) {
            if (i < 0 || nums2[j] >= nums1[i]) {
                nums1[k--] = nums2[j--];
            } else {
                nums1[k--] = nums1[i--];
            }
        }
    }
}

---

⏱️ Time Complexity

We process each element in both arrays once, hence time complexity is O(m + n). This solution beats the 100% of the users’ solutions in time.

---

🧮 Space Complexity

The merge is done in-place using the extra space already available in nums1 without any extra space, hence space complexity is O(1)

---

🧩 Related Topics

• Array

• Two Pointer

• Sorting

✅ LeetCode Result

Stay tuned for the next problem in this series!