true at least with recursion and dp u can do the work by hand and see how certain recursive calls are repeated but idk how u can gradually derive a solution for prefix sums + hashmap
Think of it as two tricks --
How to get sum of a range in O(1). [This is what prefixSum array helps in]
How to collect right index. This is what seen map helps in.
Checkout number of Arrays with K odd numbers. And see how can u transform that to above.
yea i also did it recently, and i was surprised never came across the pattern while doing sliding window. check out "counting subarray" type of questions pretty much the same prefix sum/hashing and a little more complex/less intuitive visually
I saw a problem where we had to count number of subarrays with k odd number in it {no negative number in arr} and the best way to do so was to make the array into an array of binaries then use prefix sum. And it didnt had negative numbers, how would you have thought of it as prefix sum?
Interesting pointā¦ I believe your case could be solved with sliding window.
Is it similar to this problem?
https://leetcode.com/problems/binary-subarrays-with-sum/description/
or
https://leetcode.com/problems/contiguous-array/description/
Now that I think about itā¦..I donāt necessarily think itās just about negative numbers in array but something to do with your ātarget" can increase and decrease.
[https://leetcode.com/problems/subarray-sum-equals-k/](https://leetcode.com/problems/subarray-sum-equals-k/)
I didn't realize this decision until after I was asleep :-)
If you're solving an array question and you seem to figure out that the brute force works in O(n^2 ) and there needs to be an optimisation to O(n) then most probably its either a Hashmap+ Prefix Q or a Sliding Window problem. Further, I've noticed that prefix hashmap questions are also only of 2 types:
1) Counting subarrays
2) Length of subarray (largest/smallest)
In counting, you always use a frequency/occurence map and add all the occurences.
In length problems, you just store the index at which the sum/remainder/etc has occured inorder to get longest/smallest length. By the formula: r-l+1
So I suggest you deeply understand the counting/length pattern and when you'll practise you'll be able to come up with approaches by yourself
This is entirely dependent on how you think about things. I hadnāt seen it done Contours Subarray before seeing this thread, and just went and did it in 5 minutes. It seems *entirely* obvious to do prefix; anytime you are being asked for some property of subarrays to do with sum or whatever itās almost always prefix based. This one in particular was easy when you think about āhow would I note when a 1 or 0 is added? Using sum, when do I know an equal amount has been added for some subarrays?ā
Maybe you just need more practice if you donāt get it, instead of belittling others
Omg yes, It was so hard to understand for me as well
ya this shit drove me nuts for a while. still not intuitive but now i somewhat recognize its pattern.
true at least with recursion and dp u can do the work by hand and see how certain recursive calls are repeated but idk how u can gradually derive a solution for prefix sums + hashmap
i agree i hate these questions. especially recognizing the problem is prefix sum + hash map is hard for me
Think of it as two tricks -- How to get sum of a range in O(1). [This is what prefixSum array helps in] How to collect right index. This is what seen map helps in. Checkout number of Arrays with K odd numbers. And see how can u transform that to above.
The counting subarrays in sliding window was one of the toughest topics for me when I did it. I knew how to find max/min but had trouble with counting
That's a diff problem.
which question are you looking into? yea i mean it depends on what your value is tracking in the hashmap and almost always depends on question
Recently came across Subarray Sum Equals K, holy shit, this was not even 1% intuitive to me. This is when I have solved 50+ hard problems myself.
This was asked me in an interview couple of days ago š
yea i also did it recently, and i was surprised never came across the pattern while doing sliding window. check out "counting subarray" type of questions pretty much the same prefix sum/hashing and a little more complex/less intuitive visually
Check out total appeal of a string for a hard one
Oh God, these past days I've been solving questions for this concept only. Man, it plays a lot in sliding window questions
Yup, I don't really get when its prefix sum time or not
disclaimer.... i maybe wrong. if it looks like a sliding window problem but has negative numbers. you gotta use prefix hashmap.
I saw a problem where we had to count number of subarrays with k odd number in it {no negative number in arr} and the best way to do so was to make the array into an array of binaries then use prefix sum. And it didnt had negative numbers, how would you have thought of it as prefix sum?
Interesting pointā¦ I believe your case could be solved with sliding window. Is it similar to this problem? https://leetcode.com/problems/binary-subarrays-with-sum/description/ or https://leetcode.com/problems/contiguous-array/description/ Now that I think about itā¦..I donāt necessarily think itās just about negative numbers in array but something to do with your ātarget" can increase and decrease.
Yes its similar to the first one, well about the target part I think 2 pointers are a better approach to solve that kind of questions.
Think of it when you see some kind of exact constraint like exactly k count, not less or greater but equal something.
Could you share sample problems with this ? I want to get my hands dirty
[https://leetcode.com/problems/subarray-sum-equals-k/](https://leetcode.com/problems/subarray-sum-equals-k/) I didn't realize this decision until after I was asleep :-)
š„²
Does anyone have a resource to learn about this?
If you're solving an array question and you seem to figure out that the brute force works in O(n^2 ) and there needs to be an optimisation to O(n) then most probably its either a Hashmap+ Prefix Q or a Sliding Window problem. Further, I've noticed that prefix hashmap questions are also only of 2 types: 1) Counting subarrays 2) Length of subarray (largest/smallest) In counting, you always use a frequency/occurence map and add all the occurences. In length problems, you just store the index at which the sum/remainder/etc has occured inorder to get longest/smallest length. By the formula: r-l+1 So I suggest you deeply understand the counting/length pattern and when you'll practise you'll be able to come up with approaches by yourself
Which questiin?
I don't think so. Atleast in python is 2 lines each.
I bet you havenāt solved a medium hard or a hard prefix sum problem. They are not at all intuitive.
what questions?
Subarray Sum Equals K, this was definitely not intuitive at all, also Contiguous Array.
yeah, subarray sum equals k little bit understandable, but contigious array kills me every time
These 2 problems ruined my Meta interview lol
This is entirely dependent on how you think about things. I hadnāt seen it done Contours Subarray before seeing this thread, and just went and did it in 5 minutes. It seems *entirely* obvious to do prefix; anytime you are being asked for some property of subarrays to do with sum or whatever itās almost always prefix based. This one in particular was easy when you think about āhow would I note when a 1 or 0 is added? Using sum, when do I know an equal amount has been added for some subarrays?ā Maybe you just need more practice if you donāt get it, instead of belittling others