Approach #1: Prefix Sum [Accepted]
Intuition and Algorithm
We need to quickly compute the sum of values to the left and the right of every index.
Let's say we knew S
as the sum of the numbers, and we are at index i
. If we knew the sum of numbers leftsum
that are to the left of index i
, then the other sum to the right of the index would just be S - nums[i] - leftsum
.
As such, we only need to know about leftsum
to check whether an index is a pivot index in constant time. Let's do that: as we iterate through candidate indexes i
, we will maintain the correct value of leftsum
.
Complexity Analysis
-
Time Complexity: , where is the length of
nums
. -
Space Complexity: , the space used by
leftsum
andS
.
Analysis written by: @awice.