Two PointersEasyO(n) time · O(1) space

Remove Duplicates

Mahabharata — The Pandava Spies — Eliminating Redundant Reports

एकं वाक्यं पुनः प्रोक्तं न करोति नवं फलम्। नूतनं ज्ञानमेवार्थं धारयेत् पण्डितो जनः॥

*A word spoken twice yields no new fruit. The wise retain only knowledge that is unique.*

The Story

Thirteen years had passed since the great dice game, and the Pandavas had vanished into exile. But Vidura, ever loyal, maintained a network of spies who sent reports of the brothers' whereabouts—reports that were carefully coded and sorted by urgency from 1 to 10.

One night, a messenger burst into Vidura's chamber. "Minister! A crisis! The scroll containing spy reports has been intercepted. We must transmit the unique intelligence to Kunti before dawn, but we cannot send duplicates—Duryodhana's men will recognize the pattern if we repeat any urgency level more than twice!"

Vidura unrolled the scroll. The urgency numbers were already sorted: [1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5]

"The rule," Vidura murmured. "Each urgency level may appear at most twice in our transmission. We must remove excess duplicates while preserving order."

A young spy suggested the obvious approach. "Minister, let me create a new scroll. I'll go through each report and copy it only if it hasn't appeared twice already. I'll need parchment to track counts..."

"We have no time for new scrolls, and no space for tracking tables," Vidura said sharply. "We must modify this scroll in place, and we must do it in a single pass."

He studied the sorted array. "The fact that it's sorted is our advantage. Duplicates cluster together. I need not track counts across the entire scroll—only compare with recently written values."

Vidura picked up two quills—one red, one black. "The red quill is my reader. It will scan every report. The black quill is my writer. It will mark where the next unique-enough value should be recorded."

He began: - Writer (w) points to position 2 (after accepting the first two 1s automatically) - Reader (r) starts at position 2

"For the first two positions, I accept whatever is there—we always allow at least two of anything. Now, from position 2 onward, my reader examines each value."

The reader found 1 at position 2. "I compare this with what the writer wrote two positions back: position 0 has 1. They match! This is a third 1—reject it."

The reader moved to position 3: value 2. "I compare with position 0 (writer-2): value 1. Different! Accept this 2. Write it at writer's position."

Vidura physically moved the value 2 to position 2 (the writer's position), then advanced the writer to position 3.

The process continued: - r=4 (value 2): compare with w-2=1 (value 1). Different. Accept. Write at w=3. w becomes 4. - r=5 (value 2): compare with w-2=2 (value 2). Same! This is a third 2—reject. - r=6 (value 3): compare with w-2=3 (value 2). Different. Accept. Write at w=4. w becomes 5. - r=7 (value 3): compare with w-2=4 (value 2). Different. Accept. Write at w=5. w becomes 6. - r=8 (value 4): compare with w-2=5 (value 3). Different. Accept. Write at w=6. w becomes 7. - r=9 (value 4): compare with w-2=6 (value 3). Different. Accept. Write at w=7. w becomes 8. - r=10 (value 4): compare with w-2=7 (value 4). Same! Third 4—reject. - r=11 (value 5): compare with w-2=8 (value 4). Different. Accept. Write at w=8. w becomes 9.

The final array: [1, 1, 2, 2, 3, 3, 4, 4, 5, -, -, -] The effective length: 9 (writer's position)

"The first w elements are our valid transmission," Vidura concluded. "Each urgency level appears at most twice. The extra elements beyond position w can be ignored."

The young spy was amazed. "You never looked back more than two positions. You needed no extra parchment. How?"

"Because the array is sorted," Vidura smiled. "If the current value equals the value two positions before the writer, it must be a third (or more) occurrence. All duplicates of a value cluster together in sorted order. I only need to check against the last two distinct-group values."

The transmission reached Kunti safely. And in the annals of spy craft, Vidura's technique was remembered: when removing duplicates beyond a threshold k from a sorted array, compare each new value with the value k positions behind the writer.

This is the Two Pointer technique for removing duplicates.

The Young Spy's First Instinct

Create a new array and a count map. Copy values only when count is below the threshold. This uses O(n) extra space.

java

public int removeDuplicatesBruteForce(int[] nums) {
    // Using extra space for result and counting
    List<Integer> result = new ArrayList<>();
    Map<Integer, Integer> count = new HashMap<>();
    
    for (int num : nums) {
        int currentCount = count.getOrDefault(num, 0);
        if (currentCount < 2) {  // Allow at most 2
            result.add(num);
            count.put(num, currentCount + 1);
        }
    }
    
    // Copy back to original
    for (int i = 0; i < result.size(); i++) {
        nums[i] = result.get(i);
    }
    return result.size();
}

Vidura's Wisdom

Vidura's insight: in a sorted array, duplicates are contiguous. The writer pointer marks where the next valid element should go. For each element, compare with the element `k` positions before the writer (where k is the max allowed duplicates). If different, write it; if same, skip it. For k=2 (allow at most 2 duplicates): compare `nums[reader]` with `nums[writer-2]`

java

public int removeDuplicates(int[] nums) {
    if (nums.length <= 2) return nums.length;
    
    // Writer starts at 2: first two elements always valid
    int w = 2;
    
    // Reader scans from position 2 onward
    for (int r = 2; r < nums.length; r++) {
        // Compare current with element 2 positions before writer
        // If different, this is at most the 2nd occurrence
        if (nums[r] != nums[w - 2]) {
            nums[w] = nums[r];  // Write it
            w++;                 // Advance writer
        }
        // If same as w-2, this is 3rd+ occurrence—skip
    }
    
    return w;  // New length of valid portion
}

// Test with Vidura's spy reports
public static void main(String[] args) {
    int[] reports = {1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 5};
    int newLength = new Solution().removeDuplicates(reports);
    System.out.println("Valid length: " + newLength);
    System.out.print("Reports: ");
    for (int i = 0; i < newLength; i++) {
        System.out.print(reports[i] + " ");
    }
    // Output: Valid length: 9
    // Reports: 1 1 2 2 3 3 4 4 5
}

Step-by-Step Walkthrough

Array: [0, 0, 1, 1, 1, 2, 2, 3, 3, 3]  (allow at most 2)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Initial: w=2 (first 2 elements always kept)
[0, 0, 1, 1, 1, 2, 2, 3, 3, 3]
       w  r

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
r=2: nums[2]=1, nums[w-2]=nums[0]=0
     1 != 0 → Accept! Write 1 at w=2, w becomes 3
[0, 0, 1, 1, 1, 2, 2, 3, 3, 3]
          w  r

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
r=3: nums[3]=1, nums[w-2]=nums[1]=0
     1 != 0 → Accept! Write 1 at w=3, w becomes 4
[0, 0, 1, 1, 1, 2, 2, 3, 3, 3]
             w  r

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
r=4: nums[4]=1, nums[w-2]=nums[2]=1
     1 == 1 → Skip! (third 1)
[0, 0, 1, 1, 1, 2, 2, 3, 3, 3]
             w     r

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
r=5: nums[5]=2, nums[w-2]=nums[2]=1
     2 != 1 → Accept! Write 2 at w=4, w becomes 5
[0, 0, 1, 1, 2, 2, 2, 3, 3, 3]
                w     r

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
r=6: nums[6]=2, nums[w-2]=nums[3]=1
     2 != 1 → Accept! Write 2 at w=5, w becomes 6
[0, 0, 1, 1, 2, 2, 2, 3, 3, 3]
                   w     r

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
r=7: nums[7]=3, nums[w-2]=nums[4]=2
     3 != 2 → Accept! Write 3 at w=6, w becomes 7
[0, 0, 1, 1, 2, 2, 3, 3, 3, 3]
                      w     r

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
r=8: nums[8]=3, nums[w-2]=nums[5]=2
     3 != 2 → Accept! Write 3 at w=7, w becomes 8
[0, 0, 1, 1, 2, 2, 3, 3, 3, 3]
                         w     r

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
r=9: nums[9]=3, nums[w-2]=nums[6]=3
     3 == 3 → Skip! (third 3)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Result: [0, 0, 1, 1, 2, 2, 3, 3, _, _]
   New length: 8

Deep Insight

**Why does this work?**

The invariant: at any point, `nums[0..w-1]` contains valid elements with each value appearing at most k times. The comparison `nums[r] != nums[w-k]` works because:

1. If `nums[r] != nums[w-k]`, then `nums[r]` is either a new value or has appeared fewer than k times in the valid portion 2. If `nums[r] == nums[w-k]`, since the array is sorted and `nums[w-k..w-1]` contains this value, we already have k occurrences

**Generalizing to k duplicates:** ```java if (nums.length <= k) return nums.length; int w = k; for (int r = k; r < nums.length; r++) { if (nums[r] != nums[w - k]) { nums[w++] = nums[r]; } } ```

**Edge cases:** - Length ≤ k: Return original length (all valid) - All same elements: Keep first k - All unique: Keep all - Empty array: Return 0

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n)	O(n)	HashMap/List uses extra memory proportional to input
Optimal	O(n)	O(1)	In-place modification, only two pointers needed

Pattern Recognition

✅ Sorted array with duplicates
✅ Remove/keep elements based on frequency threshold
✅ In-place modification required
✅ "Remove duplicates" or "at most k occurrences"

**LeetCode Trigger Phrases:**
→ "remove duplicates from sorted array"
→ "each element appears at most twice"
→ "modify array in-place"

Bhagavad Gita 2.66

नास्ति बुद्धिरयुक्तस्य न चायुक्तस्य भावना। न चाभावयतः शान्तिरशान्तस्य कुतः सुखम्॥

There is no wisdom for the uncontrolled, no contemplation for the undisciplined. Without contemplation, no peace; without peace, how can there be happiness?

Connection: The algorithm embodies discipline: the writer pointer accepts only what passes the test, rejecting excess duplicates without hesitation. Like a disciplined mind that retains valuable knowledge while discarding redundant thoughts, the algorithm maintains clarity through strict adherence to its rule: compare, decide, move forward.