Number of Zero-Filled Subarrays - Leetcode 2348 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem number of zero filled sub arrays we're given an integer array of nums and we want to return the number of sub-arrays filled with zero so given this subarray we can see that we have these two zeros over here and these two zeros over here so you might think well does that mean we have two sub arrays filled with zeros that's what I thought at first but actually when you think about it more closely these are two sub rays but within each of these we have this subarray with just a single zero and we have this sub Ray with just a single zero and we have this subarray and this subarray so it's true that we will need to find like these consecutive zeros but just because there are two zeros and that's like a single sub Ray that can actually be broken up into two more sub arrays of size one so in total we have six subarrays this counts as three sub arrays of zeros and this counts as three as well add those together we have a total of six in other words we have four sub arrays of size one and we have two sub arrays of size two so I'm gonna work our way backwards from this problem because once you kind of see this where your mind might first go is by just getting every contiguous subarray suppose these two like we count the number of sub arrays and we also have the length so we have two sub rays of length two let's say this is the length and this is the count and we know that each sub array of length two actually counts as three sub arrays of zero so we could basically do this and when we have this calculation after we've iterated through the entire array then we would take this count two and multiply it by three now what if we had some sub arrays of length one like we have three sub Rays maybe of length one suppose maybe like this one didn't exist this this one didn't exist and there was like a zero over here that's an example would be well a sub Ray of just one zero just counts as a single subarray what about if we have three consecutive zeros how many sub arrays would that be well sub rays of length one there would be three of them sub rays of length two there would be two of them one over here and one over here and sub rays of length three there's one of them so in total we counted six sub arrays when we have three consecutive zeros what about when we have four consecutive zeros well one two three four five six seven eight nine and then ten is just the entire one so we have ten when we have four consecutive zeros so this is kind of one way we could do it we could get every sub array get the length of it and then map it to how many we ended up getting and then using that like let's say we had one subarray of length four so we would have like a mapping like this and we know sub arrays of length four actually have 10 zero filled subarrays this is a valid way to solve this problem but let me show you a pattern because there's definitely a pattern here when we have a single zero that's one subarray when we have two zeros that's three sub Rays when we have three zeros that's six when we have four zeros that's ten notice what's happening here when we go down here we're doing a plus two when we go down here we're doing a plus three when we go down here we're doing a plus four and I can tell you that this pattern is going to repeat when we go down again we're gonna do plus five so we're noticing a pattern here how can we use it to our advantage well before I tell you that let me tell you why I know for sure that this is the pattern it actually makes a lot of sense when you think about it take a look at this when we have a single zero that's just one subarray when we add another zero here this it's self this new zero is a sub array and these two zeros are also a subarray that's why we do plus two using this new zero it's a part of two sub arrays this and this and same exact thing with this third zero when we introduce it it's a part of three sub arrays because that's the number of zeros that are like that's a total number of contiguous zeros we have now we have one subarray two sub arrays and three sub arrays including this zero we already knew we had a bunch of sub arrays here but we're not counting these because we already had those zeros by introducing another zero this zero is a part of three new sub arrays same thing with this fourth one this is a subarray that we just introduced this is a subarray we introduced this is a subarray we introduced and this is a subarray that we introduced I know I'm repeating myself a lot but I bet this makes a ton of sense to you now why this pattern is how it is so using this idea we can actually solve this problem by iterating through the array just a single time and we don't need any extra memory let me show you how I'm gonna do that we're gonna have a pointer I we're gonna iterate through every position we don't care about anything that's not a zero of course so when we get to this position we don't care just skip it when we get here it's not a zero just skip it when we get here we found a zero so what we're gonna do is well this itself is a sub array so we're going to take our result and it was initially zero but we're going to add one to it we're also going to keep track of the length of how many consecutive zeros that we're seeing because now when we shift our pointer over here now we're at the second zero since this is the second zero you tell me how many new sub arrays does the this zero introduced to just itself that's one subarray and this itself because we know there was a previous zero because we're keeping track of how many consecutive zeros we have well let's say we'll keep track of that in our account variable initially it was one now we're at two there's two so this number the number of consecutive zeros is what we're going to be adding to our result every time so now we're going to say one plus two is the result so let me just clean this up a bit our total result is three we already visited this we already visited this and now we get to a non-zero so we're going to take our account which was previously set to two but now we're going to reset it down to zero because this is not a zero so our consecutive zeros is going to be reset so we skip this guy but now we see another zero so we're going to take our count of zeros and now increment it now it's going to be set to one it's over here so we're going to take this one add it to our result three plus one and we're going to shift our pointer from here over here again it's once again a zero so we're going to take our count and add one to it because now we have two consecutive zeros so now our count is going to be two and this two value is what we're going to add to our result so now our result is three plus one plus two which is going to be a total of six then we're going to iterate again to this last position it's a four though so we're going to take our count and reset it back down to zero zero added to the result is not going to do anything so you can kind of see how we're going to probably code this up but now we're done with the array our result is six and that's what we're going to return if we ended up having a streak of maybe three consecutive zeros we would have basically done the same thing just kept incrementing our account and then taking that value and adding it to our result but you can see that this algorithm is clearly Big O of n no extra memory so the memory is bigger of one now let's code it up there's multiple ways to code this up so I will show you two of them one that kind of comes natural to me where we have a pointer and our result I'm going to initialize these both to zero and then we're just going to iterate while our pointer is in bounds of the array we're going to have our count which is going to count the number of consecutive zeros I'm going to initialize it to zero and then I'm going to have a nested Loop so while our pointer is in bounds because we definitely don't want it to go out of bounds and while the value that we're currently at num at index I is equal to zero while that's the case we're going to be incrementing our count and shifting our pointer and adding that count to the result now if we don't encounter any zeros we would still want to increment our eye pointer so I'm going to do that out here and if we did end up encountering some zeros well this would either leave off out of bounds because we visited every value or it would end at a non-zero value so it would be okay to increment our pointer out here and after for that we can just go ahead and return our result so I'll run this to make sure that it works and as you can see it does I'll quickly show you another way to code this up I prefer this way even though it's slightly more code but let me show you the other way it's using a for Loop so we don't need our eye pointer we have our result we're going to set it to zero and we would have actually our count variable and declare it outside of the loop so this count is basically going to represent the exact same thing it's just that we're going to have it out of the scope of the while loop you'll see why in just a second but here we're actually not going to have a while loop I misspoke we're going to have our for Loop in range of the length of the nums array I'm not sure what's going on with leak code syntax highlighting but I think our code is correct so I'll continue so there's two possibilities either the value at index I is equal to zero or it's not equal to zero if it is equal to zero then we want to increment our count by one so I'll do that if it's not equal to zero then we're going to reset our count to zero maybe it's already equal to zero but it does no harm to us to set it to zero again and lastly we always want to take the count and add it to the result because either it's going to be equal to zero in which case this won't do anything or it's going to tell us how many consecutive zeros we have seen and in that case we would want to add those to the result so you can see that this does work out in both cases it's just for me that this is like a less natural solution but if you prefer it that's perfectly fine let's run it to make sure that it works now as you can see yes it does I guess it's a bit more efficient but the Big O time complexity is the same if this was helpful please like And subscribe if you're preparing for coding interviews check out neatcode.io it has a ton of free resources to help you prepare thanks for watching and I'll see you soon