DSA Sheet by Technical Mickey

Remove Duplicates from Sorted Array

Removing duplicates from a sorted array is a common problem in coding interviews and real-world applications. Let’s dive into the details of this problem, how to solve it efficiently, and what the solution entails.

Problem Statement

Given an integer array nums sorted in non-decreasing order, the task is to:

Remove the duplicates in-place such that each unique element appears only once.
Maintain the relative order of the elements.
Return the number of unique elements in nums.

Key Points to Consider

In-place Modification: The changes must be made directly to the input array without using extra space for another array.
Output Requirements: The first k elements of nums should contain the unique elements in their original order, where k is the count of unique elements. The remaining elements in the array can be ignored.

Custom Judge

The custom judge evaluates your solution as follows:

				
					int[] nums = {...}; // Input array
int[] expectedNums = {...}; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

f all assertions pass, your solution is accepted.

Examples

Example 1

Input: nums = [1,1,2]

Output:

k = 2
nums = [1,2,_]

Explanation: The function should return k = 2, with the first two elements of nums being 1 and 2. The remaining elements are ignored.

Example 2

Input: nums = [0,0,1,1,1,2,2,3,3,4]

Output:

k = 5
nums = [0,1,2,3,4,_,_,_,_,_]

Explanation: The function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4. The rest are irrelevant.

Constraints

1 <= nums.length <= 3 * 10^4
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

Approach to Solution

Algorithm

Use two pointers:
- i: Tracks the position of the last unique element.
- j: Traverses the array.
Compare the current element (nums[j]) with the last unique element (nums[i]).
If nums[j] is different, increment i and update nums[i] to nums[j].
Continue this process until the array is fully traversed.
Return i + 1 as the count of unique elements.

Implementation

Here is a Java implementation of the solution:

				
					public class RemoveDuplicates {
    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int i = 0; // Pointer for the last unique element
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }

        return i + 1; // Number of unique elements
    }

    public static void main(String[] args) {
        int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        int k = removeDuplicates(nums);

        System.out.println("Number of unique elements: " + k);
        System.out.print("Updated array: ");
        for (int i = 0; i < k; i++) {
            System.out.print(nums[i] + " ");
        }
    }
}

Explanation

Start with i = 0 (the first unique element).
Traverse the array with j starting from 1.
If nums[j] != nums[i], it means we found a new unique element.
- Increment i.
- Update nums[i] with the new unique element.
The length of the unique subarray is i + 1.

Time and Space Complexity

Time Complexity: O(n) — We traverse the array once.
Space Complexity: O(1) — No additional space is used.

Testing

Example Input and Output

Test Case 1

Input: nums = [1, 1, 2]

Output: k = 2, nums = [1, 2, _]

Test Case 2

Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

Output: k = 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

Conclusion

The “Remove Duplicates from Sorted Array” problem demonstrates the power of using efficient in-place algorithms. By leveraging a two-pointer technique, we achieve optimal performance with minimal space usage. Mastering such patterns is key to excelling in coding challenges and interviews.

Have you tried solving this problem? What approach did you take? Let’s discuss in the comments below!

Technical Mickey