🧩 LeetCode Challenge: Merge Sorted Array | Top Interview Questions [Java Solution]

Introduction 🚀

If you're preparing for coding interviews, especially for roles in FAANG or similar companies, LeetCode's "Merge Sorted Array" problem is a must-solve! This problem tests your understanding of in-place array manipulations and merging algorithms. Let’s dive into the problem, understand it step-by-step, and solve it with Java.

---

Problem Statement 📝

You are given two integer arrays, nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single sorted array in-place. The merged array should overwrite nums1 while maintaining sorted order.

---

💡 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: The arrays to merge are [1,2,3] and [2,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]

---

Thought Process 🧠

To solve this in-place, we can use a two-pointer technique. Instead of starting from the beginning, we begin at the end of both arrays. Why? Because the largest numbers will occupy the last positions in nums1. Here's how it works:

1. Use two pointers, i and j, initialized to m - 1 (end of nums1's actual values) and n - 1 (end of nums2).
2. Compare nums1[i] and nums2[j]. Place the larger of the two at the last position of nums1.
3. Decrement the respective pointer and repeat.
4. If any elements remain in nums2, copy them to nums1.

---

Java Solution 💡

Here's the clean and optimized solution:

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 (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

---

Explanation of the Code 🔍

1. Pointers Initialization:

   • i points to the last valid element in nums1.
   • j points to the last element in nums2.
   • k points to the last position in nums1.

2. Reverse Traversal:

   • Compare nums1[i] and nums2[j]. Place the larger value at nums1[k].
   • Decrement k and the pointer (i or j) of the array from which the element was taken.

3. Remaining Elements in nums2:

   • If nums2 still has elements left (when j >= 0), copy them into nums1.

Note: If nums1 runs out of elements (i < 0), we only need to worry about nums2, as nums1 is already in place.

---

Why This Solution Works 🔧

• Time Complexity: O(m + n)

  We iterate through both arrays once.

• Space Complexity: O(1)

  No extra space is used; the merge is done in-place.

---

Key Takeaways 🎯

1. Understand Two-Pointer Technique: Crucial for merging or comparing arrays in sorted order.
2. Think In-Place: Many interview problems require optimizing space complexity.
3. Practice Edge Cases: Arrays with zero elements, fully overlapping elements, or extreme sizes.

---

Conclusion ✨

Solving problems like Merge Sorted Array is essential for mastering array manipulations and building a strong foundation for coding interviews. If you enjoyed this post or have any questions, feel free to comment below. Happy coding! 🚀

---

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!