LeetCode: Removing Duplicates from a Sorted Array in Java

One common problem encountered in technical interviews is removing duplicates from a sorted array. This problem tests your understanding of array manipulation, in-place modifications, and algorithm efficiency. Let’s walk through the problem, understand the constraints, and then delve into an effective solution.

Problem Statement

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. After modifying the array, return the number of unique elements (k).

Requirements

• Modify the array in-place to keep the unique elements at the beginning.
• Return the count of unique elements.
• The elements beyond the first k elements are irrelevant.

Example

Example 1

• Input: nums = [1, 1, 2]
• Output: 2, nums = [1, 2, _]
• Explanation: The function returns k = 2, with the first two elements of nums being 1 and 2 respectively. The elements beyond the first k are irrelevant.

Example 2

• Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
• Output: 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]
• Explanation: The function returns k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.

Constraints

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

Solution Approach

We can solve this problem using a two-pointer technique. This method ensures that we can modify the array in-place and achieve the desired result efficiently.

Steps

1. Initialization: Use two pointers, i and j. j will track the position of the last unique element.
2. Iteration: Start iterating with i from the second element of the array.
3. Comparison: If nums[i] is different from nums[j], it indicates a unique element. Increment j and update nums[j] to nums[i].
4. Return: After processing, j+1 will be the number of unique elements.

Solution Code

class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[j]) {
                j++;
                nums[j] = nums[i];
            }
        }
        return j + 1;
    }
}

Explanation

1. Initialization: Start with j = 0 because the first element is always unique.
2. Iteration and Comparison: Iterate through the array starting from the second element. For each element, check if it is different from the last unique element tracked by j. If so, increment j and update the value at nums[j] to the current element.
3. Return Value: The value of j + 1 gives the count of unique elements because j is zero-based.

Time Complexity Analysis

The time complexity of this solution is O(n), where n is the length of the array. This is because we traverse the array once with a single loop.

Space Complexity Analysis

The space complexity of this solution is O(1) since we are using a constant amount of extra space. We only use two extra integer variables (i and j) regardless of the input size.

Example Walkthrough

Let’s trace the example [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]:

• Initial state: j = 0
• Iteration:
• i = 1: nums[1] (0) is equal to nums[0] (0), skip.
• i = 2: nums[2] (1) is different from nums[0] (0), increment j to 1, set nums[1] = 1.
• i = 3: nums[3] (1) is equal to nums[1] (1), skip.
• i = 4: nums[4] (1) is equal to nums[1] (1), skip.
• i = 5: nums[5] (2) is different from nums[1] (1), increment j to 2, set nums[2] = 2.
• Continue similarly for remaining elements.
• Final array state: [0, 1, 2, 3, 4, _, _, _, _, _]
• j = 4, hence return j + 1 = 5.

Conclusion

This solution effectively removes duplicates in-place, maintaining an optimal time complexity of O(n) and a space complexity of O(1). The constraints ensure the array has at least one element, which simplifies the solution by removing the need to handle an empty array. This method ensures that the unique elements are retained at the beginning of the array, making it a practical and efficient approach to solving the problem.