Remove Duplicates From Sorted Array-Leetcode 26 Solution

The “Remove Duplicates from Sorted Array” problem is a classic exercise on LeetCode that tests your ability to manipulate arrays efficiently. The task involves removing duplicate elements from a sorted array and returning the length of the modified array without using extra space for another array.

This guide explores multiple approaches, from naive to optimal, with Java code examples.

Problem Statement for Remove Duplicates From Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

Naive Approach for Remove Duplicates From Sorted Array: Using Extra Space

This approach creates a temporary array to store unique elements. While it works, it does not satisfy the in-place requirement.

Algorithm

1. Traverse the input array.
2. Add unique elements to a temporary array.
3. Copy the elements back to the original array.

Code

public int removeDuplicatesNaive(int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;

    int[] temp = new int[n];
    int j = 0;

    for (int i = 0; i < n - 1; i++) {
        if (nums[i] != nums[i + 1]) {
            temp[j++] = nums[i];
        }
    }
    temp[j++] = nums[n - 1];

    // Copy back to the original array
    for (int i = 0; i < j; i++) {
        nums[i] = temp[i];
    }

    return j;
}

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n) (Extra space for temporary array)

Two-Pointer Approach: Optimal Solution for Remove Duplicates From Sorted Array

The optimal solution involves using two pointers to manipulate the array in-place.

Algorithm

1. Use one pointer (i) to track the position of unique elements.
2. Traverse the array with another pointer (j).
3. When a new unique element is encountered, update the array at position i.

Code

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

    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

Complexity

• Time Complexity: O(n) (Single pass through the array)
• Space Complexity: O(1) (In-place solution)

Explanation with Example

Given nums = [1, 1, 2, 3, 3, 4]:

1. Initial State:
   • i = 0, nums[i] = 1
2. Iterate:
   • At j = 2, nums[j] = 2, update nums[++i] = nums[j].
   • At j = 3, nums[j] = 3, update nums[++i] = nums[j].
   • At j = 5, nums[j] = 4, update nums[++i] = nums[j].
3. Final State:
   • nums = [1, 2, 3, 4, ...], return i + 1 = 4.

Using HashSet:

Using a HashSet to remove duplicates is not optimal for this specific problem because the input array is sorted, and the task requires in-place modifications. However, it can still be a valid approach for general cases when the input array is not necessarily sorted.

Here’s how you can solve this using a HashSet:

Algorithm

1. Initialize a HashSet to store unique elements.
2. Traverse the input array, and add each element to the HashSet.
3. Overwrite the input array with elements from the HashSet in sorted order (if necessary).

Code

import java.util.HashSet;

public class RemoveDuplicatesUsingHashSet {
    public int removeDuplicates(int[] nums) {
        HashSet<Integer> set = new HashSet<>();

        // Add all elements to the HashSet
        for (int num : nums) {
            set.add(num);
        }

        // Overwrite the input array with unique elements
        int i = 0;
        for (int num : set) {
            nums[i++] = num;
        }

        return set.size();
    }
}

Complexity

• Time Complexity:
  • Adding to a HashSet takes O(1) on average for each element. For n elements: O(n).
  • Iterating through the HashSet to copy back takes O(k), where k is the number of unique elements.
  • Total: O(n).
• Space Complexity: O(n) (Space for the HashSet).

Key Notes

• The HashSet approach is useful when the input is not sorted, as it automatically handles duplicate removal.
• For this specific problem, the two-pointer method remains more efficient due to its O(1) space complexity requirement.

For sorted input arrays, using a HashSet introduces unnecessary overhead because sorting is already guaranteed, which is why it’s better suited for cases where the input isn’t sorted.

Comparison of Approaches

Summary

The Two-Pointer Approach is the recommended solution due to its efficiency and compliance with the in-place modification constraint. The naive approach is educational for understanding the problem but not practical for larger inputs.