26. Remove Duplicates from Sorted Array - Detailed Explanation

Java Implementation (Brute Force):

Explanation: In both implementations, we iterate through the array and maintain a list of encountered unique elements. We rely on the sorted order: whenever we see a number that’s the same as the last unique number, we skip it. Otherwise, we record it as a new unique. After one pass, we have all unique values. We then rewrite these into the original array. The new length (k) is just the count of unique elements found.

Complexity Analysis (Brute Force): This approach makes one pass through the array to collect unique elements and another pass to overwrite the original array. This is O(n) in time complexity for an array of length n. However, it uses additional space proportional to n in the worst case (if all elements are unique, the uniqueList or unique_nums will hold all n elements), so the space complexity is O(n). This extra space usage breaks the optimal space requirement, but it’s acceptable for understanding the problem. An alternative brute-force method might use a set and sorting, which would be O(n log n) time due to sorting, but we avoided sorting by leveraging the input’s sorted property.

Java Implementation (Two-Pointer):

Explanation: We begin by assuming the first element is unique (which it is, by definition). We set slow = 0 at index 0. Then we iterate fast through the array starting from index 1. Whenever nums[fast] differs from nums[slow], we have encountered a new unique value. We increment slow and copy nums[fast] to nums[slow]. This expands the unique segment of the array. If nums[fast] is the same as nums[slow], we skip it because it’s a duplicate of the current unique value at slow. By the end, slow has moved to the last index of the unique segment. We return slow + 1 as the count of unique elements.

For example, consider nums = [0, 0, 1, 1, 2, 2, 3]:

• Start: slow = 0 (at value 0). Unique segment = [0].
• fast = 1: nums[1] is 0, which equals nums[slow] (0), so skip (duplicate of 0).
• fast = 2: nums[2] is 1, which is different from nums[slow] (still 0). Found a new unique value 1. Increment slow to 1 and set nums[1] = 1. Now the first two positions are [0, 1] (unique segment).
• fast = 3: nums[3] is 1, which equals nums[slow] (1), skip (duplicate of 1).
• fast = 4: nums[4] is 2, different from nums[slow] (1). New unique found (2). Increment slow to 2 and set nums[2] = 2. Unique segment is now [0, 1, 2].
• fast = 5: nums[5] is 2, which equals nums[slow] (2), skip.
• fast = 6: nums[6] is 3, different from nums[slow] (2). New unique (3). Increment slow to 3 and set nums[3] = 3. Unique segment = [0, 1, 2, 3].
• End of array. slow = 3, so return slow + 1 = 4. The first 4 elements of nums are [0,1,2,3], which are the unique values.

During this process, duplicates (like the extra 0, 1, 2 values) get overwritten by subsequent uniques, or simply skipped over. The array positions after the first k might still hold old values, but those are beyond the returned length and are ignored.

Complexity Analysis (Two-Pointer): We make a single pass through the array with fast, and slow only moves forward when a new unique is found. Each element is visited at most once by fast (and possibly written once by slow), so the time complexity is O(n) for n elements. The space complexity is O(1) extra space since all operations are done in-place and only a few integer variables are used. This meets the problem’s requirements and is optimal. In terms of efficiency, this approach is much better than a brute force removal which could be O(n²) if done naively by deleting elements one by one , and it uses constant space as opposed to the extra O(n) space used in the brute force solution.

Step-by-Step Example Walkthrough

Let’s walk through a concrete example to see how the two-pointer approach works step by step:

Example: nums = [0, 0, 1, 1, 2, 2, 3] (same as above, for clarity)

• Initial state:
  nums = [0, 0, 1, 1, 2, 2, 3]
slow = 0 (index 0, value = 0) – the first element is always unique.
  fast = 1 (we'll start checking from the second element).

• Step 1: (fast = 1)
  Compare nums[fast] (nums[1] = 0) with nums[slow] (nums[0] = 0). They are equal, which means the element at fast is a duplicate of the one at slow.
  Action: Do nothing (skip this element). The pointers remain slow = 0, fast will increment to 2.
  Array state: still [0, 0, 1, 1, 2, 2, 3] (no change).

• Step 2: (fast = 2)
  Compare nums[2] = 1 with nums[slow] = nums[0] = 0. They are different, which means we found a new unique element (value 1).
  Action: Increment slow to 1 (move to next write position) and set nums[1] = 1 (write the new unique value at index 1).
  Array state: now [0, 1, 1, 1, 2, 2, 3]. (We overwrote the second slot with 1. Note: the array may temporarily have a duplicate 1 at index 1 and 2, but that’s okay.)
  Pointers: slow = 1 (value 1 at index 1), fast moves to 3.

• Step 3: (fast = 3)
  Compare nums[3] = 1 with nums[slow] = nums[1] = 1. They are equal, so nums[3] is a duplicate of an existing unique (value 1).
  Action: Do nothing (skip).
  Array state: remains [0, 1, 1, 1, 2, 2, 3].
  Pointers: slow = 1, fast -> 4.

• Step 4: (fast = 4)
  Compare nums[4] = 2 with nums[slow] = nums[1] = 1. Different values, so we found a new unique element (value 2).
  Action: Increment slow to 2 and set nums[2] = 2. Write the new unique at the next position.
  Array state: now [0, 1, 2, 1, 2, 2, 3]. (Index 2 is now 2, which is correct in the unique sequence).
  Pointers: slow = 2 (value 2 at index 2), fast -> 5.

• Step 5: (fast = 5)
  Compare nums[5] = 2 with nums[slow] = nums[2] = 2. They are equal, so it's a duplicate of 2.
  Action: Skip.
  Array state: remains [0, 1, 2, 1, 2, 2, 3].
  Pointers: slow = 2, fast -> 6.

• Step 6: (fast = 6)
  Compare nums[6] = 3 with nums[slow] = nums[2] = 2. They differ, so we have a new unique (value 3).
  Action: Increment slow to 3 and set nums[3] = 3.
  Array state: now [0, 1, 2, 3, 2, 2, 3]. (The first four positions are now 0,1,2,3 — all unique).
  Pointers: slow = 3, fast -> 7 (fast has reached the end of the array).

• End: fast has finished scanning the array. We compute the result length as slow + 1 = 3 + 1 = 4. The array’s first four elements [0, 1, 2, 3] are the unique set, which matches expectation. The values after index 3 can be ignored.

Throughout this process, each duplicate was ignored, and each new unique element was written to the next available position at the front of the array. This example demonstrates how the algorithm incrementally builds the deduplicated part of the array in-place.

Common Mistakes and How to Avoid Them

When solving this problem, beginners often run into a few pitfalls:

• Modifying the Array During Iteration (Incorrectly): A naive attempt might try to remove duplicates by deleting elements (e.g., using list.remove() or shifting elements one by one) while iterating. This is error-prone because removing shifts the array and can skip elements or go out of bounds. If you ever remove an element in a loop, adjust the index appropriately or use a backward loop. In this problem, it’s simpler to avoid deletion altogether by using the two-pointer overwrite strategy. The pseudocode for deletion (removing and shifting) is O(n²) and unnecessary. Instead, focus on moving unique elements into place.

• Not Handling Empty Arrays: Always consider the edge case of an empty input. If nums = [], the function should return 0 without accessing any index. Many two-pointer solutions assume at least one element (setting slow = 0 and starting fast = 1), which would fail on an empty list. A simple check at the start (if not nums: return 0) prevents errors.

• Off-by-One Errors with Indices: Getting the final length wrong by 1 is common. Remember that if slow is an index (0-based) of the last unique element, the count of elements is slow + 1. For example, if slow = 3 (pointing to the 4th element), then there are 4 unique elements (indices 0 through 3). Also, when using a loop, ensure you loop through the correct range (e.g., in Python, for i in range(1, len(nums)): goes from index 1 to len(nums)-1 inclusive, which is correct to compare each element with its previous one).

• Comparing or Writing to the Wrong Index: In the two-pointer approach, some mistakes include always comparing nums[fast] to nums[fast-1] instead of to the last unique (nums[slow]). While nums[fast] != nums[fast-1] also works in this specific problem (because sorted means any new unique will differ from the immediate previous element), conceptually it’s clearer to compare to nums[slow] – the last placed unique element. Ensure that when you write nums[slow] = nums[fast], you increment slow first (or after, depending on how you set it up) correctly. Misplacing the increment could overwrite at the wrong index.

• Using Extra Data Structures without Considering Order: If using a set to remove duplicates, remember that a normal set does not preserve order. In a sorted array, you could use a set and then sort the result, but sorting is an extra step (O(n log n)) and not needed if you take advantage of the sorted input. If preserving the original order of unique elements is important (which it is here), be careful with approaches that might scramble that order.

• Not Returning the Correct Value: The problem requires returning the count of unique elements, not the modified array itself. A common mistake is to return the array or to print the result instead of returning it in the function. The function should modify the array in-place and return the integer k. The provided testing code (in the problem description) verifies both the return value and the first k elements of the array.

By keeping these points in mind, you can avoid the typical bugs. A good practice is to manually walk through your code with simple cases (like the step-by-step example above or edge cases) to ensure your logic holds for all scenarios.

Edge Cases to Consider

You should test your solution against a variety of edge cases to ensure it works for all of them:

• Empty Array: nums = []. The result should be 0, and the array remains empty. (By constraints, the length is at least 1, but it’s good to handle this gracefully in code in case of no input.)

• Single Element Array: nums = [5]. The result should be 1, and the array stays as [5] (one unique element, nothing to remove).

• All Duplicates: nums = [7, 7, 7, 7]. The result should be 1, with the array’s first element 7 and the rest ignored. This tests that your loop correctly skips over multiple duplicates and handles a scenario where almost every element is a duplicate.

• No Duplicates (All Elements Unique): nums = [1, 2, 3, 4]. The result should be 4 (the length of the array) and the array remains unchanged. The algorithm should essentially recognize that every element is unique and not change anything except the returned value.

• Alternating Duplicates: nums = [1, 1, 2, 2, 3, 3]. Result should be 3 with array [1, 2, 3, ...]. This checks that when duplicates come in pairs, they’re properly reduced.

• Array with Negative and Positive Values: nums = [-1, -1, 0, 0, 0, 1, 2, 2]. Result should be 4 with array [-1, 0, 1, 2, ...]. This is just to ensure that values and sign don’t matter for logic (only equality checks matter), and the algorithm works on the entire allowed range of values.