CSES - Subarray Sums II - Time Complexity

Problems and Contests
#1

Hello,

Find the number of subarrays that sum up to x given the size of the array and its elements.

As mentioned here the time complexity is O(NLogN). Is that because of the usage of map, cause if that’s the case why can’t we use unordered_map and get the complexity to O(N).

Also I tried it with unordered_map on CSES and a couple of cases timed out. map works fine.
Am I missing something here.

Thanks

#2

I don’t really think so. Unordered_map is weird, and it sometimes may cause problems.

For

Find the number of subarrays that sum up to x given the size of the array and its elements.

This can be done by using prefix sum. Find the prefix sum of the given array and iterate to select the left bound of the sub arrays. Then the sum of array is equal to p[r]-p[l-1]=x where l is constant.

This means p[r]=p[l-1]+x.

Use a balanced BST/Hash to make the queries, remember to delete them (I think) which make sure that there is no problem.

#3

unordered_map has a bad constant factor if it uses a bad hash function

see

#4

Well, if it’s a bad hash function, then it’s no longer just a constant factor.

1 Like