Contains Duplicate II - Leetcode 219 - Python

hey everyone welcome back and let's write some more neat code today so today let's solve the problem contains duplicate 2 we're given an integer array of nums and an integer K we want to return true if there are two distinct indices I and J such that the two values at those indices are equal and the absolute value difference between those indices is less than or equal to K now the most important thing to recognize here is that by this statement they mean that the size of the window between the two elements is less than or equal to K so take the first example we have 1 2 3 1 clearly we do have some duplicate values here 1 and 1 they are at different indices and the question is is the size of the window less than or equal to K well not exactly actually that's another Edge case that you have to keep track of when we have I and J pointing at the same value here what's the size of this window well it's one there's just a single element but what's the absolute value of the difference between those two indices 0us 0 that's going to equal 0 so this equation is off by one now what about this window from zero all the way to three it's of course of size four does it satisfy the absolute value well we take 3 - 0 that gives us 3 or we could have done the opposite and gotten the absolute abute value of 0 - 3 it would have equal 3 in the end anyway is this value less than or equal to K yes it is so this is a valid window so basically the problem is asking us can we find a valid window of size k + 1 such that there are duplicate values in that window well what's the easiest way to solve this problem well let's assume our K value in this case instead of being three it was actually one in that case we would want Windows of size two what would be the Brute Force way to solve this problem well just check every single window check this window are there any duplicates check this window are there any duplicates and keep doing that for every window what's the easiest way to identify duplicates usually a hash set or a hash map is pretty easy CU we can insert and look up values in constant time there's one slight Improvement here that we can make though instead of Brute Force checking every value in this window and then restarting over here and checking every value in this window and then restarting over here checking every value here we can use the sliding window technique which if you're familiar with it it's pretty obvious that it can be applied to this problem because this whole problem is about Windows so we would start our window like this we have one and two and then when we shift our window over here we keep this value in the window but we would remove this from our window and add this value to our window and check are there any duplicates here now and we would keep doing that until we got to the end of the array or that we did find duplicate values in which case all we have to do is return true we don't have to return the actual indices of those duplicates so doing it this way the time complexity will be o of n because we're using a sliding window we're never going to add the same element to the hash set more than once and the memory complexity for the hashset is going to be also o of n well actually it's more accurate to say o of K in this case where K I guess the max value it could be is n but o of K is probably more accurate here so now let's code it up so the first thing I'm going to do is initialize our window hash set this is going to keep track of all the values in our window we're going to have two pointers to Define our window we're going to have the left pointer which is going to start at the beginning and we're also going to have a right pointer but we don't need to initialize that because we can just use it in our looping here we're going to go through every position in the input array nums for every value at index R we're going to check has it already been added to our window if it has then that must mean we found a duplicate in which case we can just go ahead and return true otherwise we're going to go ahead and add that value to our window nums of R but remember the case as we shift we don't want our window to be greater than the I think it was k + one so before we even do this it's important that we make sure to do this before before we do it we have to check if our window is indeed too large which we could check by saying right minus left is greater than k then we know the window is too big because remember we know it's allowed to be less than or equal to K but if it's greater than k then that's a problem we have an invalid window in which case the easy thing to do is just to remove the leftmost value and also increment our left pointer and that's pretty much about it if we never end up returning true then out here we should probably return false and let's run the code to make sure that it works and as you can see yes it does and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out NE code. it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon