> For the complete documentation index, see [llms.txt](https://howardyangemail.gitbook.io/decode-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://howardyangemail.gitbook.io/decode-leetcode/array/prefixsum.md).

# PrefixSum

437\. Path Sum III

#### [53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)

Maintain a local max and global max, update the max with current value (starting a new array) or max + current value (continuous array).

*T: O(n)  S: O(1)*

```java
    public int maxSubArray(int[] nums) {
        int max = nums[0], curtmax = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curtmax = Math.max(curtmax + nums[i], nums[i]);
            max = Math.max(max, curtmax);
        }
        return max;
    }
```

**Solution 2:** [**Divide and Conquer**](/decode-leetcode/array/sort.md#53-maximum-subarray)

**Solution 3: DP**

```python
def maxSubArray(self, nums: List[int]) -> int:
    dp = [0 for i in range(len(nums))]
    dp[0] = nums[0]
    maxx = nums[0]
    for i in range(1, len(nums)):
        dp[i] = max(dp[i - 1] + nums[i], nums[i])
        maxx = max(dp[i], maxx)
    return maxx
```

#### [560. Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/)

Use prefix sum and store the count of sum in a hashmap. When `map.containsKey(sum - k)`, it indicates that there is a subarray sum which equals k, add it to the result.

Add a record to map (`map.put(0, 1)`), this give the count between any number 0, in case that number equals k.

*T: O(n)  S: O(n)*

```java
public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int sum = 0, result = 0;
    for (int n : nums) {
        sum += n;
        if (map.containsKey(sum - k)) {
            result += map.get(sum - k);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return result;
}
```

#### [1477. Find Two Non-overlapping Sub-arrays Each With Target Sum](https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/)

Addition to LC560, store the minimum subarray lens before i which sums to target in a `min` array. When the previous minimum `prevMin` exists, it means there is a subarray sums to `sum - target`.  That lens is `i - prevMin`. The result is the current min and previous min, which is `i - prevMin + min[prevMin]`.

{% tabs %}
{% tab title="Java, clear HashMap" %}

```java
public int minSumOfLengths(int[] arr, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    int sum = 0;
    map.put(0, -1);
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
        map.put(sum, i);
    }
    sum = 0;
    int one = Integer.MAX_VALUE, res = Integer.MAX_VALUE;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
        if (map.containsKey(sum - target)) {
            one = Math.min(one, i - map.get(sum - target));
        }
        if (map.containsKey(sum + target) && one != Integer.MAX_VALUE) {
            res = Math.min(res, one + (map.get(sum + target) - i));
        }
    }
    return res == Integer.MAX_VALUE ? -1 : res;
}
```

{% endtab %}

{% tab title="Java" %}

```java
public int minSumOfLengths(int[] arr, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    int n = arr.length;
    int[] min = new int[n];
    Arrays.fill(min, Integer.MAX_VALUE);
    int sum = 0;
    int best = Integer.MAX_VALUE;
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        Integer prevMin = map.get(sum - target);
        if (prevMin != null) {
            if (prevMin != -1 && min[prevMin] != Integer.MAX_VALUE) {
                res = Math.min(res, i - prevMin + min[prevMin]);
            }
            best = Math.min(best, i - prevMin);
        }
        min[i] = best;
        map.put(sum, i);
    }
    return res == Integer.MAX_VALUE ? -1 : res;
}
```

{% endtab %}

{% tab title="Java (Sliding Window, no HashMap)" %}

```java
public int minSumOfLengths(int[] arr, int target) {
    int n = arr.length;
    int best[] = new int[n];
    Arrays.fill(best, Integer.MAX_VALUE);
    int sum = 0, start = 0, ans = Integer.MAX_VALUE, bestSoFar = Integer.MAX_VALUE;
    for(int i = 0; i < n; i++){
        sum += arr[i];
        while(sum > target){
            sum -= arr[start];
            start++;
        }
        if(sum == target){
            if(start > 0 && best[start - 1] != Integer.MAX_VALUE){
                ans = min(ans, best[start - 1] + i - start + 1);
            }
            bestSoFar = min(bestSoFar, i - start + 1);
        }
        best[i] = bestSoFar;
    }
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

```

{% endtab %}
{% endtabs %}

[**523. Continuous Subarray Sum**](https://leetcode.com/problems/continuous-subarray-sum/)

```java
public boolean checkSubarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (k != 0) sum %= k;
        if (map.containsKey(sum)) {
            if (map.get(sum) < i - 1) return true;
        } else {
            map.put(sum, i);
        }
    }
    return false;
}
```

#### [325. Maximum Size Subarray Sum Equals k](https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/)

[Prefix + HashMap and get the maximum interval.](https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/)

```java
public int maxSubArrayLen(int[] nums, int k) {
    if (nums == null || nums.length == 0) return 0;
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    int sum = 0, res = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (map.containsKey(sum - k)) {
            res = Math.max(res, i - map.get(sum - k)); 
        }
        if (!map.containsKey(sum)) map.put(sum, i);
    }
    return res;
}
```

#### [152. Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/)

Maintain both positive and negative values in two arrays, update with current min/max.&#x20;

```python
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
    _dict = {}
    _dict[0] = -1
    _sum = 0
    _min = sys.maxsize
    for i in range(len(nums)):
        _sum += nums[i]
        if _sum - k in _dict:
            _min = min(_min, i - _dict[_sum - k])
        if _sum not in _dict:
            _dict[_sum] = i
    return 0 if _min == sys.maxsize else _min
```

```java
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] pos = new int[n];
        int[] neg = new int[n];
        int max = nums[0];
        pos[0] = neg[0] = nums[0];
        for (int i = 1; i < n; i++) {
            pos[i] = Math.max(Math.max(pos[i - 1] * nums[i], neg[i - 1] * nums[i]), 
                              nums[i]);
            neg[i] = Math.min(Math.min(pos[i - 1] * nums[i], neg[i - 1] * nums[i]),
                              nums[i]);
            max = Math.max(max, pos[i]);
        }
        return max;
    }
```

#### [1352. Product of the Last K Numbers](https://leetcode.com/problems/product-of-the-last-k-numbers/)

Maintain a prefix product. When encounter 0, reset the prefix product list.

*Add: T: O(1), GetProduct: T: O(1)*

{% tabs %}
{% tab title="Java" %}

```java
List<Integer> list;
public ProductOfNumbers() {
    list = new ArrayList<>();
    list.add(1);
}

public void add(int num) {
    if (num > 0) {
        list.add(list.get(list.size() - 1) * num);   
    } else {
        list = new ArrayList<>();
        list.add(1);
    }
}

public int getProduct(int k) {
    if (k >= list.size()) return 0;
    return list.get(list.size() - 1) / list.get(list.size() - k - 1);
}
```

{% endtab %}

{% tab title="TreeMap" %}

```java
List<Integer> list;
TreeMap<Integer, int[]> memo; // start : [end, product]
public ProductOfNumbers() {
    list = new ArrayList<>();
    memo = new TreeMap<>();
}

public void add(int num) {
    list.add(num);
}

public int getProduct(int k) {
    int endIndex = list.size() - 1;
    int startIndex = endIndex - k + 1;
    int product = 1;
    if (memo.containsKey(startIndex)) {
        int[] temp = memo.get(startIndex);
        int newend = temp[0];
        product *= temp[1] * getProductBetween(newend + 1, endIndex);
    } else if (memo.ceilingKey(startIndex) != null) {
        int ceil = memo.ceilingKey(startIndex);
        int[] temp = memo.get(ceil);
        int newend = temp[0];
        product *=  getProductBetween(startIndex, ceil - 1) * temp[1] * getProductBetween(newend + 1, endIndex);
    } else {
        product = getProductBetween(startIndex, endIndex);
    }
    memo.put(startIndex, new int[]{endIndex, product});
    return product;
}

private int getProductBetween(int start, int end) {
    int product = 1;
    for (int i = start; i <= end; i++) {
        product *= list.get(i);
    }
    return product;
}
```

{% endtab %}
{% endtabs %}

[974. Subarray Sums Divisible by K](https://leetcode.com/problems/subarray-sums-divisible-by-k/)

```java
class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0, res = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int remainder = ((sum % k) + k) % k;
            int remainderCount = map.getOrDefault(remainder, 0);
            res += remainderCount;
            map.put(remainder, remainderCount + 1);
        }
        return res;
    }
}
```

[1413. Minimum Value to Get Positive Step by Step Sum](https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/)

```cpp
int minStartValue(vector<int>& nums) {
    vector<int> prefix(nums.size(), 0);
    int minVal = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (i == 0) {
            prefix[i] = nums[i];
        } else {
            prefix[i] = nums[i] + prefix[i - 1];
        }
        minVal = min(minVal, prefix[i]);
    }
    return 1 - minVal;
}
```

[724. Find Pivot Index](https://leetcode.com/problems/find-pivot-index/)

```cpp
class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (int num : nums) sum += num;

        int prefixSum = 0;
        for (int i = 0; i < n; ++i) {
            if (prefixSum == sum - prefixSum - nums[i]) return i;
            prefixSum += nums[i];
        }
        return -1;
    }
};
```

#### [2536. Increment Submatrices by One](https://leetcode.com/problems/increment-submatrices-by-one/)

**Range Add Queries 2D: Difference Array Optimization**

### **Problem Overview**

Given an `n × n` matrix initialized to zeros, efficiently process multiple range update queries where each query adds 1 to all cells in a rectangular region `[r1,c1]` to `[r2,c2]`.

### **Visual Demo**

#### **Example**: `n = 4`, Queries: `[[1,1,2,2], [0,0,1,1]]`

***

#### **Step 1: Process Query 1 - Add 1 to region \[1,1] to \[2,2]**

**Apply Difference Array Technique:**

```
Initial Matrix (4×4):
0  0  0  0
0  0  0  0  
0  0  0  0
0  0  0  0

After Query 1 difference marking:
0  0  0  0
0 +1  0 -1     ← Row 1: +1 at col 1, -1 at col 3
0 +1  0 -1     ← Row 2: +1 at col 1, -1 at col 3  
0  0  0  0
```

#### **Step 2: Process Query 2 - Add 1 to region \[0,0] to \[1,1]**

**Accumulate difference markers:**

```
After Query 2 difference marking:
+1  0 -1  0     ← Row 0: +1 at col 0, -1 at col 2
+1 +1  0 -1     ← Row 1: +1 at col 0, +1 at col 1, -1 at col 3
 0 +1  0 -1     ← Row 2: +1 at col 1, -1 at col 3
 0  0  0  0
```

#### **Step 3: Apply Prefix Sum (Row-wise)**

**Convert difference array to actual values:**

```
Row 0: [1, 0, -1, 0] → [1, 1, 0, 0]
       ↑   ↑    ↑    ↑
       1   1+0  1-1  0+0

Row 1: [1, 2, 0, -1] → [1, 3, 3, 2]  
       ↑   ↑    ↑    ↑
       1   1+2  3+0  3-1

Row 2: [0, 1, 0, -1] → [0, 1, 1, 0]
       ↑   ↑    ↑    ↑
       0   0+1  1+0  1-1

Row 3: [0, 0, 0, 0]  → [0, 0, 0, 0]
```

**Final Result Matrix:**

```
1  1  0  0
1  3  3  2
0  1  1  0  
0  0  0  0
```

***

### **Algorithm Breakdown**

#### **Phase 1: Difference Array Setup**

For each query `[r1, c1, r2, c2]`:

```cpp
for (int r = r1; r <= r2; ++r) {
    mat[r][c1] += 1;        // Mark start of range
    if (c2 + 1 < n) {
        mat[r][c2 + 1] -= 1; // Mark end of range
    }
}
```

**Visual for Query \[1,1,2,2]:**

```
   0  1  2  3
0  0  0  0  0
1  0 +1  0 -1  ← Increment starts at col 1, ends after col 2
2  0 +1  0 -1  ← Same for each row in range
3  0  0  0  0
```

#### **Phase 2: Prefix Sum Restoration**

```cpp
for (int r = 0; r < n; ++r) {
    for (int c = 1; c < n; ++c) {
        mat[r][c] += mat[r][c - 1];  // Accumulate left to right
    }
}
```

**Row-by-row transformation:**

```
Row 1: [0, +1, 0, -1] → [0, 1, 1, 0]
       difference array   actual values
```

***

### **Key Insights**

#### **Difference Array Magic**

* **Range increment** `[L, R]` becomes **two point updates**: `+1` at `L`, `-1` at `R+1`
* **Prefix sum** converts difference markers back to actual incremented values
* **Time complexity** drops from `O(Q × R × C)` to `O(Q × R + R × C)`

#### **Why This Works**

1. **Lazy marking**: Instead of updating every cell immediately, mark range boundaries
2. **Batch processing**: Apply all difference markers first, then compute final values
3. **Cumulative effect**: Multiple queries naturally accumulate at marked positions

**Time Complexity**: `O(Q × R + R × C)` where Q = queries, R = rows, C = columns\
**Space Complexity**: `O(1)` extra space (in-place on result matrix)

This technique is particularly powerful when the number of queries is large, transforming what would be expensive range updates into efficient boundary marking operations.

```cpp
class Solution {
public:
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> mat(n, vector<int>(n, 0));
        for (const vector<int> q : queries) {
            int r1 = q[0], c1 = q[1], r2 = q[2], c2 = q[3];
            for (int r = r1; r <= r2; ++r) {
                mat[r][c1] += 1;
                if (c2 + 1 < n) {
                    mat[r][c2 + 1] -= 1;
                }
            }
        }
        for (int r = 0; r < n; ++r) {
            for (int c = 1; c < n; ++c) {
                mat[r][c] += mat[r][c - 1];
            }
        }
        return mat;
    }
};
```