Solving the LeetCode "Remove Duplicates from Sorted Array II" Problem in Go

Difficulty: Medium | Tags: Array, Two Pointers

Introduction

This problem requires modifying a sorted array in-place to remove duplicates such that each unique element appears at most twice. The challenge lies in achieving this efficiently without using extra space.

Problem Analysis

Given a sorted array, we need to ensure no element appears more than twice while maintaining the relative order. The solution must work in-place with O(1) space complexity. For example, the input [1,1,1,2,2,3] should become [1,1,2,2,3,_], returning 5.

Solution Approach

We use a two-pointer technique where one pointer (slow) tracks the position to place the next valid element, and another pointer (fast) iterates through the array. We allow at most two duplicates by comparing elements at the current and previous positions.

Go Implementation

func removeDuplicates(nums []int) int {
    if len(nums) <= 2 {
        return len(nums)
    }
    slow := 2
    for fast := 2; fast < len(nums); fast++ {
        if nums[fast] != nums[slow-2] {
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}

Complexity Analysis

Time Complexity: O(n) - We traverse the array once with the fast pointer.
Space Complexity: O(1) - No additional space is used beyond a few variables.

Testing and Examples

Test Case 1: Input [1,1,1,2,2,3] → Output 5, nums becomes [1,1,2,2,3,_]
Test Case 2: Input [0,0,1,1,1,1,2,3,3] → Output 7, nums becomes [0,0,1,1,2,3,3,_,_]

Best Practices and Tips

1. Always handle edge cases where the array length is ≤ 2.
2. Use two pointers to efficiently manage in-place modifications.
3. Ensure the solution works for the maximum constraint (3 * 10^4 elements).