Arrays: Logic Building & Problem Solving

This section focuses on essential array manipulation problems designed to build algorithmic logic, specifically focusing on in-place partition and two-pointer techniques.

---

1. Move Zeroes to End or Beginning of Array (In-Place)

Problem Description

Given an array of integers nums, reorder its elements in-place such that:

1. Move Zeroes to End: All 0s are shifted to the end of the array while preserving the relative order of non-zero elements.
2. Move Zeroes to Beginning: All 0s are shifted to the beginning of the array while preserving the relative order of non-zero elements.

---

Part 1: Move Zeroes to the End

Intuition & Two-Pointer Approach

We maintain a left pointer pointing to the next available index for a non-zero element.

1. Iterate through the array with index i from 0 to len(nums) - 1.
2. When nums[i] != 0 is encountered, swap nums[i] with nums[left].
3. Increment left by 1.
4. This partitions the array into non-zero elements on the left (0 to left - 1) and zeroes or unvisited elements on the right.

Example Walkthrough

Input: arr = [1, 4, 9, 0, 7, 7, 5, 0, 23, 44]

• i = 0 (nums[0] = 1): Swap nums[0] with nums[0], left = 1 → [1, 4, 9, 0, 7, 7, 5, 0, 23, 44]
• i = 1 (nums[1] = 4): Swap nums[1] with nums[1], left = 2 → [1, 4, 9, 0, 7, 7, 5, 0, 23, 44]
• i = 2 (nums[2] = 9): Swap nums[2] with nums[2], left = 3 → [1, 4, 9, 0, 7, 7, 5, 0, 23, 44]
• i = 3 (nums[3] = 0): Skip swap, left = 3
• i = 4 (nums[4] = 7): Swap nums[4] with nums[3], left = 4 → [1, 4, 9, 7, 0, 7, 5, 0, 23, 44]
• i = 5 (nums[5] = 7): Swap nums[5] with nums[4], left = 5 → [1, 4, 9, 7, 7, 0, 5, 0, 23, 44]
• ... continuing scan ...

Result after moving zeroes to end: [1, 4, 9, 7, 7, 5, 23, 44, 0, 0]

---

Part 2: Move Zeroes to the Beginning

Intuition & Two-Pointer Approach

To shift zeroes to the beginning, iterate from right to left (from index len(nums) - 1 down to 0):

1. Maintain a right pointer initialized to len(nums) - 1 representing the target position for non-zero elements.
2. Iterate i backwards from len(nums) - 1 down to 0.
3. Whenever nums[i] != 0 is found, swap nums[i] with nums[right].
4. Decrement right by 1.
5. Non-zero elements shift to the right end of the array, placing all zeroes at indices 0 to right.

Example Walkthrough

Input (from Part 1 result): arr = [1, 4, 9, 7, 7, 5, 23, 44, 0, 0]

• Scanning backwards from i = 9 down to 0:
• i = 9 (nums[9] = 0): Skip
• i = 8 (nums[8] = 0): Skip
• i = 7 (nums[7] = 44): Swap with nums[9] → right = 8
• i = 6 (nums[6] = 23): Swap with nums[8] → right = 7
• ... continuing backward scan ...

Result after moving zeroes to beginning: [0, 0, 1, 4, 9, 7, 7, 5, 23, 44]

---

Python Solution

class Solution:
    def move_zeroes_to_end(self, nums: list) -> list:
        """Moves all zeroes in the array to the end in-place using two pointers."""
        left = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[i], nums[left] = nums[left], nums[i]
                left += 1

        return nums

    def move_zeroes_to_beginning(self, nums: list) -> list:
        """Moves all zeroes in the array to the beginning in-place using right-to-left scan."""
        right = len(nums) - 1

        for i in range(len(nums) - 1, -1, -1):
            if nums[i] != 0:
                nums[right], nums[i] = nums[i], nums[right]
                right -= 1

        return nums

# Main function demonstrating the in-place operations
def main():
    sol = Solution()
    arr = [1, 4, 9, 0, 7, 7, 5, 0, 23, 44]

    print("Original array:", arr)
    sol.move_zeroes_to_end(arr)
    print("After move_zeroes_to_end:", arr)

    sol.move_zeroes_to_beginning(arr)
    print("After move_zeroes_to_beginning:", arr)

if __name__ == '__main__':
    main()

Complexity Analysis

• Time Complexity: O(N) — Both functions process the array of N elements in a single linear pass.
• Space Complexity: O(1) — In-place element swaps require constant extra space.

---

2. Intersection of Two Sorted Arrays

Problem Description

Given two sorted integer arrays nums1 and nums2, return an array containing their intersection. An element should appear in the intersection as many times as it appears in both input arrays, preserving the relative sorted order.

---

Intuition & Two-Pointer Approach

Since both input arrays are sorted in non-decreasing order, we can find the intersection in a single pass without using extra hash map storage by using a two-pointer technique:

1. Initialize two pointers: i = 0 (for nums1) and j = 0 (for nums2).
2. Compare nums1[i] with nums2[j] in a while loop (while i < len(nums1) and j < len(nums2)):
   • Case 1 (nums1[i] == nums2[j]): The element is common to both arrays. Append nums1[i] to ans, and advance both pointers (i += 1, j += 1).
   • Case 2 (nums1[i] < nums2[j]): nums1[i] is smaller, so it cannot match nums2[j] or any subsequent larger elements in nums2. Advance i += 1.
   • Case 3 (nums1[i] > nums2[j]): nums2[j] is smaller, so advance j += 1.
3. Stop when either pointer reaches the end of its respective array.

---

Example Walkthrough

Input: nums1 = [1, 2, 2, 3, 5], nums2 = [1, 2, 7]

Step	i (nums1[i])	j (nums2[j])	Comparison	Action	ans state
1	0 (1)	0 (1)	1 == 1	Match found! Append 1, i = 1, j = 1	[1]
2	1 (2)	1 (2)	2 == 2	Match found! Append 2, i = 2, j = 1	[1, 2]
3	2 (2)	2 (7)	2 < 7	nums1[i] smaller → i = 3	[1, 2]
4	3 (3)	2 (7)	3 < 7	nums1[i] smaller → i = 4	[1, 2]
5	4 (5)	2 (7)	5 < 7	nums1[i] smaller → i = 5	[1, 2]

End Condition: i = 5 (i = m), loop terminates.
Output: [1, 2]

---

Python Solution

class Solution:
    def intersection_array(self, nums1: list, nums2: list) -> list:
        ans = []
        i, j = 0, 0
        m, n = len(nums1), len(nums2)

        while i < m and j < n:
            if nums1[i] == nums2[j]:
                ans.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1

        return ans

#   main function for the program
def main():
    sol = Solution()
    nums1 = [1, 2, 2, 3, 5]
    nums2 = [1, 2, 7]

    print(sol.intersection_array(nums1, nums2))

#   driver code for the program
if __name__ == '__main__':
    main()

---

Complexity Analysis

• Time Complexity: O(M + N) — Where M is the length of nums1 and N is the length of nums2. In the worst-case scenario, we traverse both arrays once.
• Space Complexity: O(1) — Auxiliary space (excluding the space needed to store the output ans list).