Remove Duplicates From Sorted Array | LeetCode in C#
Here's how I solved remove duplicates from sorted array LeetCode problem
Problem Description
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
numssuch that the firstkelements ofnumscontain the unique elements in the order they were present innumsinitially. The remaining elements ofnumsare not important as well as the size ofnums. - Return
k.
Custom Judge:
The judge will test your solution with the following code:
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert(k == expectedNums.length);
for (int i = 0; i < k; i++) {
assert(nums[i] == expectedNums[i]);
}If all assertions pass, then your solution will be accepted.
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] <= 100numsis sorted in non-decreasing order.
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.
- Initialize a variable
currentNumberto store the last added unique number. Set it to a value less than the smallest possible element (e.g.,int.MinValue). - Use an
indexvariable to track the position to insert the next unique number. Start with 0. - Iterate over each element in
nums.- If the current element
numis greater thancurrentNumber, it is a unique number not yet added. - Update
currentNumberwithnumand placenumat the currentindex. - Increment
indexto prepare for the next possible unique number.
- If the current element
- After processing,
indexwill be the count of unique numbers, and the firstindexelements innumswill 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.
