Introduction

The Remove Duplicates from Sorted Array II problem involves removing extra duplicates from a sorted array such that each element appears at most twice.

Given a sorted array, modify  arr[] the array in-place so that:

  • each unique element appears at most two times
  • relative order remains same

Return the new length of the modified array.

This problem helps in understanding:

  • Two Pointer Technique
  • in-place modification
  • duplicate handling
  • optimized traversal logic

Example

Input: arr[] = [1,1,1,2,2,3]Output: [1,1,2,2,3]
New Length = 5
Explanation:
Element 1 appears three times.
Only two occurrences are kept.

Input: arr[] = [0,0,1,1,1,1,2,3,3]
Output: [0,0,1,1,2,3,3]
New Length = 7
Explanation:
Every element is allowed at most two occurrences.

Constraints

  1 <= n <= 3 * 10^4 -10^4 <= arr[i] <= 10^4    Array is sorted


Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Create a new array
  2. Track frequency manually
  3. Add elements only if frequency ≤ 2

This approach is easy to understand but uses extra space.

Steps

  1. Create result array.
  2. Traverse the array.
  3. Count frequency of current element.
  4. Add element only if count ≤ 2.
  5. Return modified array.

Dry Run

Input Array: [1,1,1,2,2,3]Traverse 1:
Count = 1
Add 1
Traverse next 1:
Count = 2
Add 1
Traverse next 1:
Count = 3
Skip element
Traverse 2:
Count = 1
Add 2
Traverse next 2:
Count = 2
Add 2
Traverse 3:
Add 3
Final Result:
[1,1,2,2,3]

Brute Force Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Each element is traversed once.

Space Complexity: O(n)
Explanation:
Extra result array is used.

Approach 2 : Optimized Solution (Two Pointer Technique)

Explanation

Since the array is sorted, duplicates appear together.

We use:

  • one pointer for traversal
  • one pointer for valid insertion

The idea is:

  • allow first two occurrences
  • skip remaining duplicates

This modifies the array in-place without extra space.

Steps

  1. If array size ≤ 2:
    • return array size
  2. Initialize:
    • index = 2
  3. Traverse array from index 2.
  4. Compare:
    • current element with element at index-2.
  5. If different:
    • place element at index
    • increment index
  6. Final index becomes new length.

Dry Run

Input Array: [1,1,1,2,2,3]Initially:index = 2Traverse third 1:
Compare with arr[index - 2]
1 == 1
Skip element
Traverse 2:
2 != 1
Place at index 2
Array:
[1,1,2,2,2,3]
index = 3
Traverse next 2:
2 != 1
Place at index 3
Array:
[1,1,2,2,2,3]
index = 4
Traverse 3:
3 != 2
Place at index 4
Final Array:
[1,1,2,2,3]
New Length = 5

Optimized Code

Complexity Analysis

Time Complexity: O(n)
Explanation:
Each element is processed once.

Space Complexity: O(n)
Explanation:
Array is modified in-place.

Edge Cases

  1. Array contains all same elements
  2. Array contains no duplicates
  3. Array size ≤ 2
  4. Large duplicate groups
  5. Negative numbers present

Why This Problem is Important

This problem helps in understanding:

  1. Two Pointer Technique
  2. In-place modification
  3. Duplicate handling
  4. Sorted array traversal
  5. Space optimization

It is one of the most important two pointer interview problems.

Real-World Applications

Duplicate filtering concepts are used in:

  1. Database systems
  2. Data cleaning pipelines
  3. Log processing systems
  4. Search engines
  5. Analytics platforms

Common Mistakes

  1. Incorrect pointer updates
  2. Wrong comparison index
  3. Modifying array incorrectly
  4. Forgetting sorted array property

Interview Tips

Interviewers often expect:

  1. O(n) solution
  2. O(1) extra space
  3. Proper two pointer explanation

Always explain why comparing with index-2 ensures at most two occurrences.

Related Questions

  1. Remove Duplicates from Sorted Array
  2. Two Sum
  3. Move Zeroes
  4. Container With Most Water
  5. Merge Sorted Arrays

Final Takeaway

The Remove Duplicates from Sorted Array II problem is a fundamental two pointer problem that teaches in-place modification and duplicate handling techniques. Understanding this problem builds a strong foundation for advanced array optimization and traversal interview problems.