Range Sum Query Immutable - Leetcode 303 - Python

[@cesarfa-b3t]

A trick I like to use for the prefix array is to subtract left and add nums[left] instead of going one position over so we don't have to worry about boundary check, for example: prefix[right] - prefix[left] + nums[left]

[@samcarter8828]

Nice trick

[@gradientO]

but that requires us to store the nums array. Using prefix array, we dont need that

[@tsunami8892]

also that can be - prefix[right] - (prefix[left - 1] || 0)

[@ChrisCox-wv7oo]

prefix[-1] returns the last element in Python

[@shavvasatya7131]

Great as usual.

[@flatmapper]

2:00 Why O(n^2)?
O(n^2) is the time complexity of finding pairs.
Intuitively the time complexity is greater to find every subarray

[@MsPokemonmaster145]

He is saying that the number of subarrays is O(n^2) (To be exact, n*(n-1)). You are right tho to find all sums it would take O(n^3).

[@sanooosai]

thank you

[@flatmapper]

Amazing!

[@MianyunNi]

what if left = 0, right = 0; -2 + (-2)

[@mehedihassan-pf6yh]

You wrote left > 0 then but as index , left can be 0 to indicate first index