Problem Description

Question

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. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
Return k.

Custom Judge:

Example 1:

Input:nums=[1,1,2]

Output:[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).

Example 2:

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

Output:[0,1,2,3,,,,,]

Explanation: Your function should return k = 4, with the first four elements of nums being 0, 1, 2, and 3 respectively. It does not matter what you leave beyond the returned k.

Constraints:

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

Solve it on LeetCode

Understanding the Problem

At first glance, removing duplicates seems trivial. Just iterate through the array and keep track of unique elements, right? The catch is the in-place requirement. We cannot create a new array to store the results. We must modify the original array and tell the caller how many unique elements exist.

The problem gives us a crucial clue that many overlook: the array is sorted. This means all duplicates are grouped together. In [1, 1, 2, 2, 2, 3], all the 1s are adjacent, all the 2s are adjacent, and so on. We never have to worry about finding a duplicate "later" in the array that we missed earlier.

This sorted property completely changes how we approach the problem. Instead of using a hash set to track seen elements (which would require extra space), we can simply compare adjacent elements. If two adjacent elements are the same, one of them is a duplicate.

The expected return value is k, the count of unique elements. But we also need to physically place those unique elements in the first k positions of the array. The elements beyond position k-1 can be anything since the caller will ignore them.

Approaches

1. Two Pointers Approach

Intuition:

In a sorted array, duplicates always appear next to each other.

This makes it easy to remove duplicates using a two-pointer technique:

writePos – points to the position where the next unique element should be placed
readPos – scans the array to find the next unique element

Whenever we discover a new unique value, we move it to nums[writePos] and advance writePos.

All unique elements end up at the front of the array. Anything beyond writePos is irrelevant.

Steps:

If the array is empty, return 0 since no elements exist.
Initialize writePos = 0, marking where the next unique element should be placed.
Use readPos to scan from the second element onward.
If nums[readPos] is different from nums[writePos], we found a new unique element.

Increment writePos.
Copy nums[readPos] to nums[writePos].

Return writePos + 1, the count of unique elements.

Code:

Complexity Analysis

Time Complexity: O(n), where n is the number of elements in the array. We traverse the array with a single pass using the two pointers.
Space Complexity: O(1), as we are using extra space only for the pointers and directly modifying the input array.

Remove Duplicates from Sorted Array

Ashish Pratap Singh