Merge two sorted arrays without extra space

Problem Overview

LeetCode Problem: Merge Sorted Array

In this problem, you are given two sorted arrays nums1 and nums2, where nums1 has a size of m + n, with the first m elements being the elements to consider and the last n slots filled with zeroes. Your task is to merge nums2 into nums1 to create a single sorted array.

Here’s the problem statement:

• You are given two integers 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.
• The final output should be stored within nums1, considering its allocation to hold m + n elements.

Understanding the Problem

The main challenge is to merge two arrays while maintaining sorted order. It is imperative to fit nums2 into nums1 without using extra space beyond what nums1 provides. This means we should take advantage of the allocated space at the end of nums1.

Example:

Suppose nums1 = [1,2,3,0,0,0] and m = 3. Also, nums2 = [2,5,6] and n = 3. The result should be nums1 = [1,2,2,3,5,6].

Key DSA Concepts and Theory

Arrays and In-Place Operations

Arrays:

• An array is a linear data structure consisting of a collection of elements. Each element is located by index.
• The size of the array needs to be defined at the time of its declaration.

In-Place Algorithm:

• An in-place algorithm transforms the input using a constant amount of space.
• This is crucial for efficient memory usage, especially in constrained environments.

Two Pointer Technique

The two-pointer technique is a common strategy to iterate through two arrays (or a single array) with two indices. In this problem, we will utilize pointers to access and compare elements from the end of nums1 and nums2, which allows us to efficiently merge them in place.

Solution Approach

Step-by-Step Explanation

1. Initialize Pointers:

   • Assign a pointer for the last valid index in nums1 (i.e., m-1).
   • Assign a pointer for the last valid index in nums2 (i.e., n-1).
   • Assign a pointer for the last index of the total array space in nums1 (i.e., m + n - 1).

2. Comparison and Placement:

   • Compare elements pointed by the two pointers in nums1 and nums2.
   • Place the larger element at the position pointed by the third pointer in the extended nums1.
   • Move the respective pointer backward after placement.

3. Fill Remaining Elements:

   • If any elements remain in nums2 after the comparison loop, fill them into nums1.

C++ Code Example

#include <vector>
using namespace std;

void merge(vector<int>& nums1, int m, vector<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 merged array

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

    // If any elements are left in nums2
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

Java Code Example

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 merged array

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

        // If any elements are left in nums2
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

Time and Space Complexity Analysis

• Time Complexity: O(m + n). Each element in both arrays is traversed once.

• Space Complexity: O(1). The operation is done in place without needing additional storage.

Common Mistakes to Avoid

1. Overwriting Elements:

   • Avoid overwriting elements in nums1 before comparing; always start placing from the end.

2. Misplaced Indexes:

   • Ensure indices are rightly calculated, especially considering starting from the end.

3. Ignoring Remaining Elements:

   • Ensure you handle leftover elements in nums2 after the main loop, if any.

Similar Problems on LeetCode

• 88. Merge Sorted Array
• 21. Merge Two Sorted Lists
• 23. Merge k Sorted Lists

Additional Resources and References

• LeetCode Discussion Forum: Engage with the community for alternative solutions and explanations.
• GeeksforGeeks on Merging Arrays: A comprehensive guide on merging techniques.
• Programming Books: "Introduction to Algorithms" by Cormen et al. includes sections on array manipulation that are useful.

This article provides a detailed understanding of the problem, solution strategies, and considerations for solving the merging of sorted arrays efficiently and elegantly in in-place scenarios.