Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Remove Duplicates from Sorted Array II

Try it yourself
MediumProblemExternal link

Description

You get an integer array nums sorted in non-decreasing order. Remove the extra copies in place, so that each value appears at most twice, and keep the numbers in their original order.

Return k, how many numbers are left. The first k seats of nums must hold them; whatever sits after seat k doesn't matter.

Use O(1) extra memory: change nums itself instead of building a second array.

How it's checked: the judge reads k, then compares the first k numbers of nums with the expected ones.

Examples

Example 1

Input: nums = [1, 1, 1, 2, 2, 3]

Output: 5, nums = [1, 1, 2, 2, 3, _]

Explanation: The third 1 is removed. Two 1s, two 2s and one 3 stay, so k = 5 and the first five seats are [1, 1, 2, 2, 3].

Example 2

Input: nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]

Output: 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]

Explanation: Four 1s become two. Everything else already appears at most twice, so k = 7: [0, 0, 1, 1, 2, 3, 3].

Example 3

Input: nums = [-2, -2, -2, -2]

Output: 2, nums = [-2, -2, _, _]

Explanation: One value, four copies: only two stay, so k = 2 and the first two seats are [-2, -2].

Constraints

  • 1 ≤ nums.length ≤ 3 × 10^4
  • -10^4 ≤ nums[i] ≤ 10^4
  • nums is sorted in non-decreasing order

Editorial

Brute Force

Intuition

Build the answer somewhere else first. Walk nums and copy each number into a second list, unless that list already ends with two copies of it. Because nums is sorted, all copies of a value sit together, so "the last two kept numbers" is the only place a copy can be.

When the walk is done, copy the list back into the front of nums. It works, but the second list is exactly what the problem rules out.

Step-by-Step Explanation

Let's trace nums = [1, 1, 1, 2, 2, 3]:

  1. 1: copy it, so the list is [1].
  2. 1: copy it, so the list is [1, 1].
  3. 1: the list already ends with two 1s, so skip it.
  4. 2: copy it, so the list is [1, 1, 2].
  5. 2: copy it, so the list is [1, 1, 2, 2].
  6. 3: copy it, so the list is [1, 1, 2, 2, 3].

Copy [1, 1, 2, 2, 3] back into the front of nums and return k = 5.

Copy the Keepers to a Second List — Each number is copied into the bottom row unless it would be a third copy.

Algorithm

  1. Create an empty list kept.
  2. For each x in nums: if kept has fewer than two numbers, or kept[-2] != x, append x.
  3. Copy kept into the front of nums and return its length.

Code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        vector<int> kept;
        for (int x : nums) {
            // keep x unless the list already ends with two copies of it
            if (kept.size() < 2 || kept[kept.size() - 2] != x) kept.push_back(x);
        }
        for (int i = 0; i < (int)kept.size(); i++) nums[i] = kept[i];   // copy back into the front of nums
        return kept.size();
    }
};

from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        kept = []
        for x in nums:
            # keep x unless the list already ends with two copies of it
            if len(kept) < 2 or kept[-2] != x:
                kept.append(x)
        nums[:len(kept)] = kept           # copy back into the front of nums
        return len(kept)

class Solution {
    public int removeDuplicates(int[] nums) {
        int[] kept = new int[nums.length];
        int size = 0;
        for (int x : nums) {
            // keep x unless the list already ends with two copies of it
            if (size < 2 || kept[size - 2] != x) kept[size++] = x;
        }
        System.arraycopy(kept, 0, nums, 0, size);   // copy back into the front of nums
        return size;
    }
}

var removeDuplicates = function(nums) {
    const kept = [];
    for (const x of nums) {
        // keep x unless the list already ends with two copies of it
        if (kept.length < 2 || kept[kept.length - 2] !== x) kept.push(x);
    }
    for (let i = 0; i < kept.length; i++) nums[i] = kept[i];   // copy back into the front of nums
    return kept.length;
};

Complexity Analysis

Time Complexity: O(n)

One pass to build the list, one pass to copy it back.

Space Complexity: O(n)

The second list can hold nearly every number: with no duplicates at all, it's a full copy of nums.

Why This Approach Is Not Efficient

It's already O(n) in time. The problem is the memory: the second list costs up to n extra seats, and the task asks for O(1).

The tempting in-place fix makes things worse. Shifting everything left each time you meet a third copy keeps the memory at O(1), but every shift moves the rest of the array: with 30,000 copies of one value that's about 450 million moves, O(n²).

Look at the second list again, though. It never gets longer than the part of nums you've already read: each number read adds at most one number to it. So the list can live in nums itself, in the seats you've finished reading. That's the whole optimal solution.

Optimal Approach - Two Pointers

Intuition

Use nums itself as the second list. Keep two indexes, both starting at 0:

  • read visits every number once.
  • write is the next free seat at the front. Everything before it is the answer so far.

When is nums[read] a third copy? When the answer so far already ends with two of it. Because the array is sorted, that's exactly when nums[write - 2] == nums[read]. Compare with nums[write - 2], the part you've written, not with nums[read - 2]: the writes change the input, so the input two seats back may no longer hold what it did.

write never gets ahead of read, so a write only ever lands on a seat that has already been read. Nothing is lost.

Step-by-Step Explanation

Let's trace nums = [1, 1, 1, 2, 2, 3]:

  1. read = 0, nums[read] = 1: write = 0 is below 2, so seat 0 gets 1. write = 1.
  2. read = 1, nums[read] = 1: write = 1 is below 2, so seat 1 gets 1. write = 2.
  3. read = 2, nums[read] = 1: nums[write - 2] = 1 is the same, so two 1s are already kept. Skip it.
  4. read = 3, nums[read] = 2: nums[write - 2] = 1 is different, so seat 2 gets 2. write = 3.
  5. read = 4, nums[read] = 2: nums[write - 2] = 1 is different, so seat 3 gets 2. write = 4.
  6. read = 5, nums[read] = 3: nums[write - 2] = 2 is different, so seat 4 gets 3. write = 5.

Result: k = 5, and the first 5 seats hold [1, 1, 2, 2, 3]. The last seat still holds the 3 it started with; it's ignored.

Read and Write Pointers — Compare Two Seats Back — Each number is compared with the value written two seats back; violet seats are the answer so far.

Algorithm

  1. Set write = 0.
  2. For read from 0 to n - 1:
    • If write < 2 or nums[read] != nums[write - 2], set nums[write] = nums[read] and add 1 to write.
  3. Return write.

Code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int write = 0;
        for (int read = 0; read < (int)nums.size(); read++) {
            // nums[write - 2] is in the part already written: if it equals nums[read], two copies are kept
            if (write < 2 || nums[read] != nums[write - 2]) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }
};

from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        write = 0
        for read in range(len(nums)):
            # nums[write - 2] is in the part already written: if it equals nums[read], two copies are kept
            if write < 2 or nums[read] != nums[write - 2]:
                nums[write] = nums[read]
                write += 1
        return write

class Solution {
    public int removeDuplicates(int[] nums) {
        int write = 0;
        for (int read = 0; read < nums.length; read++) {
            // nums[write - 2] is in the part already written: if it equals nums[read], two copies are kept
            if (write < 2 || nums[read] != nums[write - 2]) {
                nums[write] = nums[read];
                write++;
            }
        }
        return write;
    }
}

var removeDuplicates = function(nums) {
    let write = 0;
    for (let read = 0; read < nums.length; read++) {
        // nums[write - 2] is in the part already written: if it equals nums[read], two copies are kept
        if (write < 2 || nums[read] !== nums[write - 2]) {
            nums[write] = nums[read];
            write++;
        }
    }
    return write;
};

Complexity Analysis

Time Complexity: O(n)

read visits each number once, and each visit does one comparison and at most one write.

Space Complexity: O(1)

Two integers, read and write, whatever the size of the array.

Common Mistakes

Each of these passes at least one example or looks right at a glance, and the tests still reject it. The outputs below come from running the code.

Comparing with the input instead of what you wrote. if read < 2 or nums[read] != nums[read - 2]:

On nums = [1, 1, 1, 2, 2] it returns k = 3 with [1, 1, 2] in front; the answer is k = 4 with [1, 1, 2, 2] in front. The writes change the input. By the time read gets far enough, nums[read - 2] may already hold a value copied from further on, so a number can look like a third copy when it's only the second. Compare with what you wrote: nums[write - 2].

Skipping the check for one seat too many. if write <= 2 or nums[read] != nums[write - 2]:

On nums = [1, 1, 1] it returns k = 3 with [1, 1, 1] in front; the answer is k = 2 with [1, 1] in front. With write <= 2 the check is skipped for the third seat as well, so a third copy of the first value is always kept. Only the first two seats are free: the test is write < 2.

Starting at index 2 without checking the length. write = 2

On nums = [4] it returns k = 2 with [4] in front; the answer is k = 1 with [4] in front. Starting with write = 2 assumes the array has at least two numbers. With a single number nothing runs and the function returns 2, one more than the array holds.

Where This Pattern Is Taught

This problem practises same-direction two pointers: one reads, one writes. It's taught in Same-Direction Two Pointers: Changing an Array in Place, where the same loop keeps at most k copies of each value, and k = 1 is Remove Duplicates from Sorted Array.