Remove Duplicates from Sorted Array

Photo by Clark Tibbs on Unsplash

Remove Duplicates from Sorted Array

Two Pointer problem

Jul 24, 2023ยท

3 min read

Play this article

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.

Hey there! Today, we're going to talk about a cool and useful problem-solving technique in the world of competitive programming. Imagine you have an integer array, and you want to remove any duplicate elements while keeping the relative order intact. Sounds interesting, right? Let's dive into it!

Picture this: you have an array called nums sorted in non-decreasing order. Your task is to remove the duplicate elements from it.

But here's the catch: you must do it, in-place meaning you can't create a new array to store the unique elements. You need to modify the original array "nums" itself, keeping the first k elements containing the unique values.

Note: Remember whenever a input is a sorted array, and it asks you to do any computation in-place by comparing any two indexs, most probably you will need to use Two Pointer Technique.

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

Alright, let's start by understanding the problem a bit more. Consider "k" as the number of unique elements in the array after removing the duplicates. So, the goal is to modify the array in such a way that the first "k" elements are the unique ones in the order they were originally present in the array.

Example 1:

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).

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 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).


  • 1 <= nums.length <= 3 * 10<sup>4</sup>

  • -100 <= nums[i] <= 100

  • nums is sorted in non-decreasing order.

We've got a Java solution to tackle this problem, and it involves a smart technique using two pointers. Let's break it down step by step.

  1. We'll create two pointers, pointer1 and i, initialized to 0.

  2. We'll then iterate through the array using the i pointer from index 0 to the end.

  3. At each step, we'll check if the element at nums[pointer1] is different from the element at nums[i]

  4. If they are different, it means we've encountered a new unique element. So, we'll increment pointer1 and set nums[pointer1] to the new unique element found at nums[i]

  5. We keep repeating this process until we reach the end of the array.

  6. Finally, we'll return pointer1+1 which will give us the value of k (the number of unique elements in the modified array).

Isn't that a clever and efficient way to solve the problem? By doing this in-place modification, we save memory and achieve a time-efficient solution.

Now, to ensure our solution is correct, there's a custom judge that tests our implementation with some test cases. The judge checks if the modified array "nums" matches the expected answer "expectedNums" (which contains the correct unique elements with their correct length).

That's it! You've learned a powerful technique to remove duplicates from a sorted array in-place maintaining the relative order of the elements. This approach is widely used in competitive programming and coding interviews, so keep it in your problem-solving toolbox!

Remember, practice makes perfect, so don't forget to try out this technique on various arrays to master it. Happy coding! ๐Ÿš€