Remove Duplicates from Sorted Array II

Medium
252.

Remove Duplicates from Sorted Array II

Remove Duplicates from Sorted Array II is a medium coding problem on arrays and two pointers, asked in Amazon, Microsoft, Adobe and Meta interviews.

Given an integer array nums sorted in non-decreasing order, remove extra copies so that each distinct value appears at most twice, keeping the relative order.

Return the resulting array.

Example 1

Input
nums = [1,1,1,2,2,3]
Output
[1,1,2,2,3]
Explanation
The third 1 is dropped.

Example 2

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

Example 3

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

Constraints

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

Follow-up: The interview version does this in place with O(1) extra memory.

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var removeDuplicates = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove Duplicates from Sorted Array II — Problem & Solution

Remove Duplicates from Sorted Array II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Remove Duplicates from Sorted Array II is a medium coding problem on arrays and two pointers, asked in Amazon, Microsoft, Adobe and Meta interviews.

Problem statement

Given an integer array nums sorted in non-decreasing order, remove extra copies so that each distinct value appears at most twice, keeping the relative order.

Return the resulting array.

Example 1

Input: nums = [1,1,1,2,2,3]
Output: [1,1,2,2,3]
Explanation: The third 1 is dropped.

Example 2

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

Example 3

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

Constraints

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

Follow-up: The interview version does this in place with O(1) extra memory.

Hints for Remove Duplicates from Sorted Array II

  1. Hint 1

    Keep a write cursor. A value is safe to keep if it differs from the element two places back in the output.

  2. Hint 2

    That single comparison enforces 'at most twice' without counting runs explicitly.

  3. Hint 3

    The first two elements are always kept, which the same check handles automatically.

How to solve Remove Duplicates from Sorted Array II

Keep a value if it differs from the element two places back in the output; that alone enforces "at most twice" on a sorted array.

Approach

  1. Walk the input, appending to out.
  2. Append x when out has fewer than two elements or out[-2] != x.

Why it works

In sorted order, equal values are adjacent; if out[-2] == x then out[-1] == x too and a third copy would follow. Any other value is a new run or a legitimate second copy.

Complexity

  • Time — O(n)
  • Space — O(1) extra in the in-place write-cursor form

Pitfalls

  • Comparing with out[-1] only allows one copy — that is the k = 1 version of the problem.

Reference solution

Python

def removeDuplicates(nums):
    out = []
    for x in nums:
        if len(out) < 2 or out[-2] != x:
            out.append(x)
    return out

Java

public static int[] removeDuplicates(int[] nums) {
    int[] out = new int[nums.length];
    int len = 0;
    for (int v : nums) {
        if (len < 2 || out[len - 2] != v) out[len++] = v;
    }
    return Arrays.copyOf(out, len);
}

C++

vector<int> removeDuplicates(vector<int>& nums) {
    vector<int> out;
    for (int v : nums) {
        if (out.size() < 2 || out[out.size() - 2] != v) out.push_back(v);
    }
    return out;
}

JavaScript

var removeDuplicates = function(nums) {
    const out = [];
    for (let i = 0; i < nums.length; i++) {
        if (out.length < 2 || out[out.length - 2] !== nums[i]) out.push(nums[i]);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique