Welcome back to Gyan Aangan! In our journey to conquer common coding interview questions, today we're tackling a fantastic problem from the Top Interview 150 list: LeetCode 80, "Remove Duplicates from Sorted Array II". This problem is a cornerstone of array manipulation and a perfect illustration of why understanding in-place algorithms is crucial.

The Challenge: Problem Statement

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

A key constraint is that you must do this by modifying the input array in-place with O(1) space complexity, meaning you cannot allocate a new array.

Source: LeetCode Problem Page

Solution 1: The Optimal Two-Pointer Approach

When faced with constraints like O(1) space complexity, the two-pointers technique is often the most effective tool in your arsenal. It allows for elegant array manipulation without needing extra memory.

Intuition & Approach

The core idea is to maintain two pointers. A "read" pointer, i, will scan through the array, while a "write" pointer, k, will lag behind, only moving when we find a valid element to place in the modified section of the array. This is a classic pattern for an in-place algorithm.

Since the problem allows each unique element to appear at most twice, we can automatically consider the first two elements valid. This insight allows us to initialize our write pointer k at index 2. Our read pointer i will also start at index 2.

For every element nums[i] that our read pointer encounters, we must decide if it's a valid placement. The logic is surprisingly simple: we compare nums[i] with the element at nums[k - 2]. This comparison is the heart of our solution.

• If nums[i] is different from nums[k - 2], it proves that we are not introducing a third consecutive duplicate. Therefore, nums[i] is a valid number to include in our result. We perform the write operation: nums[k] = nums[i], and then advance our write pointer: k++.

• If nums[i] is the same as nums[k - 2], it signals that nums[k-2], nums[k-1], and nums[i] are all identical. Including nums[i] would violate the "at most twice" rule. In this scenario, we do nothing but advance our read pointer i, effectively skipping the invalid element.

Let's trace this algorithm with nums = [1,1,1,2,2,3]:

1. Initialize k = 2. The array is conceptually [1, 1, ...].

2. i = 2: nums[i] (1) is compared to nums[k-2] (1). They are the same. We skip. k remains 2.

3. i = 3: nums[i] (2) is compared to nums[k-2] (1). They are different. We write nums[2] = 2 and increment k to 3. The array becomes [1, 1, 2, ...].

4. i = 4: nums[i] (2) is compared to nums[k-2] (1). They are different. We write nums[3] = 2 and increment k to 4. The array becomes [1, 1, 2, 2, ...].

5. i = 5: nums[i] (3) is compared to nums[k-2] (2). They are different. We write nums[4] = 3 and increment k to 5. The array becomes [1, 1, 2, 2, 3, ...].

The loop finishes. The final value of k is 5, which is the length of the resulting array.

Code in Python

This Python code provides a clean implementation of the two-pointers strategy.

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        # k is the write pointer, initialized to 2 because the first
        # two elements are always part of the valid result.
        k = 2
        
        # i is the read pointer, starting from the third element.
        for i in range(2, len(nums)):
            # This check is the core of the in-place algorithm.
            # It ensures we only add an element if it's not a third duplicate.
            if nums[i] != nums[k - 2]:
                nums[k] = nums[i]
                k += 1
                
        return k

Complexity Analysis

• Time Complexity: O(n), a single pass through the array is required.

• Space Complexity: O(1), the definition of a true in-place algorithm.

Alternative Solution: Using a HashMap

For the sake of thorough technical prep, let's consider another method. A HashMap (or a Python dictionary) can also solve this, though it won't meet the space constraint.

Approach

Iterate through the array, using a HashMap to track the frequency of each number. A write pointer k builds the result in-place. If the frequency of the current number is two or less, it's placed at nums[k].

Code in Python

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        count = {}
        k = 0
        
        for num in nums:
            count[num] = count.get(num, 0) + 1
            
            if count[num] <= 2:
                nums[k] = num
                k += 1
                
        return k

Complexity Analysis

• Time Complexity: O(n).

• Space Complexity: O(n), which is why this is not the optimal solution for this specific problem but is a valid approach for similar questions without memory constraints.

Conclusion: Key Takeaways for Your Technical Prep

Mastering the two-pointers technique is non-negotiable for anyone serious about passing coding interviews. This problem, Remove Duplicates from Sorted Array II, perfectly demonstrates its power in creating efficient, memory-saving in-place algorithms.

For a fantastic visual breakdown of this logic, we highly recommend the video explanation from the YouTube channel niits, which greatly informed this guide.

• Video Credit: Using Two Pointers + Coding Exercise by niits.

Keep practicing these fundamental data structures and algorithms patterns, and you'll be well-prepared for whatever comes your way. Happy coding!