Remove Duplicates from Sorted Array II

Medium Arrays & Hashing Two Pointer Original on LeetCode

Reported atAppleFreshworks

Remove Duplicates from Sorted Array II is a medium arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers, compare two back), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (shift out every extra copy) up.

Problem

You get an integer array nums sorted in non-decreasing order. Remove extra copies in place so that every distinct value appears at most twice, keeping the remaining elements in their original relative order.

Return k, the number of elements left. The first k slots of nums must hold the result; what is stored after them does not matter. Do it with O(1) extra memory.

Examples

Example 1

Input
nums = [2, 2, 2, 5, 7, 7, 7, 7]
Output
5, nums = [2, 2, 5, 7, 7, _, _, _]
Why
Each value is kept at most twice: two 2s, one 5, two 7s. Slots after the first 5 do not matter.

Example 2

Input
nums = [-3, -1, -1, 0, 4]
Output
5, nums = [-3, -1, -1, 0, 4]
Why
No value appears more than twice, so the array is unchanged.

Example 3

Input
nums = [8, 8, 8]
Output
2, nums = [8, 8, _]
Why
Only the third 8 has to go.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in non-decreasing order.
  • Use O(1) extra memory: modify nums in place.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (shift out every extra copy)O(n²)O(1)
Optimal (two pointers, compare two back)O(n)O(1)

1Brute force (shift out every extra copy)

TimeO(n²)Each deletion can shift up to n elements, and there can be up to n deletions.
SpaceO(1)Only a few indices.

Walk through the array; whenever an element is the third (or later) copy of its value, delete it by shifting everything after it one step left and shrinking the logical length.

  1. Let len = n and start at i = 2.
  2. If nums[i] equals both nums[i - 1] and nums[i - 2], shift nums[i + 1 .. len - 1] one step left and decrement len (do not advance i).
  3. Otherwise advance i.
  4. Return len.
class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        int i = 2;
        while (i < len) {
            if (nums[i] == nums[i - 1] && nums[i] == nums[i - 2]) {
                for (int j = i + 1; j < len; j++) nums[j - 1] = nums[j];
                len--;
            } else {
                i++;
            }
        }
        return len;
    }
}

2Optimal (two pointers, compare two back)

TimeO(n)One pass, constant work per element.
SpaceO(1)Only the write index.

Build the answer in the prefix nums[0..k). Since the array is sorted, the next element x would be a third copy exactly when x == nums[k - 2] (the kept prefix is sorted too). Otherwise copy it to nums[k] and grow the prefix.

  1. Set k = 0.
  2. For each x in nums: if k < 2 or x != nums[k - 2], write nums[k] = x and increment k.
  3. Return k.
class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 0;
        for (int x : nums) {
            if (k < 2 || x != nums[k - 2]) {
                nums[k++] = x;
            }
        }
        return k;
    }
}

Edge cases to test

  • Arrays of length 1 or 2, which never change
  • All elements equal
  • No duplicates at all
  • A long run in the middle followed by distinct values
  • Negative numbers

Hints

Hint 1

Because the array is sorted, all copies of a value sit next to each other.

Hint 2

Keep a write index k for the kept prefix. A new element may be kept unless it equals nums[k - 2], the element two places back in the kept part.

FAQ

What is the best time complexity for Remove Duplicates from Sorted Array II?

Optimal (two pointers, compare two back) runs in O(n) time and O(1) extra space. One pass, constant work per element.

Which pattern does Remove Duplicates from Sorted Array II use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Remove Duplicates from Sorted Array II?

Yes. Brute force (shift out every extra copy) takes O(n²) time and O(1) space. Walk through the array; whenever an element is the third (or later) copy of its value, delete it by shifting everything after it one step left and shrinking the logical length.

Which edge cases should I test for Remove Duplicates from Sorted Array II?

Arrays of length 1 or 2, which never change; All elements equal; No duplicates at all; A long run in the middle followed by distinct values; Negative numbers.