Leetcode — 26. Remove Duplicates from Sorted Array

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 forward
i = 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) ✌️

Click here to view all the stories posted on this blog: https://anj910.medium.com/bookmark-c95e4c52cf44

More from Anj

Click here to view all the stories posted on this blog: https://anj910.medium.com/bookmark-c95e4c52cf44