How Can You Remove Duplicates from a Sorted Array?

Removing duplicates from a sorted array is a common problem that many encounter while preparing for tech interviews. This task is typically straightforward due to the nature of sorted arrays, which makes it easier to identify duplicates. Let’s break down how to approach this problem and offer a clear solution.

When presented with a sorted array, our goal is to modify the array in place so that each unique element appears only once. The size of the array can also be adjusted to reflect the new number of unique elements. The main advantages of working with a sorted array include that duplicates will always be adjacent, allowing for easier identification and removal.

Step-by-Step Approach

1. Initialization: Start by checking if the array is empty. If it is, return 0 as the count of unique elements. Create a variable to keep track of the index of the last unique element found. This variable will also help manage the position where the next unique element should be placed.

2. Iterate Through the Array: Use a loop to traverse through the array starting from the second element (index 1). Compare each current element with the last unique element found.

3. Check for Uniqueness: If the current element is different from the last unique element, it indicates that we’ve found a new unique element. Place this new unique element in the next position of the array.

4. Update the Index: Increase the index of the last unique element and continue iterating until the end of the array.

5. Final Size: The last value of the index variable will represent the count of unique elements.

Code Example

Here’s a sample implementation in Python:

PythonCopy code

Explanation of the Code

1. Check for an Empty Array: The function first checks if the array is empty and returns 0 if it is.

2. Tracking Uniques: The last_unique_index variable keeps track of where the last unique element is located in the array.

3. Looping through Elements: Starting from the first index, the loop compares each element in the array to the last unique element found. If it finds a new unique element, it updates the sorted_array at the last_unique_index + 1 position.

4. Returning Results: Finally, it returns the count of unique elements, which is one more than the index since the array is zero-indexed.

This efficient approach ensures that we traverse the array only once, giving us a time complexity of O(n), where n is the length of the array, and it modifies the array in place without requiring additional space, making it an optimal solution for the problem of removing duplicates from a sorted array.