How to Solve: Remove Duplicates from Sorted Array

How to Solve: Remove Duplicates from Sorted Array

(A Complete FAANG-Level Interview Guide)

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you prove you can write clean, in-place algorithms while handling edge cases like a pro."

? WHAT YOU NEED TO KNOW FIRST

Before diving in, ensure you understand: 1. Two-pointer technique (fast & slow pointers) 2. In-place array modification (avoiding extra space) 3. Time/space complexity trade-offs (O(1) space vs. O(n) space)

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every "Remove Duplicates" problem)

1. Check edge cases (empty array, single-element array).
2. Initialize two pointers (slow=0, fast=1).
3. Iterate with fast (traverse the array).
4. Compare nums[fast] with nums[slow]:
5. If different, increment slow and copy nums[fast] to nums[slow].
6. If same, skip (duplicate found).
7. Return slow + 1 (new length of unique elements).
8. Verify correctness (test with [1,1,2], [0,0,1,1,1,2,2,3,3,4]).

? WORKED EXAMPLES

Example 1 – Basic (LeetCode 26)

Problem: Remove duplicates from a sorted array in-place. Return the new length.

Solution (Python):

def removeDuplicates(nums):

    if not nums:

        return 0

    slow = 0

    for fast in range(1, len(nums)):

        if nums[fast] != nums[slow]:

            slow += 1

            nums[slow] = nums[fast]

    return slow + 1

Time Complexity: O(n) (single pass) Space Complexity: O(1) (in-place)

Why this works: - slow tracks the last unique element. - fast scans for new unique elements. - Copying nums[fast] to nums[slow+1] ensures uniqueness.

Example 2 – Medium (LeetCode 80)

Problem: Remove duplicates so that each element appears at most twice.

Solution (Python):

def removeDuplicates(nums):

    if len(nums) <= 2:

        return len(nums)

    slow = 2

    for fast in range(2, len(nums)):

        if nums[fast] != nums[slow - 2]:

            nums[slow] = nums[fast]

            slow += 1

    return slow

Time Complexity: O(n) Space Complexity: O(1)

Why this works: - slow starts at 2 (allowing two duplicates). - Compare nums[fast] with nums[slow-2] (not slow-1). - Ensures no more than two duplicates.

Example 3 – Hard (Follow-up: General K Duplicates)

Problem: Remove duplicates so that each element appears at most K times.

Solution (Python):

def removeDuplicates(nums, k):

    if len(nums) <= k:

        return len(nums)

    slow = k

    for fast in range(k, len(nums)):

        if nums[fast] != nums[slow - k]:

            nums[slow] = nums[fast]

            slow += 1

    return slow

Time Complexity: O(n) Space Complexity: O(1)

Why this works: - slow starts at k (allowing k duplicates). - Compare nums[fast] with nums[slow - k] (not slow - 1). - Generalizes to any k.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. For Remove Duplicates from Sorted Array: 1. Edge cases first—empty array? Single element? Return early. 2. Two pointers—slow tracks unique elements, fast scans. 3. Compare nums[fast] with nums[slow]—if different, copy and increment slow. 4. Return slow + 1—that’s the new length. 5. For K duplicates, compare with nums[slow - k] instead of nums[slow - 1].

Practice these variations: - Basic (LeetCode 26) - At most two duplicates (LeetCode 80) - General K duplicates (follow-up)

You’ve got this—now go crush that interview! ?"

Final Notes

• Whiteboard-ready: Every step is actionable.
• Interview-proof: Handles edge cases, follow-ups, and traps.
• FAANG-level: Covers basic to advanced variations.

Next steps: Implement all three examples in your preferred language. Time yourself—aim for <5 minutes per problem. ?