Merge Sorted Array - LeetCode Solution in C++, Java, Python

1. Introduction

In this blog post, we will provide a LeetCode solution for the "Merge Sorted Array" problem in C++, Java, and Python languages.

The "Merge Sorted Array" problem involves merging two sorted arrays into a single sorted array. The first array has enough space to accommodate all elements from both arrays. This problem tests the understanding of array manipulation and sorting algorithms.

2. Problem Statement

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 array sorted in non-decreasing order.

3. Solution in C++

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    // Merge from the end to efficiently use the space in nums1
    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--];
    }
}

Explanation:

1. Start from the end of both arrays nums1 and nums2.

2. Compare elements from both arrays and place the larger one at the correct position in nums1.

3. Continue this process until all elements of nums2 are merged into nums1.

4. If there are remaining elements in nums2, copy them over to nums1.

4. Solution in Java

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, 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:

1. Iterate backward from the end of nums1 and nums2.

2. Compare elements from both arrays, placing the larger element in the next position of nums1.

3. Continue this process, overwriting nums1 from the end.

4. If elements remain in nums2, copy them into nums1.

5. Solution in Python

def merge(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i, k = i - 1, k - 1
        else:
            nums1[k] = nums2[j]
            j, k = j - 1, k - 1
    while j >= 0:
        nums1[k] = nums2[j]
        j, k = j - 1, k - 1

Explanation:

1. Start merging from the last elements of nums1 and nums2.

2. Place the larger of the two elements at the end of nums1.

3. Continue the process, moving backward through both arrays.

4. If any elements are left in nums2, they are copied into the remaining positions of nums1.