#80

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Remove Duplicates from Sorted Array II

Solve the problem of removing duplicates from a sorted array in-place, ensuring each element appears at most twice, using a two-pointer technique.

array two pointers

Problem Statement

Given an integer array nums sorted in non-decreasing order, you are tasked with removing some duplicates in-place. Each unique element should appear at most twice, and the relative order of elements should remain the same.

The challenge is to modify the array in-place. You are to return the new length k after removing duplicates. The first k elements of nums should contain the result, and it does not matter what elements are beyond the k-th position.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

int[] nums = [...]; // Input array int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }

Example 2

Input: nums = [1,1,1,2,2,3]

Output: 5, nums = [1,1,2,2,3,_]

Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Example 3

Input: nums = [0,0,1,1,1,1,2,3,3]

Output: 7, nums = [0,0,1,1,2,3,3,_,_]

Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.

Solution Approach

Two-pointer scanning with invariant tracking

This solution leverages the two-pointer technique, where one pointer traverses the array while the other tracks the position where the next unique element should go. As you traverse, you compare each element with the last valid element placed and ensure no more than two duplicates of any element are allowed.

In-place modification

The goal is to modify the array in-place, so no extra space should be used to store the results. The key is to update the elements directly within the given array using the two-pointer approach. This ensures the result is placed in the first k positions of the array.

Edge case handling

You must account for edge cases such as an array with no duplicates or an array where all elements are the same. In these cases, the solution should still work without errors and return the correct length k.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n) since each element is visited at most once, where n is the length of the input array. The space complexity is O(1) because the solution modifies the array in-place without requiring additional space.

What Interviewers Usually Probe

Understand the candidate's ability to handle array manipulation in-place.
Look for clarity in using the two-pointer approach and maintaining order without extra space.
Check if the candidate is mindful of edge cases, such as handling arrays with no duplicates or all duplicates.

Common Pitfalls or Variants

Common pitfalls

Incorrectly handling the array's length, returning an incorrect value for k.
Not managing the two-pointer correctly, resulting in array elements being overwritten prematurely.
Misunderstanding that the elements beyond the first k positions do not need to be handled.

Follow-up variants

Allowing elements to appear more than twice, which requires adjusting the comparison logic.
Modifying the input array to return k but allowing the rest of the array to remain unchanged.
Solving the problem using a different technique, such as a hash set or direct indexing.

FAQ

What is the two-pointer technique in this problem?

The two-pointer technique involves using two indices to traverse the array: one for scanning and the other for tracking the position to place unique elements.

How does the solution handle edge cases?

The solution accounts for edge cases such as arrays with no duplicates or arrays where all elements are the same by ensuring the two-pointer logic doesn't fail or result in errors.

Why is it important to modify the array in-place?

Modifying the array in-place ensures that the space complexity remains O(1) and the result is stored directly in the given array, as required by the problem constraints.

Can the array length vary? How does this affect the solution?

Yes, the array length can vary. The solution is designed to handle arrays up to 30,000 elements, making it efficient and scalable for large inputs.

What are common mistakes when implementing the two-pointer technique?

Common mistakes include incorrectly managing the pointers, not handling the edge cases properly, or failing to ensure the in-place modification is achieved without additional memory usage.

terminal

Solution

Solution 1: Single Pass

We use a variable $k$ to record the current length of the array that has been processed. Initially, $k=0$, representing an empty array.

1

2

3

4

5

6

7

8

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = 0
        for x in nums:
            if k < 2 or x != nums[k - 2]:
                nums[k] = x
                k += 1
        return k

Continue Practicing

#75 sort colors #88 merge sorted array #42 trapping rain water