Prefix sum coding pattern

Prefix Sum is a technique used to efficiently calculate the sum of a subarray within an array.

How prefix sum helps?

1. Range Query — Get the sum of numbers in the given range (i,j)of array.
2. Target based query — For given target sum, we can either find out count of sub arrays, maximum size sub arrays etc.

Build prefix sum array

Following is code for reference.

const prefixSum = (nums) => {
    const n = nums.length;
    const prefixSum = new Array(n).fill(0);
    prefixSum[0] = nums[0];
    for (let i=1; i < n; i++) {
        prefixSum[i] = prefixSum[i-1] + nums[i];
    }
    return prefixSum;
}

Range Query

We can run range query to find out the sum of elements in the subarray.

Following is code for reference.

const rangeSum = (i, j) => { 
  if(i===0) {
    return prefixSum[j];
  }
  return prefixSum[j] - prefixSum[i-1]; 
}

Prefix XOR

A prefix XOR is the bitwise XOR of all elements in a sequence from the beginning up to a given index.

We can write similar code to build the prefix xor.

const prefixXor = (nums) => {
    const n = nums.length;
    const prefix = new Array(n).fill(0);
    prefix[0] = nums[0];
    for (let i=1; i < n; i++) {
        prefix[i] = prefix[i-1] ^ nums[i];
    }
    return prefix;
}

We can also write similar range query to find the prefix xor for window i,j

const rangeXor = (i, j) => { 
  if(i===0) {
    return prefix[j];
  }
  return prefix[j] ^ prefixSum[i-1]; 
}

Let’s solve few problems to apply this concept.

560. Subarray Sum Equals K

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

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

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

Approach #1: Build every subarray followed by finding the running sum

Following is code for reference.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            // We have sub array window <i,j>
            const window = nums.slice(i, j + 1);
            const sum = window.reduce((total, a) => total + a, 0)
            if (sum === k) {
                ans++;
            }
        }
    }
    return ans;
};

Time complexity: O(n³) which is not good. Let’s apply other apporach to optimize it.

Approach #2: Use prefix sum to find sum of sub array

We can build the prefix sum then use the range query to get the sum of numbers in window in constant time.

Following is code for reference.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
    const n = nums.length;
    let ans = 0;
    const prefix = new Array(n).fill(0);
    prefix[0] = nums[0];
    for (let i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + nums[i];
    }
    const rangeQuery = (i, j) => {
        if (i === 0) {
            return prefix[j];
        }
        return prefix[j] - prefix[i - 1];
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            // We have sub array window <i,j>, let's run prefix sum range query
            const sum = rangeQuery(i,j);
            if (sum === k) {
                ans++;
            }
        }
    }
    return ans;
};

Time complexity: O(n²). It’s better than the bruteforce. But let’s see if we can optimize it further.

Approach # 3: Use optimized prefix sum based on frequency to get the count of target

One of the best usage of prefix sum is also to count the sum efficiently. Following is approach.

1. Instead of using array to store the prefix sum, we will use integer to represent the running sum.
2. Instead of running the range query, we will try to find out how many times we have seen the prefix sum before.
3. We will use a variable to track the current prefix sum and a hashmap “prefix sum -> how many times was it seen so far”.
4. If we find currentPrefixSum — target exist in the hashmap then it means we will have that many subarray with sum as target .

Let’s take following example to understand it.

nums = [3,4,1,6,10,-3,5,5,-5, -5 ], k = 7

Following is subarray with matching target sum
{3,4} {1,6}, {10,-3}, {-3,5,5}, {10,-3,5,5,-5, -5} i.e. ans = 5

If we build as hashmap with running frequency for prefix sum
3,  4,   1,  6,  10,    -3,    5,    5, -5 -> -5
3-> 7 -> 8 -> 14 -> 24-> 21 -> 26 -> 31 -> 26 -> 21 
Hashmap: {
  3: 1, 7:1, 8:1, 14:1, 24:1, 21: 2, 26:2, 31:1
}

Let's verify each running sum
0) sum = 3 , query = sum - k = 3 - 7 = -4, doesn't exist in map so ignore
map = {}
1) sum = 7 , qury = 7 - 7 = 0, 0 doesn't exist, but can we ignore?
{3,4} is a valid subarray, therefore we can't ignore. To handle the `0`,
we need to initialize map with `0` count as `1.
map = {0: 1, 3:1}
Now map check should give us one count for ans i.e. ans = 1
2) sum = 8, query = 8-7=1, ignore
map = {0:1, 3: 1, 7:1}
3) sum = 14, query = 14 - 7 = 7, since `7` exist in map so we can update ans
ans += 1 = 2
But why?
{3,4,1,6} has two ans {3,4} and {1,6}. We had already captured {3,4}
now we would like to capture {1,6} as well. Therefore we go back as per target 
and check if diff exist or not.

4) sum = 24, query = 24- 7= 17. Ignore
5) sum = 21, query = 21 - 7 = 14, let's use ans = 3
6) sum = 26, query = 26-7= 19, Ignore
7) sum = 31, query = 31-7 = 24, let's use it ans = 4
8) sum = 26, query = 19, Ignore
9) sum = 21, query = 14, let's use ans = 5

In summary, idea here is that at the current prefix sum, we will go back as per target and see how many times sum — target has been so far. We can count that many.

This optimization is only helpful if we need to inspect the window sum. It brings down time complexity to O(n)

Following is code for reference.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
    const n = nums.length;
    let ans = 0;
    const map = new Map([[0, 1]]);
    let sum = 0;
    for (let i = 0; i < n; i++) {
        sum += nums[i];
        const prevSum = sum - k
        if (map.has(prevSum)) {
            ans += map.get(prevSum);
        }
        map.set(sum, map.has(sum) ? map.get(sum) + 1 : 1)
    }
    return ans;
};

325. Maximum Size Subarray Sum Equals k

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

Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.

Example 1:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

Approach

We can apply prefix optimized approach to solve this problem. Following additional changes will be required.

1. Since we need to find out the length of subarray therefore {0:-1} will be the initialization of map to handle the window starting from beginning of array.
2. Value in the map will be initialized only once so that we can keep track of lowest previous prefix sum.

Following is code for reference.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxSubArrayLen = function (nums, k) {
    const n = nums.length;
    let ans = 0;
    const map = new Map();
    map.set(0, -1); // Represent prefix sum from beginnning
    let sum = 0;
    for (let i = 0; i < n; i++) {
        sum += nums[i];
        if (map.has(sum - k)) {
            ans = Math.max(ans, i - map.get(sum - k));
        }
        // Initilaize only once
        map.set(sum, map.has(sum) ? map.get(sum) : i)
    }
    return ans;
};

1371. Find the Longest Substring Containing Vowels in Even Counts

https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts

Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, 'a', 'e', 'i', 'o', and 'u' must appear an even number of times.

Example 1:

Input: s = "eleetminicoworoep"
Output: 13
Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.

Approach# Bitmasking to count even vowels

1. Observe that we don’t need to know the exact count of the vowels to solve this problem.
2. We only need to know whether it appears an even or odd number of times.
3. The parity of each vowel can be stored in a boolean or bit, where 0 means even and 1 means odd.
4. We need five bits to track the parity of all five vowels (a, e, i, o, u), resulting in ²⁵ = 32 possible states.
5. We can assign the first bit to a, the second to e, and so on.
6. The state of the vowels can be represented as a binary string.
7. For instance, 00000 means all vowels have even counts, while 10000 means only a has an odd count.
8. To find substrings with even vowels, we can use the XOR operator to update and track the parity of the vowels.
9. If a vowel appears an even number of times, the result of XOR will be 0; if it appears an odd number of times, the result will be 1.

We compute a running XOR for each vowel as we traverse the string. To check for substrings with even vowels, we consider two cases:

1. If the current XOR value is 00000 (i.e., all vowels have even counts), the substring from the start of the string to the current position contains even vowels.
2. If the current XOR value has occurred before, the substring between the first occurrence of that XOR value and the current position also contains even vowels.

Following is code for reference.

/**
 * @param {string} s
 * @return {number}
 */
var findTheLongestSubstring = function (s) {
    const n = s.length;
    const position = new Map([['a', 0], ['e', 1], ['i', 2], ['o', 3], ['u', 4]]);
    const map = new Map();
    map.set(0, -1);
    let prefixXor = 0;
    let ans = 0;
    for (let i = 0; i < n; i++) {
        const chr = s[i];
        if (position.has(chr)) {
            prefixXor ^= (2 ** position.get(chr));
        }
        // update ans
        if (map.has(prefixXor)) {
            ans = Math.max(ans, i - map.get(prefixXor));
        } else {
            map.set(prefixXor, i);
        }
    }
    return ans;
};

We can optimize it further to use array instead of map as we are only storing finite keys.

/**
 * @param {string} s
 * @return {number}
 */
var findTheLongestSubstring = function (s) {
    const n = s.length;
    const position = new Map([['a', 0], ['e', 1], ['i', 2], ['o', 3], ['u', 4]]);
    const map = new Array(32).fill(null);
    map[0] = -1;
    let prefixXor = 0;
    let ans = 0;
    for (let i = 0; i < n; i++) {
        const chr = s[i];
        if (position.has(chr)) {
            prefixXor ^= (2 ** position.get(chr));
        }
        // update ans
        if (map[prefixXor] !== null) {
            ans = Math.max(ans, i - map[prefixXor]);
        } else {
            map[prefixXor] = i;
        }
    }
    return ans;
};

974. Subarray Sums Divisible by K

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

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Approach

Intituition

(A[j] - A[i]) %K = 0
A[j]%K - A[i]%K = 0
A[j]%k = A[i]%K

A[i] = A * k + R0
A[j] = B * k + R1

(A[j] - A[i]) %K = (B-A) + (R1-R0)%K

It mean, we need 
R1 - R0 = C * k
R1 = C * k + R0

Similar to above, we can apply optimized prefix sum.

Following is code for reference.

const mod = (a, b) => {
        const ans = a % b;
        return ans >= 0 ? ans : ans + b;
    }
    const n = A.length;
    let sum = 0;
    let ans = 0;
    const map = new Map();
    map.set(0, 1);
    for (let j = 0; j < n; j++) {
        const num = A[j];
        sum += num;
        const target = mod(sum, K);
        if (map.has(target)) {
            ans += map.get(target);
        }
        map.set(target, map.has(target) ? map.get(target) + 1 : 1);
    }
    return ans;
};

1590. Make Sum Divisible by P

https://leetcode.com/problems/make-sum-divisible-by-p/description/

Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.

Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.

A subarray is defined as a contiguous block of elements in the array.

Example 1:

Input: nums = [3,1,4,2], p = 6
Output: 1
Explanation: The sum of the elements in nums is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.

Approach# Apply running sum as prefix sum with module operation

We can come up with following as per given condition

nums = [3,1,4,2], p = 6
total = (nums[0,...n-1])
subarray_sum(i,j) = A[j]-A[i]
(total - (A[j]-A[i]))%p = 0
(total - A[j] + A[i])%p = 0
total%p - A[j]%p + A[i]%p = 0
A[j]%p = total%p + A[i]%p
A[i]%p = A[j]%p - total%p

Other than using the running prefix sum concept, this problem also needs to apply following concept.

Modulo with Negative Numbers: In some programming languages (like Python), the modulo operation with a negative number returns a negative result. For example, (-16) % 148 would result in -16. To handle it, we can come up with following custom mod method.

int mod(int a, int b) { 
  return (a % b + b) % b; 
}

int vs long to avoid overflow: When we calculate the sum then we need to declare sum as long to avoid the overflow. Following is code for reference.

long total = 0;
for (auto num : nums) {
    total +=num;
}

Consistent modulo to avoid overflow: long is not enough to handle the overflow for large input. To avoid it, instead of calculating the total sum, we need to keep taking mod. Please note; after applying consistent modulo, we don’t need long type.

  int total = 0;
  for (auto num : nums) {
      total = mod(total + num, p); // Apply modulo to avoid overflow
  }

Following is complete code for reference.

class Solution {
private:
    int mod(int a, int b) { return (a % b + b) % b; }

public:
    int minSubarray(vector<int>& nums, int p) {
        int total = 0;
        for (auto num : nums) {
            total = mod(total + num, p); // Apply modulo to avoid overflow
        }
        int n = nums.size();
        unordered_map<int, int> map = {{0, -1}};
        int aj_p = 0;
        int ans = n;
        for (int j = 0; j < n; j++) {
            // This represents running prefix sum i.e. A[j]
            aj_p = mod(aj_p + nums[j], p); // Apply modulo to avoid overflow
            map[aj_p] = j; // Keep updating to get the larger subarray
            int ai_p = mod(aj_p - total, p);
            if (map.count(ai_p) > 0) {
                ans = min(ans, j - map[ai_p]);
            }
        }
        return ans == n ? -1 : ans;
    }
};

1413. Minimum Value to Get Positive Step by Step Sum

https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/description/

Given an array of integers nums, you start with an initial positive value startValue.

In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).

Return the minimum positive value of startValue such that the step by step sum is never less than 1.

Example 1:

Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

Approach

1. Step by step sum is nothing but a prefix sum.
2. We can calculate the running prefix sum.
3. We need to track the minimum value of running prefix sum, lets call it x
4. If the lowest prefix sum is less than zero then value of startValue can be -x + 1 to maintain the condition
5. Otherwise we can return 1.

Following is code for reference.

class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int sum = 0;
        int x = INT_MAX;
        for(auto num: nums) {
            sum += num;
            x = min(x, sum);
        }
        return x >= 0 ? 1: -x+1;
    }
};

548. Split Array with Equal Sum

https://leetcode.com/problems/split-array-with-equal-sum/description/

Given an integer array nums of length n, return true if there is a triplet (i, j, k) which satisfies the following conditions:

• 0 < i, i + 1 < j, j + 1 < k < n - 1
• The sum of subarrays (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) and (k + 1, n - 1) is equal.

A subarray (l, r) represents a slice of the original array starting from the element indexed l to the element indexed r.

Example 1:

Input: nums = [1,2,1,2,1,2,1]
Output: true
Explanation:
i = 1, j = 3, k = 5. 
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1

Approach

1. We can utilize prefix sum to speedup subarray sum
2. We can calculate the prefix sum
3. Will first iterate j=3….n-3
4. Then iterate i=0….j-2
5. sum1 = querySum(0,i-1)
6. sum2 = querySum(i+1, j-1)
7. If sum1== sum2, then this could be a candidate ans. So let’s add into Set<>
8. Now we can try all possible boundary for k=j+2….n-2
9. sum3 = querySum(j+1,k-1)
10. sum4=querySum(k+1,n-1)
11. If set.has(sum3) && sum3 === sum4 then we have answer.

Following is code for reference.

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var splitArray = function (nums) {
    const n = nums.length;
    const prefix = new Array(n).fill(0);
    const querySum = (i, j) => {
        if (i === 0) {
            return prefix[j];
        }
        return prefix[j] - prefix[i - 1];
    }
    prefix[0] = nums[0];
    for (let i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + nums[i];
    }
    // Start with j
    for (let j = 3; j < n - 3; j++) {
        const set = new Set();
        // Try all possible i
        for (let i = 1; i < j - 1; i++) {
            const sum1 = querySum(0, i - 1);
            const sum2 = querySum(i + 1, j - 1);
            if (sum1 === sum2) {
                set.add(sum1);
            }
        }
        // Try all possible boundary for k
        for (let k = j + 2; k < n - 1; k++) {
            const sum3 = querySum(j + 1, k - 1);
            const sum4 = querySum(k + 1, n - 1);
            if (set.has(sum3) && sum3 === sum4) {
                // this is ans
                return true;
            }
        }
    }
    return false;
};

Prefix sum in 2D Array

We can extend the prefix sum concept on 2D array as well. Let’s take following example.

Here prefix sum for (i,j) is sum of all the elements in that rectangle starting from (0,0) to (i,j) .

Similar to 1D, once we calculate the prefix sum, then in constant time we can find out sum of all the elements in any window.

How to calculate prefix sum?

How to handle 0th index?

Instead of handling 0th index separately, we will create prefix size one higher. Following is code to build prefix sum on 2d.

const getPrefixSum = matrix => {
    const m = matrix.length;
    const n = matrix[0].length;
    const prefix = new Array(m+1).fill(0).map(a => new Array(n+1).fill(0));
    for (let i=1; i < m + 1; i++) {
        for (let j=1; j < n+1; j++) {
            prefix[i][j] = prefix[i][j-1] + prefix[i-1][j] - prefix[i-1][j-1] + matrix[i-1][j-1]
        }
    }
    return prefix;
}

How to run range sum query?

To calculate the range sum (x,y,p,q), we need to keep in mind of following.

When we reduce upper and right part then the corner one is removed twice. Therefore we will have to add it back. Following is code for query sum.

const rangeSumWrapper = (prefix, i, j, l, r) => {
    return prefix[l][r] - prefix[i-1][r] - prefix[l][j-1] + prefix[i-1][j-1];
}
const rangeSum = (prefix, i, j , l, r) => {
    return rangeSumWrapper(prefix, i+1, j+1, l+1, r+1);
}

304. Range Sum Query 2D — Immutable

https://leetcode.com/problems/range-sum-query-2d-immutable/

Approach # 1: Use extra length prefix size to handle 0 for cleaner code

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function(matrix) {
    // build prefix sum on 2D
    this.prefix = this.buildPrefixSum(matrix);
};
NumMatrix.prototype.buildPrefixSum = function(matrix) {
    const m = matrix.length;
    if(m === 0) {
        return [[0]];
    }
    const n = matrix[0].length;
    const prefix = new Array(m+1).fill(0).map(a => new Array(n+1).fill(0));
    
    // base case: empty col
    for(let i=0; i < m + 1; i++) {
       prefix[i][0] = 0; 
    }
    
    // base case: empty row
    for (let j=0; j < n + 1; j++) {
        prefix[0][j] = 0;
    }
    
    // fill row and col
    for (let i=1; i < m + 1; i++) {
        for (let j=1; j < n + 1; j++) {
            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1];
        }
    }
    return prefix;
    
};
NumMatrix.prototype.sumRegionWrapper = function(row1, col1, row2, col2) {
    return this.prefix[row2][col2] -  this.prefix[row1-1][col2] - this.prefix[row2][col1-1] + this.prefix[row1-1][col1-1];
};
/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
   return this.sumRegionWrapper(row1+1, col1+1, row2+1, col2+1); 
};

Approach #2: Use same size with edge case to handle zero

class NumMatrix {
private:
    vector<vector<int>> prefix;
    void buildPrefix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        prefix.resize(m, vector<int>(n));
        // Fill 0th cell
        prefix[0][0] = matrix[0][0];

        // Fill 0th col
        for (int i = 1; i < m; i++) {
            prefix[i][0] = prefix[i - 1][0] + matrix[i][0];
        }
        // Fill 0th row
        for (int j = 1; j < n; j++) {
            prefix[0][j] = prefix[0][j - 1] + matrix[0][j];
        }
        // Fill rest
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] -
                               prefix[i - 1][j - 1] + matrix[i][j];
            }
        }
    }
    int query(int i, int j, int p, int q) {
        if (i == 0 && j == 0) {
            return prefix[p][q];
        }
        if (i == 0) {
            return prefix[p][q] - prefix[p][j - 1];
        }
        if (j == 0) {
            return prefix[p][q] - prefix[i - 1][q];
        }
        return prefix[p][q] - prefix[i - 1][q] - prefix[p][j - 1] +
               prefix[i - 1][j - 1];
    }

public:
    NumMatrix(vector<vector<int>>& matrix) {
        buildPrefix(matrix);
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return query(row1, col1, row2, col2);
    }
};

1074. Number of Submatrices That Sum to Target

https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/description/

Given a matrix and a target, return the number of non-empty submatrices that sum to target.

A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.

Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.

Example 1:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

Approach: 2d prefix sum with one extra space

We can apply 2d prefix sum. Following is code for reference.

class Solution {
private:
    vector<vector<int>> prefix;
    void buildPrefix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        prefix.resize(m, vector<int>(n));
        // Fill 0th cell
        prefix[0][0] = matrix[0][0];

        // Fill 0th col
        for (int i = 1; i < m; i++) {
            prefix[i][0] = prefix[i - 1][0] + matrix[i][0];
        }
        // Fill 0th row
        for (int j = 1; j < n; j++) {
            prefix[0][j] = prefix[0][j - 1] + matrix[0][j];
        }
        // Fill rest
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] -
                               prefix[i - 1][j - 1] + matrix[i][j];
            }
        }
    }
    int query(int i, int j, int p, int q) {
        if (i == 0 && j == 0) {
            return prefix[p][q];
        }
        if (i == 0) {
            return prefix[p][q] - prefix[p][j - 1];
        }
        if (j == 0) {
            return prefix[p][q] - prefix[i - 1][q];
        }
        return prefix[p][q] - prefix[i - 1][q] - prefix[p][j - 1] +
               prefix[i - 1][j - 1];
    }

public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        buildPrefix(matrix); // first build the prefix sum
        int ans = 0;
        int m = matrix.size();
        int n = matrix[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int p = 0; p <= i; p++) {
                    for (int q = 0; q <= j; q++) {
                        // (p,q) to (i,j)
                        int sum = query(p, q, i, j);
                        if (sum == target) {
                            ans++;
                        }
                    }
                }
            }
        }
        return ans;
    }
};

363. Max Sum of Rectangle No Larger Than K

https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/description/

Approach: Apply 2d prefix sum

class Solution {
private:
    vector<vector<int>> prefix;
    void buildPrefix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        prefix.resize(m, vector<int>(n));
        // Fill 0th cell
        prefix[0][0] = matrix[0][0];

        // Fill 0th col
        for (int i = 1; i < m; i++) {
            prefix[i][0] = prefix[i - 1][0] + matrix[i][0];
        }
        // Fill 0th row
        for (int j = 1; j < n; j++) {
            prefix[0][j] = prefix[0][j - 1] + matrix[0][j];
        }
        // Fill rest
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] -
                               prefix[i - 1][j - 1] + matrix[i][j];
            }
        }
    }
    int query(int i, int j, int p, int q) {
        if (i == 0 && j == 0) {
            return prefix[p][q];
        }
        if (i == 0) {
            return prefix[p][q] - prefix[p][j - 1];
        }
        if (j == 0) {
            return prefix[p][q] - prefix[i - 1][q];
        }
        return prefix[p][q] - prefix[i - 1][q] - prefix[p][j - 1] +
               prefix[i - 1][j - 1];
    }

public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        buildPrefix(matrix); // first build the prefix sum
        int ans = INT_MIN;
        int m = matrix.size();
        int n = matrix[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int p = 0; p <= i; p++) {
                    for (int q = 0; q <= j; q++) {
                        // (p,q) to (i,j)
                        int sum = query(p, q, i, j);
                        if (sum <= k) {
                            ans = max(ans, sum);
                        }
                    }
                }
            }
        }
        return ans;
    }
};

525. Contiguous Array

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

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Approach #1(TLE): Try every substring — using prefix sum

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxLength = function (nums) {
    const n = nums.length;
    const prefix = new Array(n).fill(0);
    prefix[0] = nums[0];
    for (let i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + nums[i];
    }
    const rangeQuery = (i, j) => {
        if (i === 0) {
            return prefix[j];
        }
        return prefix[j] - prefix[i - 1];
    }
    let ans = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            const sum = rangeQuery(i, j);
            const size = j - i + 1;
            const expected = Math.floor(size / 2);
            if (sum === expected && size % 2 === 0) {
                ans = Math.max(ans, size);
            }
        }
    }
    return ans;
}

Approach #2(TLE): Try every substring — using zeros and ones counter

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxLength = function (nums) {
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n; i++) {
        let ones = 0;
        let zeros = 0;
        for (let j = i; j < n; j++) {
            const size = j - i + 1;
            if(nums[j] === 1) {
                ones++;
            } else {
                zeros++;
            }
            if(ones === zeros) {
                ans = Math.max(ans, size);
            }
        }
    }
    return ans;
};

Approach #3: Use first time ones and zero diff index tracking (similar to prefix sum optimization)

1. We would like to calculate the best substring with equal one and zero ending at index i .
2. At index i , we need to know the current ones and zeros count.
3. If ones===zeros then we have valid substring ending at i .
4. Otherwise find out diff=ones-zeros and see if diff exist in the prefix map.
5. If does exist then it means we can discard the diff to make substring valid ans.
6. Keep tracking the global ans.

Following is code for reference.

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxLength = function (nums) {
    const n = nums.length;
    const diffMap = new Map();
    let ans = 0;
    let ones = 0;
    let zeros = 0;
    for (let i = 0; i < n; i++) {
        if (nums[i] === 1) {
            ones++;
        } else {
            zeros++;
        }
        const diff = ones - zeros; // order doesn't matter, we just need to stick the chosen order
        if (!diffMap.has(diff)) {
            diffMap.set(diff, i);
        }
        if (diff === 0) {
            // valid substring
            ans = Math.max(ans, i + 1);
        } else if (diffMap.has(diff)) {
            ans = Math.max(ans, i - diffMap.get(diff));
        }
    }
    return ans;
};

We can optimize code further optimizing the variables.

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        int counter = 0;
        unordered_map<int, int> map = {{0, -1}};
        int ans = 0;
        for (int i = 0; i < n; i++) {
            counter = counter + (nums[i] == 1 ? 1 : -1);
            if (map.count(counter) > 0) {
                ans = max(ans, i - map[counter]);
            }
            if (map.count(counter) == 0) {
                map[counter] = i;
            }
        }
        return ans;
    }
};

825. Friends Of Appropriate Ages

https://leetcode.com/problems/friends-of-appropriate-ages/description

There are n persons on a social media website. You are given an integer array ages where ages[i] is the age of the ith person.

A Person x will not send a friend request to a person y (x != y) if any of the following conditions is true:

• age[y] <= 0.5 * age[x] + 7
• age[y] > age[x]
• age[y] > 100 && age[x] < 100

Otherwise, x will send a friend request to y.

Note that if x sends a request to y, y will not necessarily send a request to x. Also, a person will not send a friend request to themself.

Return the total number of friend requests made.

Example 1:

Input: ages = [16,16]
Output: 2
Explanation: 2 people friend request each other.

Constraints:

• n == ages.length
• 1 <= n <= 2 * 104
• 1 <= ages[i] <= 120

Approach 1 (TLE)# Scan every pair and verify the condition

Three conditions could be merged to one:

The Person with age A can request person with age B if

• B is in range ( 0.5 * A + 7, A ]

Then we can try all possible pair to test this condition as below.

const isValid = (ages, x, y) => {
    if (ages[y] > 0.5 * ages[x] + 7 && ages[y] <= ages[x]) {
        return true;
    }
    return false;
}
/**
 * @param {number[]} ages
 * @return {number}
 */
var numFriendRequests = function (ages) {
    let ans = 0;
    const n = ages.length;
    for (let x = 0; x < n; x++) {
        for (let y = x + 1; y < n; y++) {
            // if not a valid option
            if (isValid(ages, x, y)) {
                ans++;
            }
            if (isValid(ages, y, x)) {
                ans++;
            }
        }
    }
    return ans;
};

Approach 2 # Use counting sort + prefix sum

1. We can count each ages with help of counting sort.
2. As per condition, age is between 1<=x<=120 , therefore we can create array of 121 size.
3. Create countAges array to count the frequency of each ages.
4. Create prefixSum and populate it with help of countAges
5. For person with age i , it can make request with ( 0.5 * i + 7, i] , it means we can run prefix sum query for 0.5 * i + 7
6. Since same user can’t make friend request therefore needs to subtract countAges[i] as well.

Following is code for reference.

/**
 * @param {number[]} ages
 * @return {number}
 */
var numFriendRequests = function (ages) {
    let ans = 0;
    const countAges = new Array(121).fill(0);
    const prefixSum = new Array(121).fill(0);
    // Count each age
    for (const age of ages) {
        countAges[age]++;
    }
    // Build prefix sum
    for (let i=1; i <=120; i++) {
        prefixSum[i] = prefixSum[i-1] + countAges[i];
    }
    // Lowest valid value of i will be 15
    for (let i=15; i <=120; i++) {
        if(countAges[i] === 0) {
            continue;
        }
        const count = prefixSum[i] - prefixSum[Math.floor(i/2) + 7];
        //people will not friend request themselves, so  - numInAge[i]
        ans += count * countAges[i] - countAges[i];
    }
    return ans;
};

629. K Inverse Pairs Array

https://leetcode.com/problems/k-inverse-pairs-array/description

For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].

Given two integers n and k, return the number of different arrays consisting of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 109 + 7.

Example 1:

Input: n = 3, k = 0
Output: 1
Explanation: Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pairs.

Example 2:

Input: n = 3, k = 1
Output: 2
Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

Approach

Idea behind the approach

1. Let’s start with a simple example with n=4, no k is defined right now.
2. For k=0, the only possible arrangement for the given array will be [1,2,3,4]
3. If we shift last number 4 towards left 1 position then it will generate k=1 inverse pair as [1,2,4,3] .
4. If we would have shifted number 4 towards left by 2 position then it would have generated k=2 inverse pair as [1,4,2,3] .
5. We could have mixed and match as well i.e. to reach the target [2,4,1,3] , by shifting 2 by one position towards the left first and then shifting 4 by 2 positions towards the left. Thus, the total number of displacements is 3, which is equal to the number of inverse pairs in the new array.

Now let’s write it in recursion technique

1. f(n,k) represents the number of inversion.
2. Let’s say we have already solve problem with the size n-1 and now goal is to add last number n to make the size n problem.
3. If we add at the last position then it will not generate any new inversion i.e. f(n,k) = f(n-1,k)
4. If we add n at a position 1 step from the right f(n,k)=f(n-1,k-1)
5. If we add n at a position ith step from the right f(n,k)=f(n-1,k-i)
6. To generalize it, we can write it as below.

f(n,k) = sum( f(n-1, k-i)) where i=0....min(k,n-1)

Base cases:
f(0,k) = 0
f(n,0) = 1

Note: This is a standard Triangle of Mahonian numbers formula to count the inversion pairs.

Based on this we can write code as below.

const recursion = (n, k) => {
    if (n === 0) {
        return 0;
    }
    if (k === 0) {
        return 1;
    }
    let ans = 0;
    for (let i = 0; i <= Math.min(k, n - 1); i++) {
        ans += recursion(n - 1, k - i);
    }
    return ans;
}

We can optimize it further with memoization as below.

const recursion = (n, k, dp) => {
    if (n === 0) {
        return 0;
    }
    if (k === 0) {
        return 1;
    }
    if (dp[n][k] !== -1) {
        return dp[n][k];
    }
    let ans = 0;
    for (let i = 0; i <= Math.min(k, n - 1); i++) {
        ans += recursion(n - 1, k - i, dp);
    }
    return dp[n][k] = ans;
}
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kInversePairs = function (n, k) {
    const dp = new Array(n + 1).fill(0).map(a => new Array(k + 1).fill(-1));
    return recursion(n, k, dp);

};

Above code will throw overflow error which can be fixed by adding the modulo.

const PRIME = 1000000007;
const recursion = (n, k, dp) => {

    if (n === 0) {
        return 0;
    }
    if (k === 0) {
        return 1;
    }
    if (dp[n][k] !== -1) {
        return dp[n][k];
    }
    let ans = 0;
    for (let i = 0; i <= Math.min(k, n - 1); i++) {
        ans = (ans + recursion(n - 1, k - i, dp)) % PRIME;
    }
    return dp[n][k] = ans;
}
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kInversePairs = function (n, k) {
    const dp = new Array(n + 1).fill(0).map(a => new Array(k + 1).fill(-1));
    return recursion(n, k, dp);

};

But it still throw TLE as time complexity is O(nkmin(n,k)) .

Before we think to optimize it further, let’s write it using bottom up dynamic programming as below.

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kInversePairs = function (n, k) {
    const PRIME = 1000000007;
    const dp = new Array(n + 1).fill(0).map(a => new Array(k + 1).fill(0));
    // base case: k=0
    for (let i = 1; i < n + 1; i++) {
        dp[i][0] = 1;
    }
    // fill rest
    for (let i = 1; i < n + 1; i++) {
        for (let j = 1; j < k + 1; j++) {
            for (let p = 0; p <= Math.min(j, i - 1); p++) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - p]) % PRIME
            }
        }
    }
    return dp[n][k];
};

We can further optimize it based on following observations

1. We are traversing back to some limit in the previous row of the dp array to get sum to fill the current dp.
2. We can use prefix sum to get the window sum at constant time.

Following is updated code for reference.

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kInversePairs = function (n, k) {
    const PRIME = 1000000007;
    const dp = new Array(n + 1).fill(0).map(a => new Array(k + 1).fill(0));
    const prefix = new Array(n + 1).fill(0).map(a => new Array(k + 1).fill(0));
    // base case: k=0
    for (let i = 1; i < n + 1; i++) {
        dp[i][0] = 1;
        prefix[i][0] = 1;
    }
    // fill rest
    for (let i = 1; i < n + 1; i++) {
        for (let j = 1; j < k + 1; j++) {
            if (j - i >= 0) {
                dp[i][j] = (prefix[i - 1][j] - prefix[i - 1][j - i] + PRIME) % PRIME;
            } else {
                dp[i][j] = prefix[i - 1][j];
            }
            // Update prefix at runtime
            prefix[i][j] = (prefix[i][j - 1] + dp[i][j]) % PRIME
        }
    }
    return dp[n][k];
};

We can also re-write same using single prefix array.

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var kInversePairs = function (n, k) {
    const PRIME = 1000000007;
    const prefix = new Array(n + 1).fill(0).map(a => new Array(k + 1).fill(0));
    // base case: k=0
    for (let i = 1; i < n + 1; i++) {
        prefix[i][0] = 1;
    }
    // fill rest
    for (let i = 1; i < n + 1; i++) {
        for (let j = 1; j < k + 1; j++) {
            let current = 0;
            if (j - i >= 0) {
                current = (prefix[i - 1][j] - prefix[i - 1][j - i] + PRIME) % PRIME;
            } else {
                current = prefix[i - 1][j];
            }
            // Update prefix at runtime
            prefix[i][j] = (prefix[i][j - 1] + current) % PRIME
        }
    }
    return k === 0 ? prefix[n][k] : (prefix[n][k] - prefix[n][k - 1] + PRIME) % PRIME;
};

361. Bomb Enemy

https://leetcode.com/problems/bomb-enemy/description/

Given an m x n matrix grid where each cell is either a wall 'W', an enemy 'E' or empty '0', return the maximum enemies you can kill using one bomb. You can only place the bomb in an empty cell.

The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since it is too strong to be destroyed.

Example 1:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

Example 2:

Input: grid = [["W","W","W"],["0","0","0"],["E","E","E"]]
Output: 1

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid[i][j] is either 'W', 'E', or '0'.

Approach 1: Bruteforce approach

We can calculate ans for each cell and keep track of global max. Following is code for reference.

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;
        for(int i=0; i < m; i++) {
            for (int j=0; j < n; j++) {
                if(grid[i][j] == '0') {
                    ans = max(ans, count(grid, i, j));
                }
            }
        }
        return ans;
    }
    int count(vector<vector<char>>& grid, int i, int j) {
        int ans = 0;
        int m = grid.size();
        int n = grid[0].size();        
        vector<vector<int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (auto dir: dirs) {
            int p = dir[0];
            int q = dir[1];
            int x = i;
            int y = j;
            while( x >=0 && x <m && y >=0 && y < n && grid[x][y] !='W') {
                if(grid[x][y] =='E') {
                    ans++;
                }
                x+=p;
                y+=q;
            }
        }
      return ans;  
    }
};

Approach 2: Use prefix sum

Brute-force approach has redundant calculations when there is no wall in the rows/columns.

As we know, the given an empty cell located at (row, col), if we place a bomb on the cell, its influence zone would extend over the same row and column.

We can say that total_hits = row_hits + col_hits.

In order to calculate the row_hits, we can break it down into two cases:

Case #1: Cell is on the beginning of row

We can scan entire row until we hits the wall or boundary of the grid.

Case #2: Cell is at right after the wall

In this case the previous calculated row_hits become invalid. It means we will have to recalculate it again starting from this cell.

We can use running prefix sum here for both rows and column. Following is code for reference.

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;
        vector<int> rowHits(m,0);
        vector<int> colHits(n,0);
        for(int i=0; i < m; i++) {
            for (int j=0; j < n; j++) {
                // Reset the hits and recalculate for row if necessory
                if(j == 0 || grid[i][j-1]=='W') {
                    rowHits[i] = 0;
                    for(int k=j; k < n; k++) {
                        if(grid[i][k] =='W') {
                            // Stop the scan as we hit the wall
                            break;
                        } else if (grid[i][k] =='E') {
                            rowHits[i]++;
                        }
                    }
                }
                // Reset the hits and recalculate for cols if necessory
                if(i == 0 || grid[i-1][j] == 'W') {
                    colHits[j] = 0;
                    for(int k=i; k < m; k++) {
                        char cell = grid[k][j];
                        if(cell =='W') {
                            // Break as we can't cross the wall
                            break;
                        } else if (cell == 'E') {
                            colHits[j]++;
                        }
                    }
                }
                // Run the calculation for the empty cell
                if(grid[i][j] == '0') {
                    ans = max(ans, rowHits[i] + colHits[j]);
                }
            }
        }
        return ans;
    }
};

Happy learning :-)