Subarray Product Less Than K - Leetcode 713 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today it feels kind of weird saying that when you can actually see me I'm trying something new having like the face cam on let me know if you like it or if you dislike it so today let's solve subay product less than K we're given an integer array nums and an integer K we want to return the number of continuous subarrays such that the product of all the elements is strictly less than K so a pretty simple problem today at least in terms of the description now first things first focusing on this example here how many subarrays are in an input array about N squared we have n subarray starting at the beginning we have n minus one subarray starting at the second element etc etc so roughly n subarrays starting at each element therefore we get n s so that's a Brute Force solution for a medium problem usually brute force does not work so let's try to think about this can we do better in any possible way now when it comes to products let's think about what exactly a product is You' basically take elements and multiply them and then usually the number is bigger as a result and we're only dealing with integers here so theoretically if all of these integers are positive then as we add more elements the product should always increase and so that's kind of something that you should be asking yourself like is it more simple then we realize are we dealing with negative numbers or not they don't mention it up here they don't say every element in the array is positive so in a real interview that'd be kind of a clarifying question now if you go down if you scroll at the bottom of the problem description you will see that it says all elements are going to be positive so how does that help us can we use that to our advantage and I want you to know that my line of thinking for how to arrive at the solution might be different than yours but I'll just kind of quickly go through mine the reason I even paid attention to whether elements are positive or not is because if it's guaranteed that these elements are always positive then we can use a very simple and very fundamental algorithm that we've used a lot called the sliding window and let me tell you why we can do that it's a very common algorithm to take a Brute Force solution N2 and make it a linear time solution and so the idea is this these are our elements so we want to count all of the subarrays that satisfy the condition that start from this element so that's very easy to do like that's along the lines of the Brute Force solution right now we have 10 that's our product we add this our product is now 50 and so both of the sub Rays so far have met the condition they have been strictly less than 100 now we take two multiply it by that and that's going to be 100 it's not strictly less than that okay so if we were doing the Brute Force solution at this point now what we would do is say okay well adding positive elements is never going to make our product any smaller like multiplying more positive elements never going to make that smaller so now let's start here now let's start at five and then work our way and keep doing that but my observation here is that this looks like repeated work why take five and now multiply it by two and then you know keep doing that when in reality we could do something called two pointers we could have like at this point this is what our window was and now we know our product is too big we want to make it smaller how do we make it smaller well we've already counted all of the subarrays that start from this element so now let's do the same thing with the second element and by doing that what we're saying is shift this pointer over here and so our product which was 100 how do we do it we're we're not going to uh update the product by subtracting 10 from 100 we're going to divide 100 by 10 so basically reversing what we originally did so that will leave us with 10 which should be the product of our current subarray which it is so that's just basic math here so this is the idea behind this solution and in some cases it might not be that just shifting the pointer a single time will uh lower the product to make it lower than that threshold uh you can think of an example like this one suppose we had two 2 10 and then 10 here I think this product would be roughly 400 and then we would have to basically take our pointer here shift it by one then our product would be 200 then we'd have to shift the pointer one more time then our product uh would be 100 we'd still have to shift it actually we'd have to shift it three times in that case until our product is 10 because at that point it is less than 100 so instead of just having an if statement to shift this left pointer we're going to have a loop so that's a very important observation to make now lastly in terms of actually counting the subarrays it's not as straightforward as you would think because think about this let's quickly dry run through this let's say here this is one subay so our result is one now our product is 50 this is a second subarray now our product is going to be 100 and this subay did not count so now when we do take this uh left pointer and shift it over here our subay looks like this so the problem with this is that we kind of missed like when I originally said we have the pointer here we're going to count all sub Rays starting from this element that was actually not correct it's misleading with the Brute Force that's what we would have done but with the sliding window that's not what we're going to do we're going to take a shortcut we're going to do this because if you notice we kind of miss the subay that just included five we counted this subarray we counted this subarray and now we were trying to count this one but it's too big so we shifted our pointer and now we're at this subarray so we missed this one and it's a very easy thing to fix watch me do it we start here one subarray great we shift our right pointer over here now this is not one subay this is valid it's 50 the product is less than 100 therefore we actually found two sub Rays how do I know it's two because that's the length of this subay by introducing this five we introduced two subs let me show them to you five itself because if 10 * 5 is less than 100 of course five itself is all Al going to be less than 100 we know that that's guaranteed so by introducing five not only do we know 10 * 5 is less than 100 we know five is less than 100 as well now theoretically imagine our right pointer is here and let's just suppose for a second that K was actually 200 Now by introducing this two we introduced three new subarrays let me show them to you 2 itself 5 * 2 and 10 * 5 * 2 so that's the idea so in a way by taking this right pointer the right pointer actually tells us how many sub Rays how many valid sub rays are ending at this element so it's kind of the opposite of what I said originally so once you know this you've pretty much solved the problem every time we update our result we're going to add to the result the right pointer minus the left pointer + one that is the size of the window it's a linear time solution and no extra memory needed let's code it up so first things first I like to declare the result and that is what I'm going to be returning and then we're going to do our sliding window so left is going to be assigned to zero that's our left pointer we're going to have our right pointer as well but we're not going to declare that out there because we're going to just use that in a for Loop so it's going to iterate over the length of num so right is going to be incremented by one each time lastly let's actually declare a product now if we were not dealing with products if we were dealing with integers usually we would set this to zero but with products if it's set to zero any number multiplied by zero is always going to stay zero so we want to set this to a neutral value and one when it comes to multiplication is a neutral value any number multiplied by one is going to be that number so now let's update our product a um basically every time we see a new number so uh taking the number at the right pointer let's update our product and what we ultimately want to do is for every valid subarray we want to update the result and add to it the size of that subarray just like this taking the size right there but we can only do so if it's valid so before we do that let's make sure it's valid let's make sure the product is not greater than or equal to K so while the product is greater than or equal to K let's um update it so we will uh update our left pointer increment it by one before we update our left pointer let's get the value at that left pointer nums at left pointer and let's update our product so uh we can do that by taking the product and dividing it by that number you might think it's probably not possible for our left pointer to pass the right pointer but it actually is there are a few edge cases in this problem what if K is zero what if K is uh equal to some of the numbers within nums so we actually do need to check this let's make sure that left is less than or equal to right if it passes the right pointer then we will stop this Loop so this is the entire code let's run it to make sure that it works and as you can see on the left yes it does it's pretty efficient if you're preparing for coding interviews consider checking out n code. thanks for watching and I'll see you soon