Remove Duplicates from Sorted Array II

Problem Statement

Given an integer array nums sorted in non-decreasing order, modify it in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same. Then return the number of elements k.

Consider the number of elements of nums to be k. To get accepted, you need to do the following things:

1. Change the array nums such that the first k elements of nums contain the elements which appear at most twice.
2. The remaining elements of nums are not important as well as the size of nums.
3. Return k.

What to notice first

• The array is sorted, which means duplicates are always consecutive.
• Each element can appear at most 2 times, not removed entirely like in Problem 26.
• You must modify the array in-place without using extra space for a new array.
• Only the first k elements matter; the rest can contain anything.
• You return k, not the modified array.

Examples

Input	Output	Explanation
[1, 1, 1, 2, 2, 3]	5	Array becomes [1, 1, 2, 2, 3, _]. First 5 elements allow duplicates up to 2.
[0, 0, 1, 1, 1, 1, 2, 3, 3]	7	Array becomes [0, 0, 1, 1, 2, 3, 3, _, _]. Each unique value appears at most twice.

Constraints

• 1 <= nums.length <= 3 * 10^4
• -10^4 <= nums[i] <= 10^4
• nums is sorted in non-decreasing order.

Real-World Applications

Where this pattern appears

• Rate limiting — Allow each user to perform an action at most twice within a time window, in a pre-sorted log.
• Inventory management — Keep at most 2 units of duplicate items in a sorted warehouse manifest.
• Duplicate detection with tolerance — Allow up to 2 occurrences of sensor readings before flagging an anomaly in ordered data.
• Event deduplication — Process duplicate events but cap their count at 2 for cost reduction in stream processing.

Complexity Comparison

Approach	Time	Space	Modifies Array	Best When
Two Pointers with Counter	O(n)	O(1)	Yes	Tracking duplicate count explicitly — most intuitive
Simple Two Pointers	O(n)	O(1)	Yes	Compact solution — no explicit counter variable

Which approach should you learn first?

• Pick Two Pointers with Counter if you want explicit, easy-to-understand logic.
• Pick Simple Two Pointers if you prefer compact, clever indexing without a counter.

Intuitive

Two Pointers with Counter

O(n) time · O(1) space

Compact

Simple Two Pointers

O(n) time · O(1) space

Approach 1: Two Pointers with Counter

★ Recommended

Use two pointers and track the count of consecutive equal elements. Write an element to the result position if:

1. It’s the first element, or
2. It’s different from the previous element, or
3. It’s the same as the previous but we’ve only seen it once so far (count < 2)

The counter resets when we encounter a new element.

⏱ Time O(n) Single pass 💾 Space O(1) No extra space

Step-by-step Example

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

Step	i	nums[i]	count	Same as prev?	count < 2?	Action	k	Array State
Start	-	-	-	-	-	Initialize	0	[1, 1, 1, 2, 2, 3]
1	0	1	1	-	-	First element, write	1	[1, 1, 1, 2, 2, 3]
2	1	1	2	Yes	Yes	Write (count < 2)	2	[1, 1, 1, 2, 2, 3]
3	2	1	2	Yes	No	Skip (count = 2)	2	[1, 1, 1, 2, 2, 3]
4	3	2	1	No	-	New element, write	3	[1, 1, 2, 2, 2, 3]
5	4	2	2	Yes	Yes	Write (count < 2)	4	[1, 1, 2, 2, 2, 3]
6	5	3	1	No	-	New element, write	5	[1, 1, 2, 2, 3, 3]

Return k = 5, array first 5 elements: [1, 1, 2, 2, 3] ✓

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

Step	i	nums[i]	Action	k	Progress
Start	-	-	Initialize	0	Start with k=0
1	0	0	First element, write, count=1	1	[0, ...]
2	1	0	Same, count < 2, write, count=2	2	[0, 0, ...]
3	2	1	New element, write, count=1	3	[0, 0, 1, ...]
4	3	1	Same, count < 2, write, count=2	4	[0, 0, 1, 1, ...]
5	4	1	Same, count = 2, skip	4	No change
6	5	1	Same, count = 2, skip	4	No change
7	6	2	New element, write, count=1	5	[0, 0, 1, 1, 2, ...]
8	7	3	New element, write, count=1	6	[0, 0, 1, 1, 2, 3, ...]
9	8	3	Same, count < 2, write, count=2	7	[0, 0, 1, 1, 2, 3, 3, ...]

Return k = 7 ✓

Animated walkthrough

How the counter approach handles duplicates up to 2

Watch the counter track consecutive occurrences. When count reaches 2, we skip further duplicates. A new element resets the counter.

Back Autoplay Next Reset

Step 1 of 3

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function removeDuplicates(nums):
    if nums is empty:
        return 0

    k = 1
    count = 1
    for i from 1 to len(nums) - 1:
        if nums[i] != nums[i - 1]:
            count = 1
            nums[k] = nums[i]
            k = k + 1
        else if count < 2:
            count = count + 1
            nums[k] = nums[i]
            k = k + 1

    return k

Solution Code

Python

remove_duplicates_from_sorted_array_ii_counter.py

from typing import List


def removeDuplicates(nums: List[int]) -> int:
    """
    Two Pointers with Counter Approach
    Allow each element to appear at most twice using explicit count tracking.

    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    if not nums:
        return 0

    k = 1
    count = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:
            # New element encountered, reset counter
            count = 1
            nums[k] = nums[i]
            k += 1
        elif count < 2:
            # Same element but less than 2 occurrences, allow it
            count += 1
            nums[k] = nums[i]
            k += 1
        # else: count == 2, skip this duplicate

    return k


# Test cases
print(removeDuplicates([1, 1, 1, 2, 2, 3]))  # 5, nums = [1, 1, 2, 2, 3, _]
print(removeDuplicates([0, 0, 1, 1, 1, 1, 2, 3, 3]))  # 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]
print(removeDuplicates([1]))  # 1, nums = [1]
print(removeDuplicates([1, 2]))  # 2, nums = [1, 2]

C++

remove_duplicates_from_sorted_array_ii_counter.cpp

#include <vector>
#include <iostream>
using namespace std;

/*
Two Pointers with Counter Approach
Allow each element to appear at most twice using explicit count tracking.

Time Complexity: O(n)
Space Complexity: O(1)
*/
int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }

    int k = 1;
    int count = 1;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] != nums[i - 1]) {
            // New element encountered, reset counter
            count = 1;
            nums[k] = nums[i];
            k++;
        } else if (count < 2) {
            // Same element but less than 2 occurrences, allow it
            count++;
            nums[k] = nums[i];
            k++;
        }
        // else: count == 2, skip this duplicate
    }

    return k;
}

int main() {
    vector<int> nums1 = {1, 1, 1, 2, 2, 3};
    cout << removeDuplicates(nums1) << endl;  // 5, nums = [1, 1, 2, 2, 3, _]

    vector<int> nums2 = {0, 0, 1, 1, 1, 1, 2, 3, 3};
    cout << removeDuplicates(nums2) << endl;  // 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]

    vector<int> nums3 = {1};
    cout << removeDuplicates(nums3) << endl;  // 1, nums = [1]

    vector<int> nums4 = {1, 2};
    cout << removeDuplicates(nums4) << endl;  // 2, nums = [1, 2]

    return 0;
}

Java

remove_duplicates_from_sorted_array_ii_counter.java

/*
Two Pointers with Counter Approach
Allow each element to appear at most twice using explicit count tracking.

Time Complexity: O(n)
Space Complexity: O(1)
*/
public class RemoveDuplicatesFromSortedArrayIICounter {
    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int k = 1;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                // New element encountered, reset counter
                count = 1;
                nums[k] = nums[i];
                k++;
            } else if (count < 2) {
                // Same element but less than 2 occurrences, allow it
                count++;
                nums[k] = nums[i];
                k++;
            }
            // else: count == 2, skip this duplicate
        }

        return k;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 1, 1, 2, 2, 3};
        System.out.println(removeDuplicates(nums1));  // 5, nums = [1, 1, 2, 2, 3, _]

        int[] nums2 = {0, 0, 1, 1, 1, 1, 2, 3, 3};
        System.out.println(removeDuplicates(nums2));  // 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]

        int[] nums3 = {1};
        System.out.println(removeDuplicates(nums3));  // 1, nums = [1]

        int[] nums4 = {1, 2};
        System.out.println(removeDuplicates(nums4));  // 2, nums = [1, 2]
    }
}

JavaScript

remove_duplicates_from_sorted_array_ii_counter.js

/**
 * Two Pointers with Counter Approach
 * Allow each element to appear at most twice using explicit count tracking.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 *
 * @param {number[]} nums
 * @return {number}
 */
function removeDuplicates(nums) {
    if (nums.length === 0) {
        return 0;
    }

    let k = 1;
    let count = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] !== nums[i - 1]) {
            // New element encountered, reset counter
            count = 1;
            nums[k] = nums[i];
            k++;
        } else if (count < 2) {
            // Same element but less than 2 occurrences, allow it
            count++;
            nums[k] = nums[i];
            k++;
        }
        // else: count == 2, skip this duplicate
    }

    return k;
}

// Test cases
console.log(removeDuplicates([1, 1, 1, 2, 2, 3]));  // 5, nums = [1, 1, 2, 2, 3, _]
console.log(removeDuplicates([0, 0, 1, 1, 1, 1, 2, 3, 3]));  // 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]
console.log(removeDuplicates([1]));  // 1, nums = [1]
console.log(removeDuplicates([1, 2]));  // 2, nums = [1, 2]

Rust

remove_duplicates_from_sorted_array_ii_counter.rs

/*
Two Pointers with Counter Approach
Allow each element to appear at most twice using explicit count tracking.

Time Complexity: O(n)
Space Complexity: O(1)
*/
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
    if nums.is_empty() {
        return 0;
    }

    let mut k = 1;
    let mut count = 1;
    for i in 1..nums.len() {
        if nums[i] != nums[i - 1] {
            // New element encountered, reset counter
            count = 1;
            nums[k] = nums[i];
            k += 1;
        } else if count < 2 {
            // Same element but less than 2 occurrences, allow it
            count += 1;
            nums[k] = nums[i];
            k += 1;
        }
        // else: count == 2, skip this duplicate
    }

    k as i32
}

fn main() {
    let mut nums1 = vec![1, 1, 1, 2, 2, 3];
    println!("{}", remove_duplicates(&mut nums1));  // 5, nums = [1, 1, 2, 2, 3, _]

    let mut nums2 = vec![0, 0, 1, 1, 1, 1, 2, 3, 3];
    println!("{}", remove_duplicates(&mut nums2));  // 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]

    let mut nums3 = vec![1];
    println!("{}", remove_duplicates(&mut nums3));  // 1, nums = [1]

    let mut nums4 = vec![1, 2];
    println!("{}", remove_duplicates(&mut nums4));  // 2, nums = [1, 2]
}

Go

remove_duplicates_from_sorted_array_ii_counter.go

package main

import "fmt"

/*
Two Pointers with Counter Approach
Allow each element to appear at most twice using explicit count tracking.

Time Complexity: O(n)
Space Complexity: O(1)
*/
func removeDuplicates(nums []int) int {
  if len(nums) == 0 {
    return 0
  }

  k := 1
  count := 1
  for i := 1; i < len(nums); i++ {
    if nums[i] != nums[i-1] {
      // New element encountered, reset counter
      count = 1
      nums[k] = nums[i]
      k++
    } else if count < 2 {
      // Same element but less than 2 occurrences, allow it
      count++
      nums[k] = nums[i]
      k++
    }
    // else: count == 2, skip this duplicate
  }

  return k
}

func main() {
  nums1 := []int{1, 1, 1, 2, 2, 3}
  fmt.Println(removeDuplicates(nums1))  // 5, nums = [1, 1, 2, 2, 3, _]

  nums2 := []int{0, 0, 1, 1, 1, 1, 2, 3, 3}
  fmt.Println(removeDuplicates(nums2))  // 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]

  nums3 := []int{1}
  fmt.Println(removeDuplicates(nums3))  // 1, nums = [1]

  nums4 := []int{1, 2}
  fmt.Println(removeDuplicates(nums4))  // 2, nums = [1, 2]
}

Approach 2: Simple Two Pointers

✓ Simple

Instead of explicitly tracking a counter, use a clever indexing technique: only write an element if it differs from the element 2 positions before it (if it exists). This implicitly ensures at most 2 occurrences.

The key insight: nums[k - 2] is the element from 2 positions back in the result. If the current element is different from it, we can safely add it (ensuring at most 2 occurrences of any value).

⏱ Time O(n) Single pass 💾 Space O(1) No extra space

Step-by-step Example

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

Step	k	nums[k-2]	nums[i]	Different?	Action	Result
Start	0	-	-	-	Initialize	-
1	1	-	1	Always	Write first element	[1, ...]
2	2	-	1	Always	Write second element	[1, 1, ...]
3	2	1	1	No	Skip (already 2)	No change
4	3	1	2	Yes	Write	[1, 1, 2, ...]
5	4	1	2	Yes	Write	[1, 1, 2, 2, ...]
6	5	2	3	Yes	Write	[1, 1, 2, 2, 3, ...]

Return k = 5 ✓

Pseudocode

function removeDuplicates(nums):
    if nums is empty:
        return 0

    k = 0
    for i from 0 to len(nums) - 1:
        if k < 2 or nums[i] != nums[k - 2]:
            nums[k] = nums[i]
            k = k + 1

    return k

The condition k < 2 or nums[i] != nums[k - 2] means:

• Always write the first 2 elements (k < 2)
• For elements beyond that, write only if they differ from the element 2 positions back (nums[i] != nums[k - 2])

Solution Code

Python

remove_duplicates_from_sorted_array_ii_simple.py

from typing import List


def removeDuplicates(nums: List[int]) -> int:
    """
    Simple Two Pointers Approach
    Allow at most 2 occurrences by checking if current element differs from element 2 positions back.

    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    if not nums:
        return 0

    k = 0
    for i in range(len(nums)):
        # Always write first 2 elements, or if current differs from element 2 positions back
        if k < 2 or nums[i] != nums[k - 2]:
            nums[k] = nums[i]
            k += 1

    return k


# Test cases
print(removeDuplicates([1, 1, 1, 2, 2, 3]))  # 5, nums = [1, 1, 2, 2, 3, _]
print(removeDuplicates([0, 0, 1, 1, 1, 1, 2, 3, 3]))  # 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]
print(removeDuplicates([1]))  # 1, nums = [1]
print(removeDuplicates([1, 2]))  # 2, nums = [1, 2]

C++

remove_duplicates_from_sorted_array_ii_simple.cpp

#include <vector>
#include <iostream>
using namespace std;

/*
Simple Two Pointers Approach
Allow at most 2 occurrences by checking if current element differs from element 2 positions back.

Time Complexity: O(n)
Space Complexity: O(1)
*/
int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }

    int k = 0;
    for (int i = 0; i < nums.size(); i++) {
        // Always write first 2 elements, or if current differs from element 2 positions back
        if (k < 2 || nums[i] != nums[k - 2]) {
            nums[k] = nums[i];
            k++;
        }
    }

    return k;
}

int main() {
    vector<int> nums1 = {1, 1, 1, 2, 2, 3};
    cout << removeDuplicates(nums1) << endl;  // 5, nums = [1, 1, 2, 2, 3, _]

    vector<int> nums2 = {0, 0, 1, 1, 1, 1, 2, 3, 3};
    cout << removeDuplicates(nums2) << endl;  // 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]

    vector<int> nums3 = {1};
    cout << removeDuplicates(nums3) << endl;  // 1, nums = [1]

    vector<int> nums4 = {1, 2};
    cout << removeDuplicates(nums4) << endl;  // 2, nums = [1, 2]

    return 0;
}

Java

remove_duplicates_from_sorted_array_ii_simple.java

/*
Simple Two Pointers Approach
Allow at most 2 occurrences by checking if current element differs from element 2 positions back.

Time Complexity: O(n)
Space Complexity: O(1)
*/
public class RemoveDuplicatesFromSortedArrayIISimple {
    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            // Always write first 2 elements, or if current differs from element 2 positions back
            if (k < 2 || nums[i] != nums[k - 2]) {
                nums[k] = nums[i];
                k++;
            }
        }

        return k;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 1, 1, 2, 2, 3};
        System.out.println(removeDuplicates(nums1));  // 5, nums = [1, 1, 2, 2, 3, _]

        int[] nums2 = {0, 0, 1, 1, 1, 1, 2, 3, 3};
        System.out.println(removeDuplicates(nums2));  // 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]

        int[] nums3 = {1};
        System.out.println(removeDuplicates(nums3));  // 1, nums = [1]

        int[] nums4 = {1, 2};
        System.out.println(removeDuplicates(nums4));  // 2, nums = [1, 2]
    }
}

JavaScript

remove_duplicates_from_sorted_array_ii_simple.js

/**
 * Simple Two Pointers Approach
 * Allow at most 2 occurrences by checking if current element differs from element 2 positions back.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 *
 * @param {number[]} nums
 * @return {number}
 */
function removeDuplicates(nums) {
    if (nums.length === 0) {
        return 0;
    }

    let k = 0;
    for (let i = 0; i < nums.length; i++) {
        // Always write first 2 elements, or if current differs from element 2 positions back
        if (k < 2 || nums[i] !== nums[k - 2]) {
            nums[k] = nums[i];
            k++;
        }
    }

    return k;
}

// Test cases
console.log(removeDuplicates([1, 1, 1, 2, 2, 3]));  // 5, nums = [1, 1, 2, 2, 3, _]
console.log(removeDuplicates([0, 0, 1, 1, 1, 1, 2, 3, 3]));  // 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]
console.log(removeDuplicates([1]));  // 1, nums = [1]
console.log(removeDuplicates([1, 2]));  // 2, nums = [1, 2]

Rust

remove_duplicates_from_sorted_array_ii_simple.rs

/*
Simple Two Pointers Approach
Allow at most 2 occurrences by checking if current element differs from element 2 positions back.

Time Complexity: O(n)
Space Complexity: O(1)
*/
pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
    if nums.is_empty() {
        return 0;
    }

    let mut k = 0;
    for i in 0..nums.len() {
        // Always write first 2 elements, or if current differs from element 2 positions back
        if k < 2 || nums[i] != nums[k - 2] {
            nums[k] = nums[i];
            k += 1;
        }
    }

    k as i32
}

fn main() {
    let mut nums1 = vec![1, 1, 1, 2, 2, 3];
    println!("{}", remove_duplicates(&mut nums1));  // 5, nums = [1, 1, 2, 2, 3, _]

    let mut nums2 = vec![0, 0, 1, 1, 1, 1, 2, 3, 3];
    println!("{}", remove_duplicates(&mut nums2));  // 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]

    let mut nums3 = vec![1];
    println!("{}", remove_duplicates(&mut nums3));  // 1, nums = [1]

    let mut nums4 = vec![1, 2];
    println!("{}", remove_duplicates(&mut nums4));  // 2, nums = [1, 2]
}

Go

remove_duplicates_from_sorted_array_ii_simple.go

package main

import "fmt"

/*
Simple Two Pointers Approach
Allow at most 2 occurrences by checking if current element differs from element 2 positions back.

Time Complexity: O(n)
Space Complexity: O(1)
*/
func removeDuplicates(nums []int) int {
  if len(nums) == 0 {
    return 0
  }

  k := 0
  for i := 0; i < len(nums); i++ {
    // Always write first 2 elements, or if current differs from element 2 positions back
    if k < 2 || nums[i] != nums[k-2] {
      nums[k] = nums[i]
      k++
    }
  }

  return k
}

func main() {
  nums1 := []int{1, 1, 1, 2, 2, 3}
  fmt.Println(removeDuplicates(nums1))  // 5, nums = [1, 1, 2, 2, 3, _]

  nums2 := []int{0, 0, 1, 1, 1, 1, 2, 3, 3}
  fmt.Println(removeDuplicates(nums2))  // 7, nums = [0, 0, 1, 1, 2, 3, 3, _, _]

  nums3 := []int{1}
  fmt.Println(removeDuplicates(nums3))  // 1, nums = [1]

  nums4 := []int{1, 2}
  fmt.Println(removeDuplicates(nums4))  // 2, nums = [1, 2]
}

Approach 3: Optimized Two-Pointer

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

remove_duplicates_from_sorted_array_ii_optimized.py

"""
Solution for Remove Duplicates from Sorted Array II
"""

def solve():
    """Implementation for approach 3 of Remove Duplicates from Sorted Array II"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

remove_duplicates_from_sorted_array_ii_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Remove Duplicates from Sorted Array II
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

RemoveDuplicatesFromSortedArrayIiOptimized.java

/**
 * Solution for Remove Duplicates from Sorted Array II
 * Approach 3
 */
public class RemoveDuplicatesFromSortedArrayIiOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

remove_duplicates_from_sorted_array_ii_optimized.js

/**
 * Solution for Remove Duplicates from Sorted Array II
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

remove_duplicates_from_sorted_array_ii_optimized.rs

/// Solution for Remove Duplicates from Sorted Array II
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

remove_duplicates_from_sorted_array_ii_optimized.go

package main

import "fmt"

// Solution for Remove Duplicates from Sorted Array II
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Confusing with Problem 26. Problem 26 removes all duplicates. Problem 80 allows up to 2 occurrences. Don’t mix them up!
• Off-by-one errors in simple approach. When checking nums[k - 2], ensure k >= 2 first, or use k < 2 or to guard the check.
• Not resetting the counter. In the counter approach, reset count = 1 whenever you encounter a new element, not just incrementing it.
• Modifying the comparison order. Always compare with the previous element (or the element 2 back for the simple approach), not arbitrary indices.
• Forgetting the sorted property. The array is sorted, so duplicates are always consecutive. This is critical to both solutions.

Related Problems

• Remove Duplicates from Sorted Array ↗ Easy #26
• Remove Element ↗ Easy #27
• Search in Rotated Sorted Array II ↗ Medium #81
• Move Zeroes ↗ Easy #283

Interview Tips

Key trade-offs to discuss

• Why two pointers? Because the array is already sorted. Duplicates are consecutive, so we can make decisions on-the-fly without extra space.
• Counter vs. Index trick: The counter approach is explicit and easier to explain. The index trick (comparing with k - 2) is more elegant but requires clearer thinking. Practice both.
• Generalization: If the problem asked for “at most k occurrences,” you’d need the counter approach and adjust the limit.
• Edge cases: Single element (return 1), two elements (return 2), all same (return 2), all unique (return n).
• Follow-ups to expect:
  • “What if duplicates can appear up to k times?” (Generalize the counter approach)
  • “Can you do this recursively?” (You can, but iteration is cleaner)
  • “What if the array is unsorted?” (You’d need a hash map — O(n) space)

← Previous
#79 Word Search Next
#81 Search in Rotated Sorted Array II →