[Leetcode] Prefix Sum

Posted on | In , |

Prefix Sum problem

560. Subarray Sum Equals K

Leetcode: https://leetcode.com/problems/subarray-sum-equals-k/

[Solution]

  • Use a hashmap to store {curSum: frequency}
  • if sumB - sumA == k => nums[a:b]
  • Loop with num, find how many accumalated-sums before num plus k can reach to the total sum so far.

Time Complexity: O(n), Space Complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
def subarraySum(self, nums, k):
    sm = 0
    sums = collections.defaultdict(int)
    sums[0] = 1
    res = 0
    for num in nums:
        sm += num
        if sm - k in sums:
            res += sums[sm - k]
        sums[sm] += 1
    return res

238. Product of Array Except Self

Leetcode: https://leetcode.com/problems/product-of-array-except-self/

  • Setup a left-to-right culuculum 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        forward = [i for i in nums]
        backward = [i for i in nums]
        for i in range(1, len(nums)):
            forward[i] = forward[i - 1] * nums[i]
        for i in reversed(range(len(nums) - 1)):
            backward[i] = backward[i + 1] * nums[i]
        res = [0 for _ in range(len(nums))]
        for i in range(len(nums)):
            if i == 0:
                res[i] = backward[i + 1]
            elif i == len(nums) - 1:
                res[i] = forward[i - 1]
            else:
                res[i] = forward[i - 1] * backward[i + 1]
        return res

325. Maximum Size Subarray Sum Equals k

Leetcode: https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/

1
2
3
4
5
6
7
8
9
10
11
12
13
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
    sums = [i for i in nums]
    sumIndex = collections.defaultdict(int)
    res = 0
    sumIndex[0] = -1
    for i in range(len(nums)):
        if i > 0:
            sums[i] = sums[i - 1] + nums[i]
        if sums[i] - k in sumIndex:
            res = max(res, i - sumIndex[sums[i] - k])
        if sums[i] not in sumIndex:
            sumIndex[sums[i]] = i
    return res

525. Contiguous Array

Leetcode: https://leetcode.com/problems/contiguous-array/

Good explanation: https://leetcode.com/problems/contiguous-array/solutions/99655/python-o-n-solution-with-visual-explanation/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def findMaxLength(self, nums: List[int]) -> int:
    if len(nums) < 2:
        return 0
    cnt = 0
    d = collections.defaultdict(int)
    d[0] = -1
    res = 0
    for index, num in enumerate(nums):
        if num == 1:
            cnt += 1
        else:
            cnt -= 1
        if cnt in d:
            res = max(res, index - d[cnt])
        else:
            d[cnt] = index
    return res

974. Subarray Sums Divisible by K

Leetcode: https://leetcode.com/problems/subarray-sums-divisible-by-k/

1124. Longest Well-Performing Interval

Leetcode: https://leetcode.com/problems/longest-well-performing-interval/

A good video: https://www.youtube.com/watch?v=H76XMJmBfP0

Same as LC 560.

Note:

  • We keep a point, when we meet hour > 8, we +1 to the point, else we -1.
  • Besides the situation that whole array satisfies a valid interval, the longest subarray always happens when the point == 1 (If point > 1 you can always expand it leftwards or rightwards)
  • intervalSum = curSum - prevSum. We store the position of the first appearance of the previous sum in a dictionary, when we meet curSum - 1 in the dictionary, which means there exist a subarray between curSum and the prevSum so that the point == 1, we get the length of the subarray.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def longestWPI(self, hours):
    # looks like two pointers but actually not
    sm = 0
    res = 0
    d = collections.defaultdict(int)
    d[0] = -1
    for i, hour in enumerate(hours):
        if hour > 8:
            sm += 1
        else:
            sm -= 1
        if sm - 1 in d:
            res = max(res, i - d[sm - 1])
        if sm not in d:
            d[sm] = i
    if sm > 0:
        return len(hours)
    return res