Remove Duplicates from Sorted Array

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];
}

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

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 k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

---

The title and description make our task somewhat confusing.

What we are being asked to do is count how many unique numbers are in the sorted array that contains duplicates, that's it.  We have to do this in place, which means not utilizing any HashSets, HashMaps, or anything like that.

From that task description, this problem is very similar to Move Zeroes and String Compression.

What we can do is utilize two pointers, these are particularly helpful for sorted arrays.  The left pointer will act as a placeholder for writing the next unique value, and the right will act as a scout for the next differing number which will be the next unique value.  Once a new unique number is found, we will move the left placeholder by one and write the next unique value in place.

What this will do is continuously build a unique partition of unique values, and we will just need to return the length of that partition.

---

First off, if the length of the input array is zero then the output array will be zero as well.

        if not nums:
            return 0

 

Otherwise, we will set our two pointers at the first index of the input array.

        left, right = 0, 0

 

While the right pointer hasn't passed the end of the input array, we will keep scouting for numbers.

        while right < len(nums):

 

Here's the trick.

If the values at the two pointers are ever mismatched, then we have found the next unique number that we'll need to place in our nonduplicate partition of the input array.

Since the array is sorted, the next mismatched number will be the next unique number we'll need to include.

1

1

2

2

2

3

3

 ^    ^

 

To include this next unique number, we will move the left pointer forward so it becomes a placeholder for it, then we will write the value at the right pointer to the left index.

1

1

2

2

2

3

3

    ^ ^

1

2

2

2

2

3

3

    ^ ^

 

Now the left pointer will wait for the next mismatch and it will do the same thing.

1

2

2

2

2

3

3

    ^          ^

 

1

2

3

2

2

3

3

       ^       ^

            if nums[left] != nums[right]:
                left += 1
                nums[left] = nums[right]
            right += 1

 

We can see the left pointer is building a partition of unique numbers and all we need to do is return that partition length, plus one since arrays index at zero.

1

2

3

2

2

3

3

 

        return left + 1

---