Day 30 Of Dsa Problem Solving

🧩 Q1: Merge Sorted Array – Two Approaches Explained

In this post, we’ll dive into solving the classic “Merge Sorted Array” problem from Leetcode. We'll explore two efficient approaches for merging two sorted arrays in-place inside the first one.

❓ Problem Statement

You are given two integer arrays:

• nums1 with a length of m + n, where the first m elements are valid and the rest are zeros.
• nums2 with n elements.

Your task is to merge nums2 into nums1 as one sorted array in-place.

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

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

✅ Approach 1: Two-Pointer Merge Using Extra Space

This method is intuitive and mimics the merge step of merge sort.

🔧 Step-by-Step Strategy

1. Copy the first m elements of nums1 into a temporary array called nums1Copy.

📌 Why? We will be overwriting nums1, so we need to preserve the original values.

1. Use two pointers:

   • p1 for nums1Copy
   • p2 for nums2

2. Loop from index 0 to m + n - 1:

   • Compare nums1Copy[p1] and nums2[p2]
   • Assign the smaller one to nums1[i]
   • Move the corresponding pointer

⚠️ Edge Case Handling

• If one array is exhausted, continue with the other.

💡 Why This Works

• We're merging two sorted arrays by comparing their front elements.
• We avoid overwriting data by using a copy of nums1.
• Simple and easy to understand.

📈 Time & Space Complexity

Complexity	Value	Explanation
Time	O(m + n)	Each element is considered once
Space	O(m)	Temporary array stores original nums1

👨‍💻 Code (Approach 1)

var merge = function(nums1, m, nums2, n) {
    let nums1Copy = nums1.slice(0, m); // Step 1
    let p1 = 0, p2 = 0;

    for (let i = 0; i < m + n; i++) {
        if (p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2])) {
            nums1[i] = nums1Copy[p1++];
        } else {
            nums1[i] = nums2[p2++];
        }
    }
};

🔍 Example Trace

nums1Copy: [1, 2, 3]
nums2:     [2, 5, 6]

Step 1: Compare 1 and 2 → take 1 → nums1 = [1, _, _, _, _, _]
Step 2: Compare 2 and 2 → take 2 (from nums1Copy) → nums1 = [1, 2, _, _, _, _]
Step 3: Compare 3 and 2 → take 2 (from nums2) → nums1 = [1, 2, 2, _, _, _]
Step 4: Compare 3 and 5 → take 3 → nums1 = [1, 2, 2, 3, _, _]
Step 5: nums1Copy done → take 5 → nums1 = [1, 2, 2, 3, 5, _]
Step 6: → take 6 → nums1 = [1, 2, 2, 3, 5, 6]

---

✅ Approach 2: Reverse Two-Pointer (In-Place, No Extra Space)

This approach is more space-efficient and clever. We take advantage of the extra space at the end of nums1 by filling it from the backward.

🔧 Step-by-Step Strategy

1. Initialize three pointers:

   • p1 = m - 1: last valid element in nums1
   • p2 = n - 1: last element in nums2
   • i = m + n - 1: last position in nums1

2. Loop backward through nums1:

   • If p2 < 0, we're done.
   • If nums1[p1] > nums2[p2], assign nums1[i] = nums1[p1--]
   • Else, assign nums1[i] = nums2[p2--]

✅ No need for additional memory!

💡 Why This Works

• We're guaranteed that nums1 has enough space at the end.
• Merging from the back avoids overwriting valid values.
• No extra space is used — fully in-place!

📈 Time & Space Complexity

Complexity	Value	Explanation
Time	O(m + n)	Every element is placed once
Space	O(1)	In-place, no additional memory used

👨‍💻 Code (Approach 2)

var merge = function(nums1, m, nums2, n) {
    let p1 = m - 1;
    let p2 = n - 1;

    for (let i = m + n - 1; i >= 0; i--) {
        if (p2 < 0) break;

        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[i] = nums1[p1--];
        } else {
            nums1[i] = nums2[p2--];
        }
    }
};

🔍 Example Trace

nums1: [1, 2, 3, 0, 0, 0]
nums2: [2, 5, 6]

Start filling from index 5:

Step 1: Compare 3 and 6 → take 6 → nums1 = [1, 2, 3, 0, 0, 6]
Step 2: Compare 3 and 5 → take 5 → nums1 = [1, 2, 3, 0, 5, 6]
Step 3: Compare 3 and 2 → take 3 → nums1 = [1, 2, 3, 3, 5, 6]
Step 4: Compare 2 and 2 → take 2 (nums2) → nums1 = [1, 2, 2, 3, 5, 6]
Step 5: Take 2 → nums1 = [1, 2, 2, 3, 5, 6]

gggggggggg

🧩 Q2: Move Zeroes – Intuition and Efficient Solution Explained

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. You must do this in-place without making a copy of the array.

Input:

nums = [0,1,0,3,12]

Output:

nums = [1,3,12,0,0]

✅ Approach 1: Using One Pointer (In-Place Overwrite)

We can solve this efficiently by using a single pointer to track the position of non-zero elements.

---

🔧 Step-by-Step Strategy

• Initialize a variable Pointer to 0.
  
  📌 This pointer tracks the position where the next non-zero element should go.

• Loop through the array from start to end:

  • If the current element is not zero (nums[i] !== 0):
  • Place it at nums[Pointer]
  • Increment Pointer

• After the loop:

  • All non-zero elements are shifted to the front.
  • Fill the remaining positions (from Pointer to nums.length - 1) with zeroes.

---

💡 Why This Works

• You overwrite the original array in-place without using extra space.
• The order of non-zero elements is preserved.
• All zeroes are moved to the end efficiently.

---

📈 Time & Space Complexity

Complexity	Value	Explanation
Time	O(n)	One pass for shifting, one for filling zeroes
Space	O(1)	No extra space used

👨‍💻 Code (Approach 1)

var moveZeroes = function(nums) {
    if (nums.length < 2) return nums;

    let Pointer = 0;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {
            nums[Pointer] = nums[i];
            Pointer++;
        }
    }

    // Fill the rest with zeroes
    for (let j = Pointer; j < nums.length; j++) {
        nums[j] = 0;
    }

    return nums;
};

🔍 Example Trace

Input

nums = [0, 1, 0, 3, 12]

---

🧮 Step-by-step Execution

• Initial Pointer = 0

1. i = 0 → 0 → skip
2. i = 1 → 1 → place at index 0 → nums = [1, 1, 0, 3, 12] → Pointer = 1
3. i = 2 → 0 → skip
4. i = 3 → 3 → place at index 1 → nums = [1, 3, 0, 3, 12] → Pointer = 2
5. i = 4 → 12 → place at index 2 → nums = [1, 3, 12, 3, 12] → Pointer = 3

---

🧹 Fill remaining with zeroes from Pointer = 3:

• nums[3] = 0
• nums[4] = 0

---

✅ Final Output:

[1, 3, 12, 0, 0]