How do you solve Remove Duplicates from Sorted Array II?

Initialize a write pointer at index 2. Iterate through the array starting from index 2. For each element, compare it with the element at write-2. If different, write the current element at the write pointer and increment write. Finally, return the write pointer as the new length of the array.

Remove Duplicates from Sorted Array II

Q: What is the time complexity of Remove Duplicates from Sorted Array II?

O(n). The algorithm makes a single pass through the array, performing constant-time comparisons and writes for each element.

Q: What pattern does Remove Duplicates from Sorted Array II use?

The Pattern: Two Pointers (In-Place Overwrite) The Heuristic: When removing duplicates with constraints on allowed occurrences, use a write pointer to track the position to overwrite and compare the current read element with the element at a fixed offset behind the write pointer to enforce the occurrence limit.

Medium Two Pointers

Problem

Given a sorted integer array nums, remove duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array; modify the input array in-place with O(1) extra memory.

1 ≤ nums.length ≤ 3 * 10⁴
−10⁴ ≤ nums[i] ≤ 10⁴
nums is sorted in non-decreasing order

Example

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

Output: 5

The algorithm allows each element to appear at most twice. Initially, the array has three '1's. The first two '1's are kept, but the third is removed by overwriting. The resulting array is [1,1,2,2,3], and the returned length is 5.

Approach

Straightforward Solution

A naive approach would create a new array or use extra space to track counts, which violates the O(1) space constraint. Alternatively, a brute-force approach would repeatedly shift elements to remove duplicates, resulting in O(n^2) time complexity.

Core Observation

Because the array is sorted, duplicates appear consecutively. The problem reduces to allowing at most two occurrences of each unique element, which can be tracked by comparing the current element with the element two positions before the current write position.

Path to Optimal

Preview

The key insight is to use two pointers: one for reading the array and one for writing the allowed elements. By starting the write pointer at index 2, the algorithm compares the current read element with the element at write-2…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize a write pointer at index 2. Iterate through the array starting from index 2…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm makes a single pass through the array, performing constant-time comparisons and writes for each element.

Space

O(1)

Only a few integer variables are used for pointers; no additional data structures are allocated, satisfying the in-place requirement.

Pattern Spotlight

Two Pointers (In-Place Overwrite)

When removing duplicates with constraints on allowed occurrences, use a write pointer to track the position to overwrite and compare the current read element with the element at a fixed offset behind the write pointer to enforce the occurrence limit.

Solution

Python

1class Solution:
  def removeDuplicates(self, nums: List[int]) -> int:
      write = 2
4
      for i in range(2, len(nums)):
          if nums[i] != nums[write - 2]:
              nums[write] = nums[i]
              write += 1
9
      return write

Step-by-Step Solution

Initialize Write Pointer to Allow First Two Elements

3	`write = 2`

Objective

To set the starting position for writing allowed elements, assuming the first two elements are always valid.

Key Insight

Since duplicates are allowed up to twice, the first two elements can always be kept. Starting the write pointer at index 2 means the algorithm only needs to check from the third element onward whether to overwrite or skip, simplifying boundary conditions and ensuring correctness.

Interview Quick-Check

Core Logic

Starting the write pointer at 2 leverages the problem constraint that up to two duplicates are allowed, so the first two elements are always included.

State & Boundaries

The loop starts from index 2, ensuring the write pointer and read pointer do not overlap incorrectly.

Iterate Through Array and Overwrite Allowed Elements

To scan the array from the third element, selectively overwriting elements to maintain at most two duplicates.

Return the Length of the Modified Array

To return the count of elements retained after removing excess duplicates.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 6 Critical

if nums[i] != nums[write - 2]:

Check if the current element differs from the element two positions before the write pointer.

This comparison enforces the 'at most twice' rule by ensuring that the current element is not a third or further duplicate of the same value already written.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why does comparing the current element with the element at write-2 ensure that duplicates appear at most twice?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Remove Duplicates from Sorted Array II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Remove Duplicates from Sorted Array II drill

or drill a free problem

1	`class Solution:`
2	`def removeDuplicates(self, nums: List[int]) -> int:`
3	`write = 2`
4
5	`for i in range(2, len(nums)):`
6	`if nums[i] != nums[write - 2]:`
7	`nums[write] = nums[i]`
8	`write += 1`
9
10	`return write`