In this Study Guide, we will learn about problem based on prefix sum.
My Other on Study Guide :
Line Sweep Algorithms | Solving kth kind of problems
BFS and its variations | Binary Lifting Technique
Binary Index Tree | Prefix Sum
Introduction
Often these kinds of problems asks for either count or length (minimum/maximum) of subarray based on certain mathematical condition for example that the subray sum or
sub array divisbility or mod or vowel counting etc etc.
At first glance you will tempted to attempt these kind of problems using Sliding Window technique but quickly realizes that its not possible, either elements are -ve or some other conditions.
For these kind of problem, we have Prefix Sum approach.
I have divided this guide into 4 sections.
Section 1 : deals with standard prefix sum problem.
Section 2 : deals with problems on divisbility and modulo.
Section 3: deals with prefix sum and XOR.
Section 4: 2D Prefix Sum Problems.
Please drop in comments if any interesting problems are missed out.
I have kept the code(in C++) as collpased, I would encourage to solve yourself first and if you get stuck , expand to see the code.
Mostly all this problems has time complexity of O(n) and a space complexity of also O(n) due to map.
Basic Idea
Lets understand this with an introductory problem 560. Subarray Sum Equals K
The question ask count of subarray whose sum is K (given as an input along with array).
psumi is current running subarray sum.
if in past psumj we have found an array which we have recorded (in hash map) such that
psumi - psumj = K
that essentially mean array from [j...i] sum is K and that is what we are looking for !
so after accumulating psumi, we try to find psumj existence in our map using below forumla.
psumj = psumi - K
Template
- Maintain a
prefix_sum = 0, this is our psumi - Setup a unordered_map or sometime vector is also help if you know the range.
- A varaible to store
answer = 0 - Initialize this map[0] element.
a) if the question is asking for count thenm[0] = 1, why is this ? suppose in above example if psumi - K = 0, that means entire subarray is an answer , so add m[0] to answer.
b) if we need to find length thenm[0] = -1, if at ith index psumi - K = 0, that means the i - j , here j is m[0] is -1,length is i + 1(0 based indexing). - Iterate the array and accumulate pSum.
- Check if pSum -K exists in map ? , if Yes add to answer.
- Increment(count) or store index(length) of current psum like we do
countMap[pSum]++orlenMap[pSum] = i.
Easy problem : 1480. Running Sum of 1d Array
Section 1
Warmup Problem on psum:
303. Range Sum Query - Immutable
560. Subarray Sum Equals K
1310. XOR Queries of a Subarray
Just follow the above template step by step.
Expand to see Code
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> countMap;
int pSum = 0;
int ans = 0;
int n = nums.size();
countMap[0] = 1;
for(int i =0; i < n ; ++i){
pSum += nums[i];
if(countMap.count( pSum -k) > 0){
ans += countMap[pSum-k];
}
countMap[pSum]++;
}
return ans;
}2559. Count Vowel Strings in Ranges
Here we mark each string index as 1 if condition satisfies and then uses prefix sum to answer queries in O(1) time.
Compute prefix sum in standard way in O(n) time.
Expand to see Code
class Solution {
public:
vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
int n = words.size();
vector<int> arr(n, 0);
for(int i =0; i < n ; ++i){
int l = words[i].size() -1;
if((words[i][0]=='a' or words[i][0]=='e' or
words[i][0]=='i' or words[i][0]=='o' or
words[i][0]=='u' ) and (words[i][l]=='a' or words[i][l]=='e' or
words[i][l]=='i' or words[i][l]=='o' or
words[i][l]=='u' )){
arr[i] = 1;
}
}
vector<int> psum(1+n, 0);
for(int i = 0; i < n ; ++i){
psum[i+1] = arr[i] + psum[i];
}
vector<int> ans(queries.size());
for(int i =0; i< queries.size(); ++i){
ans[i] = psum[queries[i][1]+1] - psum[queries[i][0]];
}
return ans;
}
};
325. Maximum Size Subarray Sum Equals k
Same problem as above but instead of asking count, here we need to find the longest subarray size.
So we have initialize lenMap[0] = -1
Secondly if the pSum doexnt exist in hasmap only then update the index, this is because we haev to find the longest length, so the earlier index are better.
Expand to see Code
int maxSubArrayLen(vector<int>& nums, int k) {
unordered_map<int, int> lenMap;
int pSum = 0;
int ans = 0;
int n = nums.size();
lenMap[0] = -1;
for(int i =0; i < n ; ++i){
pSum += nums[i];
if(lenMap.count( pSum -k) > 0){
ans = max(ans, i - lenMap[pSum-k]);
}
if(lenMap.find(pSum)==lenMap.end()) // Update if not exists
lenMap[pSum] = i;
}
return ans;
}1248. Count Number of Nice Subarrays
Same as 560 but we are only interested in odd number, so convert the input array as binary array 1 or odd and 0 for even and proceed same as 560.
[930. Binary Subarrays With Sum] (https://leetcode.com/problems/binary-subarrays-with-sum/description/)
Exactly same as above
2364. Count Number of Bad Pairs
Total pairs would be n * (n-1) / 2
And remove tose pairs which dont satisfy the rule i- nums[i] == j - nums[j]
Expand to see Code
long long countBadPairs(vector<int>& nums) {
long long n = nums.size();
long long ans = (n * (n-1))>>1;
unordered_map<int, long long> m;
for(int i =0; i <n ; ++i){
int diff = i - nums[i];
ans -= m[diff];
++m[diff];
}
return ans;1658. Minimum Operations to Reduce X to Zero
This question ask for removal from left or right, that means , all other leftover element would be a subarray.
We have to minimum operation if leftover element subarray would be as large as possiible.
Lets see with an example to understand better.
[1,1,4,2,3], x = 5
total sum of element is 10 , and we need to reduce x to 0, so that means leftover subarray sum would be total - x
So try to find a largest subarray where this holds true and if not return -1.
Expand to see Code
int minOperations(vector<int>& nums, int x) {
int target = -x;
for (int i : nums)
target += i;
int n = nums.size();
if(target==0) // base where all elements of array used to get x
return n;
int ans = INT_MIN;
int left = 0;
int right = 0;
unsigned long long sum =0;
for (; right < n ; ++right)
{
sum += nums[right];
while(sum >= target)
{
if(sum==target)
ans = max(ans, right-left +1);
sum -= nums[left++];
}
}
return ans==INT_MIN ? -1 : n - ans;
}Section 2: Prefix Sum & Division/Modulo
Next few questions requires some mathematics and divisbility rule.
For divisiiblity related problem (subarray divisible by K) , we need to know if
subarray between [j,i] i.e. psum_i - psum_j = q . K
If we take modulo on both side
psum_i %K - psum_j%K = 0;
So while iterating we look for psum_i%K
And also update in similar way i.e. countMap[psum %K]++
Negative remainder :
As per Euclidean division algorithm, Given two integers a and b, with b ≠ 0, a = bq + r , where 0 ≤ r < |b|
Point to note is remainder(r) must always be a +ve number.
What happen either of a or b is -ve , for example -5 % 2 = ?
For example -5 = 2 *(-3) + 1 (r is 1)
But if you do same in C++, r`` would be -1, this is due to C++ implementation. To fix this we would do (r + 2(b) ) % 2(b) , that would give 1. If remainder is +ve , it wont harm either So for prefix sum problem, we can do psum_j = ( ( (psum + i) %K ) + K)%K and find this value in hashmap. So we add ith element to psum and for negative offset we add+K``` and take modulo again.
With above knowledge lets try to solve few problems
974. Subarray Sums Divisible by K
As we discussed above , at each iteration look for (psum +i )%K and to fix negative remainded add +K and again take modulo.
Expand to see Code
int subarraysDivByK(vector<int>& A, int K) {
int ans = 0;
int sum = 0;
unordered_map<int, int> countMap;
countMap[0] = 1;
for(int i : A){
// For +ve remainder it wont matter
// FOr -ve remainder, it will make as +ve
sum = (((sum + i)%K ) +K)%K;
if(countMap.find(sum)!=countMap.end()){
ans += countMap[sum];
}
countMap[sum]++;
}
return ans;
}1497. Check If Array Pairs Are Divisible by k
bool canArrange(vector<int>& arr, int k) {
unordered_map<int, int> rem_map;
for(int i : arr){
int r = (i + k) % k;
if(r < 0){
r += k;
}
if(rem_map[(k-r)%k] > 0 ){
--rem_map[(k-r)%k];
}else{
++rem_map[r];
}
}
int sum = 0;
// if all the remainder found their complementary partner ? sum would be 0 then
for(auto& i : rem_map){
sum += i.second;
}
return sum==0;
}1590. Make Sum Divisible by P
Here we are trying to find smallest subarray of size remainder i.e. k = totalSum % p, here totalSum is sum of all array element.
psumi - psumj = k
if we remove this smallest subarray of k that means entire subarray sum excluding this smallest subarray will be divisible of p.
So we go and find the smallest subarray of size k
Code:
Notice we haev to find Smallest Subarray so we overwite an existing sum , unlike 325.
Expand to see Code
int minSubarray(vector<int>& nums, int p) {
// Smallest subarray of size remainder(k)
long long sum = accumulate(nums.begin(), nums.end(), 0LL);
int k = sum % p;
if(k==0){
return 0;
}
unordered_map<int, int> lenMap;
lenMap[0] = -1;
int psum = 0;
int n = nums.size();
int ans = n;
for(int i =0; i < nums.size(); ++i){
psum = (psum + nums[i])%p;
auto it = lenMap.find((psum -k + p )%p);
if(it!=lenMap.end()){
ans = min(ans, i - it->second);
}
lenMap[psum] = i;
}
return ans == n ? -1: ans;
}523. Continuous Subarray Sum
Asking subarray whichis multiple of K and length atleast 2
multiple of K means remainder has to 0, same as above problems.
Expand to see Code
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int, int> m ; //key is remainder and value is position
int sum =0;
int n = nums.size();
m[0] = -1;
for(int i = 0; i < n ; ++i)
{
sum += nums[i];
sum %= k;
if(m.find(sum)!=m.end() )
{
if(i - m[sum] > 1)
return true;
}
else
m[sum] = i;
}
return false;
}2575. Find the Divisibility Array of a String
We cant keep accumulating next number as it will go beyong range of even long long
Check this
ith number would be (psum10 + ith digit)%m
i+1th digit is [(psum10 + ith digit)10 + i+1th digit]%m
which will be [(psum10 + ith digit)%m ] *10 + i+1th digit
that means we can do a modulo at ith iteration after calculating psum and that will keep psum range in check !
Expand to see Code
vector<int> divisibilityArray(string word, int m) {
int n = word.size();
vector<int> ans(n, 0);
long long psum = 0;
for(int i =0; i < n ; ++i){
psum = psum*10 + (word[i]-'0');
psum %= m;
if(psum==0){
ans[i] = 1;
}
}
return ans;
}2845. Count of Interesting Subarrays
This is mix of couple of problem, first only modulo number considered , this is same as 930 & 1248, so input array can be first converted in binary array.
Secondly insight is same divisibility rule,
1.we add the ith element first
- do modulo
- then check psum -k we have seen in past or not
- To fix negative remainded we do +K and then modulo afterward again.
Expand to see Code
long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
// Step 1: convert input array such that for each
// i : nums[i] % modulo == k
int n = nums.size();
for(int i =0; i < n ; ++i){
nums[i] = (nums[i] % modulo) == k;
}
// After above conversion array will have 1 or 0 only
//Step 2:
// count the 1's
long long cnt = 0;
unordered_map<long long, long long> countMap;
countMap[0] = 1;
long long ans = 0;
for(int i =0; i < n ; ++i){
cnt += nums[i];
cnt %= modulo;
if(countMap.find(((cnt - k + modulo)%modulo)) != countMap.end())
ans += countMap[((cnt - k + modulo)%modulo)];
countMap[cnt]++;
}
return ans;
}Section 3: Prefix Sum & XOR
A quick way to identofy these kind of problems : if it is asking even/odd occurence of something in subarray.
We utilize the property of XOR, that if we count by setting even some bit as the occurence is even , that finaly result of the bit position is 0 otherwise 1.
Lets see this with this sample problem.
1442. Count Triplets That Can Form Two Arrays of Equal XOR
1915. Number of Wonderful Substrings
First thing is input string contain a..j characters and we have these substring(subarray) which has atmost 1 odd character.
Atmost 1 odd means , either 0 odd(everything even) or 1 odd.
At first we will tempted to solve using Sliding window technique becuase the left pointer which voilate the condition at ith index can become a valid candidate in future.
Try dry run with this small example abb, when we encounter 1st b , there are two characters which are odd so rule is voilated and we move left pointer to b but
when we encouter 2nd b then all of sudden abb subarray is valid as a frequency is odd and b is even.
Approach: Take a bitmask and count odd/even only using XOR for each character a...j
Now apply our template where instead of ADD or MODULO we do XOR operation with ith element.
Even Occurence
Next we try to see if this bitmask we have see in past? that means evevything in between cancel out each other and is an even string and should be added to result.
Lets see with example : a0a1b0b1
after process b1, psum which calculated as mask would be 0 and psum[0], we have seen in past when we initialize the hasmap,
in essence this means entire substring from 0 to ith index contains even occurence of whatever characters came thats why they cancel each other in XOR and resultant psum is 0.
At-most 1-odd
Similar Problem:
1542. Find Longest Awesome Substring
Exact same as above with number, remember palindrome property that either frequency has to be even for all character or atmost 1 character can be odd which will be middle element.
Expand to see Code
int longestAwesome(string s) {
int mask =0;
unordered_map<int, int> lenMap;
lenMap[0] = -1;
int ans = 1;
for(int i =0; i< s.size(); ++i){
mask ^= (1 << (s[i]-'0'));
if(lenMap.find(mask)!=lenMap.end())
ans = max(ans, i - lenMap[mask]);
for(int j =0; j <10; ++j){
if(lenMap.find(mask ^ (1 << j))!=lenMap.end())
ans = max(ans, i - lenMap[mask ^ (1 << j)]);
}
if(lenMap.find(mask)==lenMap.end())
lenMap[mask] = i;
}
return ans;
}1371. Find the Longest Substring Containing Vowels in Even Counts
Easier as we dont have to consider odd case also me have to find longest substring, so we have record earlier occurence.
Expand to see Code
int findTheLongestSubstring(string s) {
unordered_map<int, int> lenMap;
lenMap[0] = -1;
int mask =0;
unordered_map<char, int> toIdx;
toIdx['a'] = 0;toIdx['e'] = 1;toIdx['i'] = 2;
toIdx['o'] = 3;toIdx['u'] = 4;
int ans = 0;
for(int i =0; i < s.size() ; ++i){
char c= s[i];
if(c=='a' or c=='e' or c=='i' or
c=='o' or c=='u' )
mask ^= (1 << (toIdx[c]));
auto it = lenMap.find(mask);
if(it!=lenMap.end())
ans = max( ans, i - it->second);
else{
lenMap[mask] = i;
}
}
return ans;
}Section 4: 2D Prefix Sum Problems
Sometime we see problems where we have to do some operations on sub-matrix, like finding max/min in range of matrix or sum.
We use prefix in two dimensional way to find them.
There are two operatiosn : compute prefix sum at next cell (r,c) and also get operation(like sum) between (r1 ,c1) & (r2, c2)
Lets see with an example
Compute psum
psum[i][j] = psum[i-1] [j] + psum[i] [j-1]
if you notice that component [i-1][j-1] is added twice, so we will reduce one part.
psum[i][j] = psum[i-1] [j] + psum[i] [j-1] - psum [i-1][j-1]
and finall add current element.
psum[i+1][j+1] = psum[i+1] [j] + psum[i] [j+1] - psum[i][j] + arr[i][j]
**Size of psum matrix row and column will always be 1 extra. Same we will do while doing a get, so if someone ask
for sum(0,0) , we will actually return sum(1,1) **
Get psum : suppose we have to get psum between sub-matrix (r2 ,c2) & (r3, c3) Yellow painted region.
We have orange region computed with us from earlier section and how to get yellow region out. If we deleted
psum(r1 - 1, c2) and psum (r2 , c1 -1)
Again notice that we are deleting psum[r1 - 1, c1-1) , twice , so adjust that by adding
Notice that above we have stored psum(0,0) actually as psum(1,1), so whatever operation we do, increment r1,c1,r2,c2 by 1 before doing that.
psum[r2] [c2] - psum[r1-1] [c2] - psum[r2][c1-1] + psum[r1-1][c1-1]
304. Range Sum Query 2D - Immutable
Apply knowledge what we learnt above.
Expand to see Code
class NumMatrix {
int m;
int n;
vector<vector<int>> psum;
public:
NumMatrix(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
psum.resize(m+1, vector<int>(n+1, 0));
for(int i =0; i < m ; ++i){
for(int j=0; j < n; ++j){
psum[i+1][j+1] = psum[i+1][j]+psum[i][j+1] +grid[i][j]-psum[i][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return psum[row2+1][col2+1] - psum[row2+1][col1] - psum[row1][col2+1] +psum[row1][col1];
}
};1314. Matrix Block Sum
Same as earlier 2D prefix sum, so here at each cell , we have to form a valid rectangle of size 2k ( k on left, right , up down).
So first compute psum of input matrix.
Then for each grid cell, compute bottom right and top-left co-ordinate of a valid rectangle, and then compute psum in standard 2D way.
Expand to see Code
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size();
int n = mat[0].size();
vector<vector<int>> psum(m+1, vector<int>(1+n, 0));
for(int i =0; i <m; ++i)
for(int j =0; j <n; ++j)
psum[i+1][j+1] = psum[i+1][j]+psum[i][j+1]-psum[i][j]+mat[i][j];
for(int i =0; i < m; ++i)
for(int j =0; j < n; ++j)
{
int r1 = max(i-k, 0);
int c1 = max(j-k, 0);
int r2 = min(i+k+1, m);
int c2 = min(j+k+1, n);
mat[i][j] = psum[r2][c2] - psum[r2][c1] -psum[r1][c2] + psum[r1][c1];
}
return mat;
}
};In this question we are given some empty cells (marked as 0 ), and we are given quadilateral stamp size. Return true if each and every empty cell is covered by some stamp.
Intuition 1: Once you come to a cell, check the polygon of stamp size, if the 2d psum is 0, which means that entire stamping grid is empty and can be stamped.
Now if you stamp it we have to leave some marker that this grid area is stamped, How can we do it quickly.
To understand that we have to learn a trick called Differential Array.
1D Differential Array:
Lets understand with a porblem statement, suppose we have input array [0, 0, 0, 0, 0, 0] and we want to update values in range 1, 4. Then we have 0, 1, 1, 1, 1, 0] here there are multiple update operation and later we have to print tha updated array, how can we do this efficiently for each update ? We create another array called difference array and update index 1 and 5 [0, 1, 0, 0, 0, -1, 0]
Note the size of differential array, 1 more than original array, Why ?
Suppose you have to mark first and last element , you have to mark last+1 and hence 1 extra size of this differential array.
Now if you do psum on this diffential array you get [0, 1, 1, 1, 1, 0, 0]
2D-Diiffential Array :
Not very intutive to get in one go, let me show with an example.
Suppose we have 3 * 3 matrix and we have to update the sub-grid (0,0) to (1,1) , we update following index
[0,0] = 1
[0, 2] = -1 ( size of width which is 2)
[2, 0] = -1 ( size of height is 2)
[2, 2] = 1Updating [0,0] & [0,2] is same as 1-D Difference Array but why we do reverse for [2,0]=-1 and [2,2]=1 ?
Reason is when we update psum pf row=2 we want all those psum to nullify the affect of above row (row=1). I would suggest you do this small example on paper and it will get things clear.
[ 0, 0, 0 ], [1, 0, -1],
[ 0, 0, 0 ], ---> [0, 0, 0 ],
[ 0, 0, 0 ] [-1, 0, 1]Now lets compute psum of the above grid, remember that psum is 1-index and hence we always allocate an extra size for both row and column and update using following way
for(int i = 0; i < m ; ++i){
for(int j =0; j < n ; ++j){
psum[i+1][j+1] = psum[i][j+1] + psum[i+1][j] -psum[i][j] +grid[i][j];Do manually using on a paper and notice we find the exact grid which is stamped i.e.
[0, 0, 0, 0],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 0]Note that psum grid from range (1,1) to (2, 2) actually correpond to stamped area from (0, 0) to (1,1).
So for this problem
- First find the stamp size grid at each cell, and if that grid sum is 0, that mean this grid is empty and can be stamped, place the marker as shown above in another matrix.
- Compute psum of that new matrix.
- For each empty grid cell, compute psum and if it is 0 that means, no one stamped it. return false.
- In the end return true, that means each empty grid is stamped by someone.
Note in below code, I am using stamp vector both for stamping as well as doing prefix sum on it. Hence the size is +2 extra, +1 for Difference Array and +1 for Prefix Sum.
Secondly while iterating the original grid, and once we find a grid of size of stamp, for stamping purpose I am doing +1 to all the co-ordinate as we are operating in psum array.
Expand to see Code
class Solution {
public:
bool possibleToStamp(vector<vector<int>>& grid, int h, int w) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> psum1(1+m, vector<int>(1+n, 0));
auto compute_psum=[&](vector<vector<int>>& grid, vector<vector<int>>& psum){
for(int i =0; i < m ; ++i){
for(int j =0; j < n ; ++j){
psum[i+1][j+1] = psum[i+1][j] + psum[i][j+1] -psum[i][j] + grid[i][j];
}
}
};
auto get_psum=[&](int r1, int c1, int r2, int c2, vector<vector<int>>& psum){
r1++; c1++; r2++; c2++;
return psum[r2][c2] - psum[r2][c1-1] - psum[r1-1][c2] + psum[r1-1][c1-1];
};
compute_psum(grid, psum1);
vector<vector<int>> stamp(m+2, vector<int>(n+2, 0));
for(int i =0; (i+h-1) < m ; ++i){
for(int j =0 ; (j+w-1) < n ; ++j){
//Step 1
if(get_psum(i, j, i +h -1, j + w-1, psum1)==0){
stamp[i+1][j+1]++;
stamp[i+1][j+w+1]--;
stamp[i+h+1][j+1]--;
stamp[i+h+1][j+w+1]++;
}
}
}
//Step 2
for(int i = 1; i <=m ; ++i){
for(int j =1; j<=n ; ++j){
stamp[i][j] += (stamp[i][j-1]+stamp[i-1][j] -stamp[i-1][j-1]);
}
}
for(int i =0; i < m ; ++i){
for(int j =0; j < n ; ++j){
if(grid[i][j]==0 and stamp[i+1][j+1]==0)return false;
}
}
return true;
}
};221. Maximal Square
Strandard psum 2D template , at each grid which is 1 , we assume it as bottom right corner and try to make mimumim of left, up and corner , if all 3 are 1 , that we can form a sqaure here.
Expand to see Code
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> psum(1+m, vector<int>(1+n, 0));
int ans = 0;
for(int i =0; i <m ; ++i){
for(int j =0; j <n ; ++j){
if(matrix[i][j]=='1'){
psum[i+1][j+1] = 1 + min(psum[i+1][j], min(psum[i][j+1], psum[i][j]));
ans = max(ans, psum[i+1][j+1]);
}
}
}
return ans*ans;
}
};2201. Count Artifacts That Can Be Extracted
Mostly same as Range Sum Query above.
Key idea is calculate the rectangular size of artificat by left-top and right-bottom co-ordinates.
and then see if the psum of this rectangular block has same excavation size or not.
If yes that means all block has been excavated and this artifcats can be collected.
Expand to see Code
class Solution {
public:
int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
vector<vector<int>> grid(n, vector<int>(n, 0));
for(auto& d : dig){
grid[d[0]][d[1]] = 1;
}
vector<vector<int>> psum(1+n, vector<int>(1+n, 0));
for(int i =0; i < n ; ++i){
for(int j =0; j < n ; ++j){
psum[i+1][j+1] = psum[i+1][j] + psum[i][j+1] -psum[i][j] + grid[i][j];
}
}
int ans = 0 ;
for(auto& a : artifacts){
int artifact_size = (a[3]-a[1] + 1) * (a[2]-a[0]+1);
int r1 = a[0] + 1;
int c1 = a[1] + 1;
int r2 = a[2] + 1;
int c2 = a[3] + 1; // psum is 1-index
int excavation_size = psum[r2][c2] - psum[r1-1][c2] -psum[r2][c1-1] + psum[r1-1][c1-1];
if(artifact_size==excavation_size){
++ans;
}
}
return ans;
}
};3148. Maximum Difference Score in a Grid
In this problem, we can ask from anywhere but move either right or down.
Score would be calculated as c2-c1 where c2 is new cell and c1 is old cell value.
Suppose we make multiple moves overall score would be.
(c5 -c4) + (c4 - c3) +(c3 - c2) + (c2 -c1)
Notice that each term would cancel each other except first and last, so if we are at agiven grid cell, we need to find minimum c1 so that score can be maximized, so we need to find the minimum number in grid, for example if we are at 14 , we need to find blue or red grid value. Minium in this grid can be calculated using prefix sum(minimum) technique, see code below.
Expand to see Code
class Solution {
public:
int maxScore(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> pmin(1+m, vector<int>(1+n, INT_MAX));
for(int i =1; i <=m ; ++i){
for(int j = 1; j <=n ; ++j){
pmin[i][j] = min({grid[i-1][j-1], pmin[i][j-1], pmin[i-1][j]});
}
}
int ans = INT_MIN;
for(int i=1; i <=m ; ++i){
for(int j=1; j <=n ; ++j){
if(i==1 and j==1) continue;
ans = max(ans, grid[i-1][j-1] - min(pmin[i][j-1], pmin[i-1][j]));
}
}
return ans;
}
};