In-Place Array Manipulation Techniques

1. The Essence of In-Place Algorithms

An "in-place" algorithm transforms the input data using a small, constant amount of extra memory. For arrays, this means you are expected to modify the given array itself rather than creating a new one to store the result. This is a common requirement to test for space efficiency.

Let's dive into our first problem, which is a perfect illustration of this principle.

2. Problem 1: Removing Duplicates from a Sorted Array

The Task: Given a sorted integer array nums, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements must be kept the same. You should return the number of unique elements.

The key constraints here are:

• The array is sorted. This is a major hint!
• The modification must be in-place.
• The relative order of unique elements must be preserved.

Since the array is sorted, all duplicate elements will be grouped together. This structure allows us to solve the problem efficiently. The core idea is to use two pointers: one to iterate through the array (a "read" pointer) and another to keep track of the position for the next unique element (a "write" pointer).

This video provides an excellent walkthrough of this two-pointer strategy.

Dissecting the Two-Pointer Logic

As the video demonstrated, the algorithm is surprisingly concise. Let's break it down:

• A write pointer (let's call it j or write_index) starts at index 1 (or 0, depending on implementation style). This pointer marks the boundary of the processed, unique part of the array. The elements from nums[0] to nums[j-1] are the unique elements found so far.
• A read pointer (let's call it i) iterates through the array from the second element.
• At each step, we compare the element at the read pointer, nums[i], with the last-known unique element, nums[j-1].
• If nums[i] is different, it means we've found a new unique element. We then place it at the write pointer's position (nums[j] = nums[i]) and advance the write pointer (j += 1).
• If nums[i] is the same, we do nothing but advance the read pointer, effectively skipping the duplicate.

The final value of the write pointer, j, is the length of the subarray containing unique elements.

This approach is highly efficient:

• Time Complexity: O(n), because we iterate through the array once with our read pointer.
• Space Complexity: O(1), as we only use a few variables (pointers) and modify the array in-place.

To solidify your understanding and learn about common errors, the following reading is very helpful.

3. Problem 2: Rotating an Array

Let's tackle another common in-place manipulation problem that requires a different kind of thinking.

The Task: Given an array, rotate the array to the right by k steps, where k is non-negative.

For example, if nums = [1, 2, 3, 4, 5, 6, 7] and k = 3, the result should be [5, 6, 7, 1, 2, 3, 4].

A simple solution would be to create a new array and place each element in its new, rotated position using modular arithmetic: new_nums[(i + k) % n] = nums[i]. This works, but it requires O(n) extra space for the new array. The real challenge is to do it in O(1) space.

There's a surprisingly elegant and clever algorithm to achieve this using reversals.

The Three-Reversal Algorithm

The logic, once you see it, is a fantastic trick to remember. To rotate an array to the right by k steps:

1. Reverse the entire array.
   • [1, 2, 3, 4, 5, 6, 7] becomes [7, 6, 5, 4, 3, 2, 1]
2. Reverse the first k elements. (For k=3)
   • [7, 6, 5] becomes [5, 6, 7]. The array is now [5, 6, 7, 4, 3, 2, 1]
3. Reverse the remaining n-k elements.
   • [4, 3, 2, 1] becomes [1, 2, 3, 4]. The array is now [5, 6, 7, 1, 2, 3, 4]

And just like that, the array is rotated correctly in O(1) space! Each reversal can be done in-place by swapping elements from the ends inwards.

• Time Complexity: O(n), because we pass through the elements three times (one for each reversal), which is still linear.
• Space Complexity: O(1).

For a deeper dive and to see another interesting in-place method, check out the following resource.

Conclusion

In this lesson, we focused on the crucial skill of in-place array manipulation. You've seen how to modify an array directly to save space, a common requirement in performance-critical applications and technical interviews.

Key Takeaways:

• In-place algorithms operate directly on the input data, aiming for O(1) auxiliary space complexity.
• For removing duplicates from a sorted array, a two-pointer technique (with one read and one write pointer) is a highly efficient O(n) time, O(1) space solution.
• For rotating an array, the three-reversal method is a clever and efficient O(n) time, O(1) space algorithm that is a great pattern to have in your toolbox.
• Always consider edge cases, such as an empty array or rotation values (k) larger than the array's length.

Preview of the Next Lesson

We got a preview of the two-pointer technique today. In the next lesson, we will formalize this concept. You'll learn how to apply the two-pointer technique as a general pattern to solve a wider variety of problems on sorted arrays and strings, such as finding pairs that sum to a target, or squaring a sorted array.