The link to the problem: https://leetcode.com/problems/remove-duplicates-from-sorted-array/
Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.
Constraints: Must modify the array in-place. i.e., space complexity should be O(1).
For example, for input nums = [1,2,2,3,3,3,5,5]
output is 4 when top 4 elements in nums will be [1,2,3,5] Thoughts:
I found that we can use 2 pointers to solve most of the questions that require to do in-place. One pointer traverses the array slower than the other one.
Code Logic:
I have two pointers, i and j.
- Pointer j is the fast pointer that will traverse the whole array.
- Pointer i points at the previous element that we have checked. (we can also say that i always points to the last element of the “non-duplicated array”)
Hence, we keep moving j forward, if nums[j] doesn’t equal the one we just checked (i.e., nums[i]), we can assign this value to the next position of i (i.e., nums[i+1])
The strategy will be we keep overwriting nums[i] since only the original duplicated values will be overwritten.
For example, nums = [1,2,2]
i = 0 j = 0: since nums[j]==nums[i], do nothing. move j forward i = 0 j = 1: nums[j]!= nums[i], so we assign nums[j] to nums[i+1]
nums = [1,2,2]. move both i and j forwardi = 1 j = 2: nums[j]==nums[i], do nothing. (nums = [1,2,2])move j forwardi = 1 j = 3: the loop is terminated result will return i+1 since we need to return the length of the result arr, not the index.
Below is the 0ms code that beats 100%:
public int removeDuplicates(int[] nums) {
if(nums.length<=1)
return nums.length;
int count = 0;
int i = 0, j = 0;
int n = nums.length;
while(j<n)
{
if(nums[j]!=nums[i])
nums[++i] = nums[j];
j++;
}
return i+1;
}Time complexity: O(n)
Space complexity: O(1) ✌️
