Tutorial: Remove Duplicates from Sorted Array II Interview Question and Solution in Python

In this tutorial, we will dive into the “Remove Duplicates from Sorted Array II” interview question. This question is commonly encountered in technical interviews, especially for positions related to software development and data analysis. We will provide a detailed explanation of the problem, discuss the thought process behind solving it, and present a Python solution. By the end of this tutorial, you should have a solid understanding of how to approach and solve this problem efficiently.

Problem Statement

Given a sorted array, you need to modify the array in-place such that duplicates are allowed at most twice, and any additional duplicates beyond the second occurrence are removed. The resulting array should be modified in-place and you should return the length of the modified array.

Example

Input:

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

Output:

Modified array: [1, 1, 2, 2, 3]
Modified array length: 5

Constraints

• The input array is sorted in non-decreasing order.
• You must modify the array in-place and return the length of the modified array.
• It is not necessary to maintain the elements beyond the modified length.

Approach

To solve this problem, we need to keep track of the frequency of each element while iterating through the sorted array. Since duplicates are allowed at most twice, we can allow the first two occurrences of a duplicate element, but any additional occurrences should be removed. We will use two pointers and an additional variable to achieve this.

Here’s a step-by-step breakdown of the approach:

1. Initialize two pointers, slow and fast, both starting at index 2 (since we are allowed at most two duplicates).
2. Initialize a variable count to keep track of the count of duplicates for the current element.
3. Iterate through the array using the fast pointer, starting from index 2.
4. Compare the element at the fast pointer with the element two positions before the slow pointer (to account for the first two allowed duplicates).
5. If the elements at both pointers are the same, increment the count variable.
6. If the elements are different, reset the count to 1.
7. If the count is less than or equal to 2, update the element at the slow pointer with the element at the fast pointer.
8. Increment both pointers, slow and fast.
9. Return the value of the slow pointer as the length of the modified array.

Python Solution

Now that we understand the approach, let’s implement it in Python:

def removeDuplicates(nums):
    if len(nums) <= 2:
        return len(nums)

    slow = 2
    count = 1

    for fast in range(2, len(nums)):
        if nums[fast] == nums[slow - 2]:
            count += 1
        else:
            count = 1

        if count <= 2:
            nums[slow] = nums[fast]
            slow += 1

    return slow

Explanation

1. We start by handling the edge case where the length of the input array is less than or equal to 2. In such cases, there is no need to perform any modifications, and we simply return the length of the array.
2. Initialize the slow pointer to 2. This pointer will be used to keep track of the position where the next non-duplicate element should be placed.
3. Initialize the count variable to 1. This will keep track of the number of occurrences of the current element.
4. Iterate through the array using the fast pointer, starting from index 2. We start from index 2 because the first two elements are allowed to have duplicates.
5. Compare the element at the fast pointer with the element two positions before the slow pointer. This comparison checks for duplicates beyond the second occurrence.
6. If the elements at both pointers are the same, increment the count variable. This indicates that we have found another occurrence of the same element.
7. If the elements are different, reset the count to 1. This means we have encountered a new element, so we reset the count to track its occurrences.
8. If the count is less than or equal to 2, update the element at the slow pointer with the element at the fast pointer. This ensures that we keep only the first two occurrences of the duplicate element.
9. Increment both pointers, slow and fast, to continue processing the array.
10. Finally, return the value of the slow pointer as the length of the modified array. The array is modified in-place up to the slow pointer’s position.

Complexity Analysis

• Time Complexity: The solution processes each element in the input array exactly once. Therefore, the time complexity of this solution is O(n), where n is the length of the input array.
• Space Complexity: The solution uses a constant amount of extra space, regardless of the size of the input array. Hence, the space complexity is O(1).

Testing the Solution

Let’s test the solution with some sample inputs to ensure that it works as expected:

# Test case 1
nums1 = [1, 1, 1, 2, 2, 3]
print("Input:", nums1)
length = removeDuplicates(nums1)
print("Modified array:", nums1[:length])
print("Modified array length:", length)
print()

# Test case 2
nums2 = [0, 0, 1, 1, 1, 1, 2, 3, 3]
print("Input:", nums2)
length = removeDuplicates(nums2)
print("Modified array:", nums2[:length])
print("Modified array length:", length)

Conclusion

In this tutorial, we explored the “Remove Duplicates from Sorted Array II” interview question. We discussed the problem statement, developed an approach to solve it, and provided a detailed Python solution. We also analyzed the time and space complexity of the solution. By following the step-by-step approach outlined in this tutorial, you should be well-equipped to tackle similar problems involving duplicate removal and array manipulation in interviews or coding challenges.