Tutorial: Remove Duplicates from Sorted Array II - Java Solution

In this tutorial, we will explore the “Remove Duplicates from Sorted Array II” interview question and provide a comprehensive Java solution. This question is a common problem in technical interviews and assesses your understanding of arrays, two-pointer techniques, and basic algorithmic thinking. We’ll break down the problem, discuss the approach, and then provide a step-by-step implementation using Java.

Problem Statement

Given a sorted array, you need to modify it so that duplicates are allowed at most twice, and return the new length of the modified array.

For example:
Given the sorted array nums = [1, 1, 1, 2, 2, 3],
Your function should return 5, with the first five elements of the modified array being [1, 1, 2, 2, 3]. It doesn’t matter what you leave beyond the returned length.

Approach

To solve this problem, we will use a two-pointer approach along with a counter to keep track of the number of occurrences of each element. Since the array is already sorted, duplicates will be adjacent to each other. We will iterate through the array, maintaining two pointers:

Slow Pointer (i): This pointer will be used to modify the array in-place. It will point to the last position where the element is allowed to appear.
Fast Pointer (j): This pointer will traverse the array to count the occurrences of each element.

We will also use a variable called count to keep track of the number of occurrences of the current element. Initially, count will be set to 1 since we have encountered the first occurrence of the element.

The basic idea of our approach is as follows:

For each element at index j, if it is equal to the previous element, we increment the count.
If the element at index j is not equal to the previous element, we reset the count to 1 since this is a new element.

Now, we have three cases to consider:

If count is less than or equal to 2, it means we can keep the element at the slow pointer’s position. We update the slow pointer’s position and copy the element.
If count is greater than 2, it means we have encountered a duplicate more than twice. In this case, we don’t copy the element and just move the fast pointer.
At the end of each iteration, we copy the last element encountered (if applicable) since the loop will exit before copying it.

The slow pointer’s position (i) at the end of the loop will give us the length of the modified array.

Java Implementation

public class RemoveDuplicatesFromSortedArrayII {
    public int removeDuplicates(int[] nums) {
        if (nums.length <= 2) {
            return nums.length;
        }

        int i = 2; // Slow pointer
        int count = 1; // Initialize count for the first element
        for (int j = 2; j < nums.length; j++) {
            if (nums[j] != nums[i - 1]) {
                count = 1; // Reset count for new element
            } else {
                count++; // Increment count for duplicate element
            }

            if (count <= 2) {
                nums[i] = nums[j]; // Copy element to slow pointer's position
                i++; // Move slow pointer
            }
        }

        return i; // Length of modified array
    }

    public static void main(String[] args) {
        RemoveDuplicatesFromSortedArrayII solution = new RemoveDuplicatesFromSortedArrayII();
        int[] nums = {1, 1, 1, 2, 2, 3};
        int newLength = solution.removeDuplicates(nums);
        System.out.println("Modified Array Length: " + newLength);
        System.out.print("Modified Array: ");
        for (int i = 0; i < newLength; i++) {
            System.out.print(nums[i] + " ");
        }
    }
}

Explanation

Let’s walk through the implementation step by step:

We start by checking if the length of the nums array is less than or equal to 2. If it is, there’s no need to perform any modifications, so we return the length as is.
We initialize the slow pointer i to 2 and the count variable to 1. This is because the first two elements can always appear twice in the modified array.
We loop through the array with the fast pointer j starting from 2 (since the first two elements are already allowed duplicates).
Inside the loop, we check if the element at index j is different from the element at index i - 1 (previous element in the modified array). If they are different, it means we have encountered a new element, so we reset the count to 1.
If the elements are the same, we increment the count to keep track of the number of occurrences of the current element.
We then check if the count is less than or equal to 2. If it is, we copy the element at index j to the slow pointer’s position (i) and increment the slow pointer i.
After the loop, the slow pointer i points to the last valid position in the modified array. The length of the modified array is equal to i, so we return it.
In the main method, we create an instance of RemoveDuplicatesFromSortedArrayII and test the solution with a sample input array. We print the modified array’s length and its elements.

Complexity Analysis

The time complexity of this solution is O(n), where n is the length of the input array. We traverse the array once, and each element is examined once.

The space complexity is O(1), as we are modifying the input array in-place and using a constant amount of extra space for variables (i, count, and j).

Conclusion

In this tutorial, we addressed the “Remove Duplicates from Sorted Array II” interview question and provided a detailed Java solution. We discussed the problem statement, devised an approach using a two-pointer technique, and implemented the solution step by step. Understanding the underlying principles of this question will not only help you in interviews but also improve your algorithmic problem-solving skills.

Tutorial: Remove Duplicates from Sorted Array II – Java Solution