Merge Sorted Array easy

Problem Statement

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

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]

Example 2:

Input: nums1 = [1], m = 1 nums2 = [], n = 0

Output: [1]

Steps:

1. Initialization: We'll use three pointers: p1 pointing to the last element of nums1 (index m-1), p2 pointing to the last element of nums2 (index n-1), and p pointing to the last position of the merged array (index m+n-1).

2. Comparison and Placement: Compare the elements at nums1[p1] and nums2[p2]. The larger element is placed at nums1[p]. Decrement the pointer of the larger element and p.

3. Handling Remaining Elements: Once one of the pointers p1 or p2 reaches the beginning of its array, copy the remaining elements from the other array to nums1.

Explanation:

The algorithm works by iteratively comparing the last elements of the two sorted arrays. The larger element is placed at the end of the merged array (nums1). This process continues until one of the arrays is exhausted. The remaining elements from the other array are then copied directly into nums1. This approach ensures that the resulting array nums1 is sorted in descending order from the end. After the merging process, the sorted array will be in nums1 from index 0 to m+n-1.

Code:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1; // Pointer for nums1
        int p2 = n - 1; // Pointer for nums2
        int p = m + n - 1; // Pointer for merged array

        // Compare and merge elements from the end
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }

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

Complexity:

• Time Complexity: O(m + n). We iterate through nums1 and nums2 at most once.
• Space Complexity: O(1). We are using only a constant number of extra variables (pointers). No additional arrays are created.