> 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 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 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 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 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 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. ```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 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 list; TreeMap 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 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& nums) { vector 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& 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> rangeAddQueries(int n, vector>& queries) { vector> mat(n, vector(n, 0)); for (const vector 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; } }; ``` --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://howardyangemail.gitbook.io/decode-leetcode/array/prefixsum.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.