Scale Engineer

Remove Duplicates from Sorted Array

Easy
#0026Time: O(N)Space: O(k)24 companies
Patterns
Two Pointers
Data structures
Array
Companies
AccentureAdobeAmazonApple

Prompt

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:

The judge will test your solution with the following code:

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

If all assertions pass, then your solution will be accepted.

 

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

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward approach is to use an auxiliary data structure, like another array or a list, to store only the unique elements. We can iterate through the original sorted array and add an element to our auxiliary array only if it's different from the last element we added. After processing all elements, we copy the contents of the auxiliary array back into the beginning of the original array and return its size.

Algorithm

  • Check for the edge case where the input array nums is empty. If so, return 0.
  • Create a new ArrayList<Integer> called uniqueElements.
  • Add the first element of nums (nums[0]) to uniqueElements.
  • Iterate through the nums array from the second element (i = 1 to nums.length - 1).
  • For each element nums[i], compare it with the previous element nums[i-1].
  • If nums[i] is not equal to nums[i-1], it's a new unique element, so add it to the uniqueElements list.
  • After the loop finishes, the uniqueElements list contains all the unique items in the correct order.
  • Copy the elements from uniqueElements back to the original nums array. Iterate from j = 0 to uniqueElements.size() - 1 and set nums[j] = uniqueElements.get(j).
  • Finally, return the size of the uniqueElements list, which is the count of unique elements k.

Walkthrough

This method prioritizes simplicity over space efficiency. It doesn't modify the array in-place directly during the identification of unique elements, but rather uses an intermediate storage.

import java.util.ArrayList;import java.util.List; class Solution {    public int removeDuplicates(int[] nums) {        if (nums.length == 0) {            return 0;        }         List<Integer> uniqueElements = new ArrayList<>();        uniqueElements.add(nums[0]);         for (int i = 1; i < nums.length; i++) {            if (nums[i] != nums[i-1]) {                uniqueElements.add(nums[i]);            }        }         for (int i = 0; i < uniqueElements.size(); i++) {            nums[i] = uniqueElements.get(i);        }         return uniqueElements.size();    }}

Complexity

Time

O(N)

Space

O(k)

Trade-offs

Pros

  • Conceptually simple and easy to follow.

  • Separates the logic of finding unique elements from modifying the original array.

Cons

  • Requires extra space proportional to the number of unique elements, which can be up to O(N) in the worst case (all elements are unique).

  • Violates the strict 'in-place' O(1) space complexity constraint of the problem.

Solutions

public class Solution { public int RemoveDuplicates ( int [] nums ) { int k = 0 ; foreach ( int x in nums ) { if ( k == 0 || x != nums [ k - 1 ]) { nums [ k ++] = x ; } } return k ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem