LeetCode : Count of Range Sum – Stokastik

LeetCode : Count of Range Sum – Stokastik

This one looks like a very simple problem at first glance but I found it to be quite tricky during implementation. The straightforward solution is to pre-compute the prefix sums S(i), i.e. the sum of all integers from 0 to i-th index for all possible i, and then compute all possible range sums S(i, j), which is the sum of all integers from index i to index j. This can be computed by the simple formula S(i, j) = S(j) - S(i-1). After we have obtained the sums S(i, j) for all pairs i, j (i <= j), we simply check whether S(i, j) lies within the [lower, upper] range. Since there are O(N²) number of pairs i, j and for each pair, the operation of computing the sum S(i, j) and checking if the sum lies within [lower, upper] is O(1), the run-time complexity of this approach is O(N²).

Read full article from LeetCode : Count of Range Sum – Stokastik