Scale Engineer

Remove Duplicates from Sorted Array II

Med
#0080Time: O(N^2)Space: O(1)14 companies
Patterns
Two Pointers
Data structures
Array
Companies
AccoliteAdobeAmazonApple

Prompt

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

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,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 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,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,_,_]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through the array, identifies groups of duplicate elements, and if a group has more than two elements, it manually shifts the rest of the array to overwrite the excess duplicates. This is an intuitive but inefficient way to solve the problem in-place.

Algorithm

  • Initialize a pointer i = 0 and the effective length n = nums.length.
  • Loop while i is less than n.
  • Inside the loop, use another pointer j starting from i to find the end of the contiguous block of elements equal to nums[i].
  • Calculate the count of these elements (j - i).
  • If count > 2, it means there are count - 2 excess duplicates.
    • Shift all elements from index j to n-1 to the left by count - 2 positions.
    • Decrease the effective length n by count - 2.
    • Advance i by 2, since we've kept two elements.
  • If count <= 2, no elements are removed. Advance i to j to process the next distinct number.
  • After the loop terminates, return the final effective length n.

Walkthrough

The core idea is to process the array in chunks of identical numbers. We use a pointer i to mark the beginning of a chunk and another pointer j to find its end. The number of elements in the chunk is count = j - i.

If count is greater than 2, we have count - 2 excess elements that need to be removed. We achieve this by shifting all subsequent elements (from index j to the end) to the left by count - 2 positions. This overwrites the unwanted duplicates. After shifting, we must also decrease the effective length of the array. The pointer i is then advanced by 2, as we keep two elements from the current chunk.

If count is 2 or less, no removal is needed, and we simply advance i to j to start processing the next chunk of numbers.

This method is considered brute-force because the shifting operation can be very time-consuming, especially for arrays with many duplicates at the beginning.

class Solution {    public int removeDuplicates(int[] nums) {        int i = 0;        int n = nums.length;        while (i < n) {            // Find the end of the block of duplicates            int j = i;            while (j < n && nums[j] == nums[i]) {                j++;            }            int count = j - i;             if (count > 2) {                int numToRemove = count - 2;                // Shift elements to the left                for (int k = j; k < n; k++) {                    nums[k - numToRemove] = nums[k];                }                // Update the effective length                n -= numToRemove;                // Move i to the next position after the two kept elements                i += 2;            } else {                // Move to the next distinct number                i = j;            }        }        return n;    }}

Complexity

Time

O(N^2)

Space

O(1)

Trade-offs

Pros

  • It correctly solves the problem in-place, adhering to the O(1) extra space requirement.

Cons

  • Highly inefficient with a time complexity of O(N^2) in the worst-case scenario.

  • The logic for index manipulation and shifting is complex and can be difficult to implement correctly.

Solutions

public class Solution {    public int RemoveDuplicates(int[] nums) {        int k = 0;        foreach(int x in nums) {            if (k < 2 || x != nums[k - 2]) {                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