Remove Duplicates from Sorted Array easy

Problem Statement

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: nums = [1,1,2] Output: 2, nums = [1,2] Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4] Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Steps

1. Initialize two pointers: i (slow pointer) and j (fast pointer). Both start at index 0.
2. Iterate: The fast pointer j iterates through the array.
3. Compare: If nums[i] is different from nums[j], it means we've encountered a new unique element.
4. Increment and copy: Increment i and copy the value at nums[j] to nums[i+1]. This effectively moves the unique element to the next available position in the compacted array.
5. Return: After iterating through the entire array, i + 1 represents the length of the array containing only unique elements.

Explanation

The algorithm leverages the sorted nature of the input array. Since the array is sorted, duplicate elements will always be adjacent to each other. The slow pointer i tracks the index of the last unique element encountered. The fast pointer j iterates through the array, discovering new unique elements. When a new unique element is found, it's placed right after the last unique element, effectively overwriting the duplicate elements.

Code

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0; //Handle empty array case

        int i = 0; // Slow pointer
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1). We use only a constant amount of extra space for the pointers i and j.