Remove duplicates from sorted array (in-place)
1234567891011121314151617181920212223242526272829303132333435363738394041424344
import java.util.List;
class Main {
public static void main(String[] args) {
/**
* Problem: Remove duplicates from sorted array (in-place)
*
* Input: nums = [1, 1, 2, 2, 3, 4, 4]
* Output: 4 (and nums becomes [1, 2, 3, 4, _, _, _])
*/
int[] nums = {1, 1, 2, 2, 3, 4, 4};
// I need to remove duplicated elements and fill out the remaining slots
// I think we can use Two pointers in the same direction
// We need two pointers. One moving slow and pointing to the slow where
// we can put a non duplicated element
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) { // Time O(n)
if (nums[slow] != nums[fast]) {
slow++;
nums[slow] = nums[fast];
}
}
// Time complexity O(n)
// Space complexity O(1)
int amountUniqueElements = slow + 1;
System.out.println("Unique elements: " + amountUniqueElements);
System.out.println("nums after removing duplicates:" + nums);
// Also, we can use Java Stream to create a stream of Integers and then
// collecting them to a Set to remove duplicates. However, we will lose
// how many remaining slots we need to fill out with '_' character.
// Nonetheless, thinking carefully, I think having a Set we can not add
// more than one '_' character. That would require using another data
// structure such as List
}
}
Java
INFO