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

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