Remove Duplicates

Array, Two Pointers

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.

Solutions

The key to solving this problem is understanding that you’re working with a sorted array, which means all duplicates of a particular number are adjacent to each other. This property allows you to effectively remove duplicates by comparing each element with its next one. The in-place requirement means you should not use additional space proportional to the size of the input array. You can use a constant amount of extra space, though. The relative order of the elements should be kept the same, meaning that you should not sort the array or change the order of unique elements. Finally, you should return the number of unique elements after removing duplicates. The remaining elements of the array after the first k are not important.

Approach - Brute Force Technique

This approach uses a temporary array to store the unique elements from the original array. It iterates through the original array and checks if the current element is different from the next one. If it is, the current element is stored in the temporary array. After the iteration, the last element of the original array is also stored in the temporary array. Finally, the unique elements from the temporary array are copied back to the original array. The function returns the number of unique elements.

Steps

1. Empty Array Check: If the length of nums is 0, the method returns 0. This is because there are no elements to process in an empty array.

2. Temporary Array Initialization: A temporary array temp of the same length as nums is created. This array is used to store the unique elements from nums.

3. Variable Initialization: A variable j is initialized to 0. This variable is used as an index for the temp array.

4. Iteration Over nums: The method iterates over the nums array from the first element to the second last element. For each element at index i, it checks if it is different from the next element at index i + 1.

5. Storing Unique Elements: If the current element is different from the next one, it means that the current element is unique and it is stored in the temp array at index j. Then, j is incremented by 1.

6. Storing the Last Element: After the iteration, the last element of nums is stored in temp at index j, and j is incremented by 1. This is done because the last element is not checked in the iteration.

7. Copying Back to nums: The unique elements from temp are copied back to nums from index 0 to j - 1.

8. Return Value: The method returns j, which is the number of unique elements in nums.

public class Solution
{
    public int RemoveDuplicates(int[] nums)
    {
        if (nums.Length == 0) return 0;
        int[] temp = new int[nums.Length];
        int j = 0;
        for (int i = 0; i < nums.Length - 1; i++)
        {
            if (nums[i] != nums[i + 1])
            {
                temp[j++] = nums[i];
            }
        }
        temp[j++] = nums[nums.Length - 1];
        for (int i = 0; i < j; i++)
        {
            nums[i] = temp[i];
        }
        return j;
    }
}

Complexity

• Time complexity: O(N)

• Space complexity: O(N)

Approach - Two Pointers

This approach avoids the use of extra space by maintaining a pointer that keeps track of the position of the last unique element in the original array. It iterates through the original array and checks if the current element is different from the element at the pointer’s position. If it is, the pointer is moved one step forward and the current element is stored at the pointer’s position in the original array. The function returns the number of unique elements.

Steps

1. Check for Empty Array: The function first checks if the input array nums is empty. If it is, it immediately returns 0, as there are no elements and hence no duplicates.

2. Initialization: A variable i is initialized to 0. This variable will serve as a pointer to the last non-duplicate element in the array.

3. Iteration: The function then enters a loop that starts from the second element of the array (index 1) and goes up to the last element. The loop variable j serves as a pointer to the current element being checked.

4. Check for Duplicates: Inside the loop, the function checks if the current element nums[j] is different from the last non-duplicate element nums[i]. If it is, it means nums[j] is not a duplicate of the last non-duplicate element.

5. Update Non-Duplicate Element: If nums[j] is not a duplicate, the function increments i and updates nums[i] to nums[j]. This effectively moves the non-duplicate element to the next position in the array, right after the last non-duplicate element.

6. Return Result: After the loop finishes, the function returns i + 1, which is the number of non-duplicate elements in the array.

public class Solution
{
    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)

• Space complexity: O(1)