Prefix Sum Problem List

One-dimensional Prefix Sum

LC 1749

Maximum absolute sum of any subarray: Find the minimum and maximum values in the prefix sum array, and the absolute difference between them is the answer.

1
2
3

def maxAbsoluteSum(self, nums: List[int]) -> int:
    s = list(accumulate(nums, initial=0))  # prefix sum of nums
    return max(s) - min(s)

2055. Plates Between Candles

1. Find the first candle at or to the right of a
2. Find the first candle at or to the left of b
3. Use prefix sum to count the number of plates between them

Steps 1 and 2 can use binary search, but it will time out. It’s best to pre-process and record the position of the first candle to the left/right of each position.

Prefix Sum and Hash Table

Enumerate the right, maintain the left. The key is to find the property of [maintain the left]!

1524. Number of Subarrays With Odd Sum

Utilize the property: odd-even=odd, even-odd=odd

2845. Count of Interesting Subarrays

Involves modulo. Modulo operation is closed under addition and subtraction!

LC 560

Input: nums = [1,2,3], k = 3 Output: 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def subarraySum(self, nums: List[int], k: int) -> int:
    res=0
    n=len(nums)
    s=[0]*(n+1)
    for i, x in enumerate(nums):
        s[i+1]=s[i]+x
    cnt=defaultdict(int)
    for sj in s:
        res+=cnt[sj-k]
        cnt[sj]+=1
    return res

3026. Maximum Good Subarray Sum

Good array: The absolute difference between the first and last numbers is 1.

Define a hash table minS, where the key is an element x in the array, and the value is the minimum prefix sum of all positions where x is located (excluding x itself).

1124. Longest Well-Performing Interval

We consider a day to be a “tiring day” when an employee works more than 8 hours. A “well-performing interval” means that during this period, the “number of tiring days” is strictly greater than the “number of non-tiring days”. Input: hours = [9,9,6,0,6,6,9] Output: 3 Explanation: The longest well-performing interval is [9,9,6].

3381. Maximum Element Sum of Subarrays Divisible by K

Return the maximum sum of a non-empty subarray in nums, such that the length of the subarray is divisible by k.

Modulo operation

2488

Median, converted to +1, -1 logic

Distance Sum

1685. Sum of Absolute Differences in a Sorted Array

Input: nums = [1,4,6,8,10] Output: [24,15,13,15,21]

Distance sum approach: Iterate to nums[i]=x, the sum of differences with numbers to its left is xi-preSum[i]; the sum of differences with numbers to its right is preSum[-1]-preSum[i+1]-x(n-i-1).

Can also be done with dynamic programming: Let s be the sum of distances from nums[i] to other numbers. Let nums[i+1]=nums[i]+d,

Then the sum of distances from nums[i+1] to other numbers is s+id-(n-i-2)d=s+d(2i+2-n).

XOR

1310. XOR Queries of a Subarray

XOR associativity

1177. Can Make Palindrome from Substring

How to quickly find the count of each letter in a substring? Odd/even property reminds us of XOR. 1^1=0, 0^1=1, so XORing with 1 can change odd/even.

Prefix Sum of Powers

2438. Range Product Queries of Powers

Two-dimensional Prefix Sum

1
2
3
4
5

m,n=len(matrix), len(matrix[0])
p=[[0]*(n+1) for _ in range(m+1)]
for i in range(m):
    for j in range(n):
        p[i+1][j+1]=p[i][j+1]+p[i+1][j]-p[i][j]+int(matrix[i][j])

221. Maximal Square

Given a 2D binary matrix filled with ‘0’s and ‘1’s, find the largest square containing only ‘1’s and return its area.