How to Solve Remove Duplicates from Sorted Array II

In this problem, you need to remove duplicates in a sorted array so that each unique element appears at most twice. Using the two-pointer technique, you can achieve this in-place and maintain the relative order. The challenge lies in tracking the elements without modifying the length of the array or affecting the order of the remaining elements.

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

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.

How GhostInterview Helps

• GhostInterview helps by providing a step-by-step breakdown of how to apply the two-pointer approach for in-place array manipulation.
• By simulating interview-style questions, GhostInterview can guide you through solving problems efficiently and avoiding common mistakes.
• The platform’s examples and explanations help clarify how to handle edge cases and improve your understanding of the in-place modification technique.

Topic Pages

• Array
• Two Pointers

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.