## 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:

- 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. - Start a loop that runs until the
`fast`

pointer reaches the end of the array. - 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. - Increment the
`slow`

pointer by 1 and replace the value at the`slow`

pointer with the value at the`fast`

pointer. - 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. - 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.