Remove Duplicates from Sorted Array II - Practice Coding Problems

Remove Duplicates from Sorted Array II - Problem

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.

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.

Input & Output

Example 1 — Multiple Duplicates

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

› Output: 5

💡 Note: Remove one duplicate '1' to get [1,1,2,2,3]. Return length 5. Final array: [1,1,2,2,3,3] where we only consider first 5 elements.

Example 2 — Some Triples

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

› Output: 7

💡 Note: Remove duplicates to get [0,0,1,1,2,3,3]. Two 0s, two 1s, one 2, two 3s - all ≤ 2 occurrences each.

Example 3 — No Excess Duplicates

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

› Output: 3

💡 Note: No element appears more than twice, so keep all elements. Return length 3.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array [1,1,1,2,2,3] with some elements appearing > 2 times

Process

Use two pointers to keep at most 2 of each element

Output

Return k=5, first 5 elements are [1,1,2,2,3]

Key Takeaway

🎯 Key Insight: Compare with element 2 positions back to naturally allow exactly 2 duplicates per unique value

Asked in

M Microsoft 25 a Amazon 20 f Facebook 15 G Google 12

The key insight is to use two pointers where we compare each element with the element 2 positions back in our result. This automatically ensures each unique element appears at most twice. Best approach is the two-pointer technique with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Optimal Solution	O(n)	O(1)	Use two pointers: one for writing position, one for reading. Compare with element 2 positions back.
Brute Force - Count Duplicates	O(n²)	O(1)	For each element, count how many times it appears before current position

Two Pointers - Optimal Solution — Algorithm Steps

Start with write pointer at index 2 (first 2 elements are always valid)
For each element from index 2, compare with element at write-2 position
If different, place current element at write position and increment write pointer
Return final write pointer position

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Write pointer starts at index 2, first 2 elements always kept

Compare

Compare current element with nums[write-2]

Decision

If different, place at write position and advance pointer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    if (numsSize <= 2) return numsSize;
    
    int write = 2; // Start from index 2
    
    for (int i = 2; i < numsSize; i++) {
        // If current element is different from element 2 positions back
        if (nums[i] != nums[write - 2]) {
            nums[write] = nums[i];
            write++;
        }
    }
    
    return write;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for array format [1,2,3]
    int nums[10000];
    int numsSize = 0;
    
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array with constant time operations

✓ Linear Growth

Space Complexity

O(1)

Only using a few pointer variables, modifying array in-place

✓ Linear Space

85.0K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers - Optimal Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler