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

Introduction

The “Remove Duplicates from Sorted Array” is a commonly asked interview question that tests your ability to manipulate arrays and solve problems efficiently. This question aims to assess your understanding of array manipulation, two-pointer technique, and algorithm optimization. In this tutorial, we will discuss the problem statement, explore the optimal approach, and provide a step-by-step solution using Java.

Problem Statement

Given a sorted array, your task is to remove the duplicate elements in-place and return the new length of the array. You should not use any extra space for another array; the solution should modify the original input array in-place and return the length of the modified array.

Here’s the method signature for the problem:

public int removeDuplicates(int[] nums)

Example

Input:

nums = [1, 1, 2]

Output:

Length = 2, nums = [1, 2]

Approach Overview

The key to solving this problem is the fact that the input array is sorted. This property allows us to compare adjacent elements to identify duplicates. Since we need to solve this problem in-place and return the new length, we can utilize a two-pointer approach.

The two pointers, slow and fast, will traverse the array simultaneously. The slow pointer will point to the last unique element found in the array, while the fast pointer will explore the array to find the next distinct element. Whenever the fast pointer encounters a different element from the one at the slow pointer, we update the slow pointer and replace its value with the value at the fast pointer. This effectively removes duplicates as we iterate through the array.

Step-by-Step Solution

Let’s implement the solution step by step:

1. Initialize two pointers, slow and fast, both starting at index 1. The slow pointer will be used to keep track of the last unique element, and the fast pointer will traverse the array.
2. Start a loop that runs until the fast pointer reaches the end of the array.
3. Inside the loop, compare the element at the fast pointer with the element at the slow pointer. If they are different, it means we have found a new unique element.
4. Increment the slow pointer by 1 and replace the value at the slow pointer with the value at the fast pointer.
5. Continue the loop until the fast pointer reaches the end of the array. The slow pointer now points to the last unique element, and the array from index 0 to slow contains the modified array without duplicates.
6. Return the value of slow + 1 as the new length of the modified array.

Java Code Implementation

Now let’s translate the approach into Java code:

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }

    int slow = 0;

    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }

    return slow + 1;
}

Complexity Analysis

The time complexity of this solution is O(n), where n is the number of elements in the input array. We only traverse the array once with two pointers, and each comparison and assignment operation takes constant time.

The space complexity is O(1) since we are modifying the input array in-place without using any extra space that scales with the input.

Testing the Solution

Let’s test the solution with some examples:

public static void main(String[] args) {
    Solution solution = new Solution();

    int[] nums1 = {1, 1, 2};
    System.out.println("Original array: " + Arrays.toString(nums1));
    int newLength1 = solution.removeDuplicates(nums1);
    System.out.println("New length: " + newLength1);
    System.out.println("Modified array: " + Arrays.toString(Arrays.copyOf(nums1, newLength1)));

    int[] nums2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
    System.out.println("Original array: " + Arrays.toString(nums2));
    int newLength2 = solution.removeDuplicates(nums2);
    System.out.println("New length: " + newLength2);
    System.out.println("Modified array: " + Arrays.toString(Arrays.copyOf(nums2, newLength2)));
}

Conclusion

In this tutorial, we discussed the “Remove Duplicates from Sorted Array” interview question and provided a comprehensive Java solution. We learned about the two-pointer technique, which is particularly useful when dealing with sorted arrays. By understanding the problem, breaking down the approach, and implementing the solution step by step, you can effectively solve this problem in interviews and improve your algorithmic problem-solving skills. Remember to consider both time and space complexities when analyzing and optimizing your solutions.