Remove Duplicates from Sorted Array II - Leetcode 80 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
9:30 - Coding Explanation

leetcode 80

#neetcode #leetcode #python

[factified]

To all those who are just starting their coding journey, you might not understand the code sometimes or even the question. But, that is completely fine. Just stick with it since you have chosen this journey with a purpose and have patience, which in my opinion, is the most important that a programmer must have. Be patient, give yourself time and practice whenever you can.

[jamshedkarimnazarov]

This solution is kind of a tricky one. I wouldn't be able to come up with this on my own, but yes once you explained it, it makes sense.

[crikxouba]

Even when explained to me as clearly as this, I always find these loops and pointers a complete mind f**k

[Dannyboyjr]

I feel like ChatGPT's answer is easier to understand on this one.

def removeDuplicates(self, nums: List[int]) -> int:

left = 2

if len(nums) <= 2: return len(nums) #This line of code isn't necessary for passing the leetcode problem but is still a good check

for right in range(2, len(nums)):
if nums[right] != nums[left - 2]:
nums[left] = nums[right]
left += 1

return left

[sergiofranklin]

def removeDuplicates(self, nums):
j, count = 1, 1

for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
count += 1
else:
count = 1

if count <= 2:
nums[j] = nums[i]
j += 1

return j

[janki-bxrn]

Way easier solution from ChatGPT, easy to understand and much more intuitive

class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) <= 2:
return len(nums)

# Initialize the two pointers.
write_index = 2 # Start from the third position.
for i in range(2, len(nums)):
# Only write the element if it is not the same as the element two positions back.
if nums[i] != nums[write_index - 2]:
nums[write_index] = nums[i]
write_index += 1

return write_index

[RuslanZinovyev]

There is a way simpler solution and more intuitive from my perspective, I can't say that your explanation was really helpful this time, but I really appreciate what you are doing for us.

def removeDuplicates(nums: List[int]) -> int:
if len(nums) <= 2:
return len(nums)
l = 2
for r in range(2, len(nums)):
if nums[r] != nums[l - 2]:
nums[l] = nums[r]
l += 1
return l

[parthphalke]

Thank you for your efforts for the fellow community !🤟

[EjazAhmed-pftz]

Thank you so much sir, but could you please combine videos in a playlist so that will be easy for us to follow

[shaguntripathi]

In the Constraints:
1 <= nums.length <= 3 * 104
We should consider the test case having len(nums)<=2, in this case we should return the len(nums) itself.

[kaytim]

An alternative solution building off of the Remove Duplicates from Sorted Array I solution:

class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
left = 1
freq = 1

for i in range(1, len(nums)):
if nums[i] > nums[left - 1]:
nums[left] = nums[i]
left += 1
freq = 1
elif nums[i] == nums[left - 1] and freq < 2:
nums[left] = nums[i]
left += 1
freq += 1

return left

Instead of nested loops I added a var that keeps track of how many times a value is added and an elif that adds up to two of a given value.

[uptwist]

Thanks for the solution. Very easy to follow and reason.

[vigneshs]

The fact i can write the solution with O(n^2) but still here to optimize the solution...Thank you bro

[dash]

Love your videos, they are very insightful and helpful. I'm very greatful for you.
I would like this time to share my solution to it, as for the first time ever it has a cleaner approach.
Same idea with L and R pointers. with each iteration replace L with R, then check if L is valid, as follows:

class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
l = 2
for r in range(2, len(nums)):
nums[l] = nums[r]

if nums[l] != nums[l - 2]:
l += 1

return l

[pul]

simpler version:

function removeDuplicates(nums: number[]): number {

// edge case to return early if 2 or fewer elements
if (nums.length <= 2) return nums.length;

let j = 1; // start from the second element

for(let i = 2; i < nums.length; i++){
// if the current element doesn't equal the element at j-1 (two places behind),
// it means we have found a place where a duplicate can be allowed
if(nums[i] !== nums[j-1]) {
j++;
nums[j] = nums[i]
}
}

// Since j represents the _index_ of the last element in the "no more than 2 duplicates array, " we add 1 to get the number of values
return j + 1;
};

[simsekcool]

I found it easier to use a set to solve this question and the first version of this question as well. I just check if the element we are currently at is already in both sets. If its in neither or in just one of the sets, then I added it to the other set and I swap the element at r and the element at i. But if the element is already in both sets, then I only increment r and don't do any swapping. Here is the code:
sett1= set()
sett2= set()
i = 0
for r in range(len(nums)):
if nums[r] not in sett2:
if nums[r] not in sett1:
#case where its not in either set
sett1.add(nums[r])
nums[i], nums[r] = nums[r], nums[i]
i+=1
else:
#case where its not in set 2 but its in set1
sett2.add(nums[r])
nums[i], nums[r] = nums[r], nums[i]
i+=1
#case where its in both sets
return i

[Jaeoh.woof]

My solution is very similar to the 1st version of the problem but with a slight twist.
Runtime beats 98%

def removeDuplicates(self, nums: List[int]) -> int:
l = 2
flag = 0
for r in range(2, len(nums)):
if nums[r] != nums[r-2-flag]:
nums[l] = nums[r]
l +=1
else:
flag +=1
return l

[omar-eocq]

you make this question hard, you can make it easier by starting left and right from index 2 and if(nums[right ]!==nums[left -2]){
nums[left ]=nums[right ]; we increment left ++ otherwise right ++, finally return left

[lmbzkxq]

For those, who want a more stricter solution.

The relative order is not preserved in this solution, if there are 4 3's [2, 3, 3, 3, 3], we should consider the relative ordering where the first two 3's are considered, but the your solution kinda considers the last occurence of 3.

[shyamsudheer]

at 0.55 why is it better to shift the value to the end instead of popping because both have time complexity of O(n)?