26. Remove Duplicates From Sorted Array | LeetCode in C#

This post is a journal about how I solved the Remove Duplicates from Sorted Array problem from LeetCode.

Intuition

The problem requires us to remove duplicates from a sorted array in-place while maintaining the original order of elements. Since the array is sorted, duplicates are consecutive. This means we can efficiently identify and skip duplicates by comparing each element to the last unique element identified.

Approach

The key is to keep track of the position at which the next unique element should be placed. We start with an index pointing to the first position. As we iterate through the array, we compare each element with the last unique element found. If an element is greater than this last unique element, it means we have encountered a new unique number. We then place this new unique element at the current index and increment the index.

1. Initialize a variable currentNumber to store the last added unique number. Set it to a value less than the smallest possible element (e.g., int.MinValue).
2. Use an index variable to track the position to insert the next unique number. Start with 0.
3. Iterate over each element in nums.
   • If the current element num is greater than currentNumber, it is a unique number not yet added.
   • Update currentNumber with num and place num at the current index.
   • Increment index to prepare for the next possible unique number.
4. After processing, index will be the count of unique numbers, and the first index elements in nums will be the unique elements.

Complexity

• Time complexity: The algorithm iterates through the array once, making the time complexity (O(n)) where (n) is the length of the array.

• Space complexity: The algorithm uses a constant amount of extra space, so the space complexity is (O(1)).

Code

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        var currentNumber = int.MinValue;
        var index = 0;

        foreach(var num in nums){
            if(num > currentNumber)
            {
                currentNumber = num;
                nums[index++] = currentNumber;
            }
        }

        return index;
    }
}

Video

Conclusion

With this approach, we efficiently remove duplicates in-place resulting in the desired number of unique elements at the beginning of the array without using any additional space beyond a few variables.

References

• Remove Duplicates from Sorted Array - LeetCode