PrefixSum
437. Path Sum III
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)
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
Solution 3: DP
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
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)
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;
}
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]
.
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;
}
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;
}
Prefix + HashMap and get the maximum interval.
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;
}
Maintain both positive and negative values in two arrays, update with current min/max.
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
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;
}
Maintain a prefix product. When encounter 0, reset the prefix product list.
Add: T: O(1), GetProduct: T: O(1)
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);
}
974. Subarray Sums Divisible by K
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
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;
}
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;
}
};
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]]
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]
:
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
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
atL
,-1
atR+1
Prefix sum converts difference markers back to actual incremented values
Time complexity drops from
O(Q × R × C)
toO(Q × R + R × C)
Why This Works
Lazy marking: Instead of updating every cell immediately, mark range boundaries
Batch processing: Apply all difference markers first, then compute final values
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.
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;
}
};
Last updated
Was this helpful?