Monotonic Deque
-
Use: Sliding window max/min in O(1) per step
-
Invariant
- Elements in the deque are monotonic (duplicates allowed)
- Store up to k elements in the deque for window size k
- New elements go to back; expired elements go out from front
-
Idea
-
Maximum in window = keep the largest elements in the deque = decreasing
- For new element, to put in the appropriate positions
- invariant: back >= new element ⇒ pop while !invariant
- recent so fine to discard others
- push new element to back
- invariant: back >= new element ⇒ pop while !invariant
- Maintaining window size k
- If front element is out of window, pop front
- For new element, to put in the appropriate positions
-
Minimum in window = keep the smallest elements in the deque = increasing
- For new element, to put in the appropriate positions
- invariant: back ⇐ new element ⇒ pop while !invariant
- recent so fine to discard others
- push new element to back
- invariant: back ⇐ new element ⇒ pop while !invariant
- Maintaining window size k
- If front element is out of window, pop front
- For new element, to put in the appropriate positions
-
Alternative
Just use a priority queue (max-heap/min-heap) to keep track of max/min in window. Insert {elem,index} pairs and when you query discard elements which are out of window. There will be in total n insertions and n deletions, each O(log k) time.
Often it’ll be easier to think in these terms and then, if needed, optimize to a monotonic deque.
Problems
Sliding Window Maximum
Link: https://leetcode.com/problems/sliding-window-maximum/vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<int> ans;
ans.reserve(n - k + 1);
deque<int> dq;
auto push = [&](int index) {
// 2 steps
// max k => decreasing
// invariant back() > elem so discard while !invariant
while (!dq.empty() && nums[dq.back()] <= nums[index]) // NOTE: elems
dq.pop_back();
dq.emplace_back(index); // NOTE: index here
// maintain k size window
if (dq.front() == index - k) dq.pop_front();
};
for (int i = 0; i < n; i++) {
push(i);
if (i >= k - 1)
ans.emplace_back(nums[dq.front()]); // decreasing so front max
// NOTE: elem again
}
return ans;
}Sliding Window Minimum ( storing values )
Link: https://cses.fi/problemset/task/3221#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n, k, x, a, b, c;
cin >> n >> k >> x >> a >> b >> c;
int x0 = x;
int left_boundary = -1; // sentinel value
deque<int> q; // I need to store the elems this time
auto push = [&](int num) {
// min so q in increasing order
while (!q.empty() && q.back() > num) q.pop_back();
q.emplace_back(num);
// if boundary elem is at front, remove it ( this is where I NEED to keep multiples of same value)
if (q.front() == left_boundary) q.pop_front();
};
int ans = 0;
for (int i = 0; i < n; i++) {
push(x);
if (i >= k - 1) {
ans ^= q.front();
left_boundary = (left_boundary == -1 ? x0 : left_boundary = (a * left_boundary + b) % c);
}
// update x
x = (a * x + b) % c;
}
cout << ans;
}
Razika ( Adhoc + Monotonic Deque )
Link: https://vjudge.net/problem/DMOJ-coci12c4p4#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n, k;
cin >> n >> k;
vector<int> v(n);
for (int& i : v) cin >> i;
sort(v.begin(), v.end());
// idea: sort it
// then you always want to either remove the first elem or the last elem
// as any other won't make sense
// Attempt 1: Greedy
// optim: min{ A_l - A_0 + min{ A_i+1 - A_i } }
// removing from middle only increases the second term and does not help the first one
// removing it from the ends helps the first term
// ^ this was wrong
// 5 2
// 0 11 16 121 130
// by focusing on ends, I miss thatt the middle you should sacrifice an immediate gain
// on the ends to remove a larger gap in the middle
// Attempt 2:
// Property of the optimal solution:
// The final set will be a contiguous subarray of the sorted array
// Proof:
// Suppose not, then there exists A_i and A_j in the final set
// such that i < k < j and A_k is not in the final set
// Then, we can replace A_i or A_j with A_k to get a smaller difference
// solution: min{ all n-k length windows }
const int INF = (int)1e18;
int ans = INF;
int win = n - k;
deque<int> dq; // we will use the n-k-1 length d_i = a_i-a_i-1 deque to find min in O(1)
auto push = [&](int x, int left_boundary) { // value based
while (!dq.empty() && dq.back() > x) dq.pop_back();
dq.push_back(x);
if (dq.front() == left_boundary) dq.pop_front();
};
for (int i = 0; i < n; i++) {
int win_first_idx = i - win + 1;
int left_boundary = INF;
if (win_first_idx > 0) left_boundary = v[win_first_idx] - v[win_first_idx - 1];
if (i) push(v[i] - v[i - 1], left_boundary);
if (win_first_idx >= 0) {
int current_diff = v[i] - v[win_first_idx];
int min_gap = dq.front();
ans = min(ans, current_diff + min_gap);
}
}
cout << ans << "\n";
}Shortest subarray with sum at least K ( unique idea )
Link: https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k
Very unique idea based on two observations.
int shortestSubarray(vector<int>& nums, int k) {
// attempt 1: keep on increasing r untill sum>=k
// keep on increasing l such that sum>=k
// this is a candidate subarray
// ^ is wrong
// 1 2 3 -100 20 20 20 -100 1 2 3
// if you keep on moving right till sum>=k
// you absorb large losses and won't stop till the end
// attempt 2: if I just move r by +1
// at the rightmost 20, if I match exactly and l = 0
// then I won't increase l as now sum < k
// but I ignore that moving ahead can possible remove a
// very large negative aborbed
// idea: operator on prefix sums
// iterate all ends j
// for any i < j, if there's a k s.t. i < k < j
// and if P(k)<P(i), i is never a candidate as
// so as indices increase, if you find a new lower P(i)
// discard any older with a higher P(i)
// so P(i) must increase ( strictly )
// monotonic dq except indices and vals are inverted
// for any dq.front() index that has satisfied the condition
// of >=k sum, you can discard it forever because
// if it was ever to be used again it will give a longer
// array
// also since p(i) is increasing if the first one
// does not satisfy, nothing other will
int n = nums.size();
vector<long long> p(n + 1, 0);
deque<int> dq;
int ans = n + 1;
auto push = [&](int idx) {
// NOTE: if you use a priority queue here instead of dq
// you don't have to do this next loop as no monotonicity
// needs to be maintained
// the solution then just needs one observation:
// in my pq I have all previous prefix sums
// and I iterate by the smallest ones that satify
// whichever are satified, are never needed again
while (!dq.empty() && p[dq.back()] >= p[idx]) dq.pop_back();
dq.emplace_back(idx);
// boundary discard, except this is not fixed
// length
while (!dq.empty() && p[idx] - p[dq.front()] >= k) {
ans = min(ans, idx - dq.front());
dq.pop_front();
}
};
push(0);
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] + nums[i - 1];
push(i);
};
if (ans == n + 1) ans = -1;
return ans;
}K Empty Slots (inversion idea)
Link: https://leetcode.ca/all/683.htmlA naive approach is to use simulate it day by day using delta encoding and a fenwick tree to check for each bulb you turn on, if the prefix sum at k distance on any side is 0.
Though inversion idea is more elegant. Consider on(i) as day when bulb i turns on and then iterate over each bulb ( assume i is the right end ). Then for the k length segment the left of i, if min of that range
is > both of the on ends, then that segment is valid candidate answer.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> bulbs(n + 1);
for (int i = 1; i <= n; i++) cin >> bulbs[i];
// bulb i is turned on at day bulbs[i]
vector<int> days(n + 1);
for (int i = 1; i <= n; i++) {
days[bulbs[i]] = i;
}
deque<int> dq;
int win = k + 2; // k + thw two ends
auto push = [&](int index) {
// min so must be increasing
while (!dq.empty() && days[dq.back()] >= days[index]) {
dq.pop_back();
}
dq.push_back(index);
if (dq.front() == index - k)
dq.pop_front();
};
int ans = n + 1;
for (int i = 1; i <= n; i++) {
if (i >= win) {
int range_min = days[dq.front()];
int last_on = max(days[i - win + 1], days[i]);
if (range_min > last_on) {
ans = min(ans, last_on);
}
}
push(i); // push after the check so lagged by 1
}
if (ans == n + 1) ans = -1;
cout << ans;
}Maximum subarray size with difference atmost k ( non fixed window with separate boundary handling )
Link: https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/int longestSubarray(vector<int>& nums, int limit) {
int n = nums.size();
deque<int> mx_dq, mn_dq;
// non fixed length variation, basicaly since you pop based on
// "my left is this index, you need to store indexes"
// and I only need to store indexes where elems are increasing ( strictly )
// case 4 4 1, when I'm at 1 (elem), l is 0 and my constrant is violated
// I need to pop till the very last index with that value so only store the
// last
// duplicates works as well though
auto push = [&](deque<int>& dq, int idx, auto should_pop) {
while (!dq.empty() && should_pop(nums[dq.back()], nums[idx]))
dq.pop_back();
dq.emplace_back(idx);
};
auto rem_idx = [&](int idx) {
if (!mx_dq.empty() && mx_dq.front() == idx)
mx_dq.pop_front();
if (!mn_dq.empty() && mn_dq.front() == idx)
mn_dq.pop_front();
};
// iterating on the right boundary
int len = 1;
int l = 0; // what's good left
for (int r = 0; r < n; r++) {
push(mx_dq, r, [](int q_last, int elem) { return q_last <= elem; });
push(mn_dq, r, [](int q_last, int elem) { return q_last >= elem; });
while (nums[mx_dq.front()] - nums[mn_dq.front()] > limit) {
rem_idx(l++);
// must hold as one element range
assert(!mx_dq.empty());
assert(!mn_dq.empty());
};
assert(l <= r);
len = max(len, r - l + 1);
}
return len;
}Count of subarray partitions with max - min <= k ( another one similar to prev except sum with dp and prefix sum optim )
Link: https://leetcode.com/problems/count-partitions-with-max-min-difference-at-most-k/int countPartitions(vector<int>& nums, int k) {
#define int long long
// for each i
// find the smallest j<=i that it's valid range
// now any partition of k..i where k>=j is also valid
// for each of those you add f(k-1) to the ans
// f(i) = no of ways to partition prefix ending at i
const int mod = (int)1e9 + 7;
int n = nums.size();
deque<int> mx_dq, mn_dq;
auto push = [&](auto& dq, int idx, auto should_pop) {
while (!dq.empty() && should_pop(idx, dq.back())) dq.pop_back();
dq.emplace_back(idx);
};
auto rem_idx = [&](int idx) {
if (!mx_dq.empty() && mx_dq.front() == idx) mx_dq.pop_front();
if (!mn_dq.empty() && mn_dq.front() == idx) mn_dq.pop_front();
};
vector<int> pref(n + 1), dp(n + 1);
pref[0] = dp[0] = 1;
int j = 0;
for (int i = 0; i < n; i++) {
push(mx_dq, i, [&](int idx, int q_back) { return nums[idx] >= nums[q_back]; });
push(mn_dq, i, [&](int idx, int q_back) { return nums[idx] <= nums[q_back]; });
// pop while range is invalid
assert(!mx_dq.empty());
assert(!mn_dq.empty());
auto valid = [&]() {
return nums[mx_dq.front()] - nums[mn_dq.front()] <= k;
};
while (!valid()) rem_idx(j++);
assert(j <= i); // single elemen is always valid
// for all k = j..i, add dp(k-1), range of dp sums is then j-1...i-1 => j+i in pref array => pref[i] - pref[j-1]
(dp[i + 1] = pref[i] - (j ? pref[j - 1] : 0) + mod) %= mod; // pref sums are increasing but %mod is not increasing so u need to add mod
(pref[i + 1] = pref[i] + dp[i + 1]) %= mod;
}
return dp.back();
#undef int
}Count subarrays with prime max - prime min <= k ( some tricky edge cases )
Link: https://leetcode.com/problems/count-prime-gap-balanced-subarraysint primeSubarray(vector<int>& nums, int k) {
// for each i
// find the smallest j<=i that it's valid range
// now any partition of k..i where k>=j is also valid
// for each of those you add f(k-1) to the ans
// f(i) = no ofways to partition prefix ending at i
const int N = (int)5e4 + 10;
vector<int> compo(N);
compo[1] = 1;
for (int i = 2; i < N; i++)
for (int j = i + i; j < N; j += i) compo[j] = 1;
int n = nums.size();
deque<int> mx_dq, mn_dq, all_primes;
auto push = [&](auto& dq, int idx, auto should_pop) {
while (!dq.empty() && should_pop(idx, dq.back())) dq.pop_back();
dq.emplace_back(idx);
};
auto rem_idx = [&](int idx) {
if (!mx_dq.empty() && mx_dq.front() == idx) mx_dq.pop_front();
if (!mn_dq.empty() && mn_dq.front() == idx) mn_dq.pop_front();
if (!all_primes.empty() && all_primes.front() == idx) all_primes.pop_front();
};
int ans = 0, j = 0;
for (int i = 0; i < n; i++) {
if (!compo[nums[i]]) {
push(mx_dq, i, [&](int idx, int q_back) { return nums[idx] >= nums[q_back]; });
push(mn_dq, i, [&](int idx, int q_back) { return nums[idx] <= nums[q_back]; });
all_primes.push_back(i);
}
// pop while range is invalid
auto valid = [&]() {
// longest is better
return mx_dq.empty() || mn_dq.empty() || nums[mx_dq.front()] - nums[mn_dq.front()] <= k;
};
while (j <= i && !valid()) rem_idx(j++);
if ((int)all_primes.size() >= 2) {
int last = all_primes[(int)all_primes.size() - 2];
// j to last is valid
if (j <= last)
ans += last - j + 1;
}
}
return ans;
}Number of subarrays with max - min <= 2 ( in similar vein as previous )
Link: https://leetcode.com/problems/continuous-subarrays/
long long continuousSubarrays(vector<int>& nums) {
// observation:
// rephrase: max - min of the subarray <= 2
// a usual solution with 2 deques, one for max and one for min and iterating over all ends is evident
// observation: once you discard and l, it is not longer ever needed by any subsequent r
// this is the usual dq observation
deque<int> mx_dq, mn_dq;
auto push = [&](auto& dq, int idx, auto should_pop) {
while (!dq.empty() && should_pop(nums[dq.back()], nums[idx]))
dq.pop_back();
dq.emplace_back(idx);
};
auto rem_idx = [&](int idx) {
if (mx_dq.front() == idx) mx_dq.pop_front();
if (mn_dq.front() == idx) mn_dq.pop_front();
};
long long ans = 0;
int n = nums.size();
int l = 0;
for (int i = 0; i < n; i++) {
// i is my end
push(mx_dq, i, [](int q_last, int cur) { return q_last <= cur; });
push(mn_dq, i, [](int q_last, int cur) { return q_last >= cur; });
// validate start
while (l <= i) // if just 1 elem we always satisfy
{
// you can also use that if dq_front violates, you jump right off to mx_dq.front()+1 but nothing really gained asymptotically
bool ok = (mx_dq.empty() || abs(nums[mx_dq.front()] - nums[i]) <= 2) && (mn_dq.empty() || abs(nums[mn_dq.front()] - nums[i]) <= 2);
if (!ok)
rem_idx(l++);
else
break;
};
assert(l <= i);
ans += (i - l + 1);
}
return ans;
}First note the use of lambdas and autos. auto is quite verstatile. Note that I do not optimise my jumps, which seems to be a quite good constant factor optimisation so much so that even a map based solution using that is much faster.
long long continuousSubarrays(vector<int>& nums) {
map<int, int> m;
long long res = 0;
for (int i = 0, j = 0; i < nums.size(); ++i) {
auto [it, inserted] = m.insert({nums[i], i});
if (!inserted)
it->second = i;
else {
for (auto it1 = begin(m); nums[i] - it1->first > 2;) {
j = max(j, it1->second + 1);
m.erase(it1++);
}
for (auto it1 = prev(end(m)); it1->first - nums[i] > 2;) {
j = max(j, it1->second + 1);
m.erase(it1--);
}
}
res += i - j + 1;
}
return res;
}Maximum number of robots within budget ( simple two pointer that uses deque to get max withing the two pointer window )
Link: https://leetcode.com/problems/maximum-number-of-robots-within-budget/int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
#define int long long
// observation if for some j..i range, j is dicarded it is dicarded forever
// I can do two points, for each r, increase l but I need to do range max
// for which I can use dq
int n = chargeTimes.size();
vector<int> pref(n);
pref[0] = runningCosts[0];
for (int i = 1; i < n; i++) pref[i] = pref[i - 1] + runningCosts[i];
deque<int> q;
auto push = [&](int i) {
// max so decreasing
while (!q.empty() && chargeTimes[q.back()] <= chargeTimes[i]) q.pop_back();
q.emplace_back(i);
};
int l = 0, ans = 0;
for (int r = 0; r < n; r++) {
push(r);
// increase l while l<=r and we are out of budget
auto cur_budget = [&]() {
int k = r - l + 1;
return chargeTimes[q.front()] + k * (pref[r] - (l ? pref[l - 1] : 0));
};
while (l <= r && cur_budget() > budget) {
if (q.front() == l) q.pop_front();
l++;
};
if (l <= r) {
ans = max(ans, r - l + 1);
}
}
return ans;
#undef int
}Number of subarrays that can be made increasing in k operations ( start from reverse trick )
Link: https://leetcode.com/problems/count-non-decreasing-subarrays-after-k-operationslong long countNonDecreasingSubarrays(vector<int>& nums, int k) {
#define int long long
// rephrase:
// sum over subarrays { 1 if can be make increasing in k ops else 0 }
// observation 1
// consider j..i
// if I can make this increasing then I can make any of the subarray of this subarray increasing
// hence I only need to consider for an i, the min j s.t. I can still make it increasing
// observation 2
// j..i, if a j is discarded it is dicarded forever, there is no j..i+1 that can be valid
// can I maintain a queue, such that for the element in j..i, I can answer if I can make it increasing
// 1 elem => 0 inc
// adding one after, need max(0,range_max-new_elem)
// think of a high water mark based approach, store each high starts in a dq
// ^ this above was too complicated
// observation:
// process j from right to left
// a larger on the left is trivial to flood
// removal from right is free
int n = nums.size();
deque<int> dq;
dq.push_back(n - 1);
// my range is i..right
int right = n - 1, ans = 1, cur_cost = 0;
for (int i = n - 2; i >= 0; i--) {
// dq stores high marks from left to right of the current i..right
// push in i and update costs
while (!dq.empty() && nums[i] > nums[dq.front()]) {
int popped = dq.front();
dq.pop_front();
int flood_till = dq.empty() ? right : dq.front() - 1;
int elems = flood_till - popped + 1; // elems bw this and the next front, note that the first elem in my range is always the first leader
cur_cost += elems * (nums[i] - nums[popped]);
// for 10 (cur ) | 3.... 5 ... 7... as my dq
// what range was 3, what range was 5, what range was 7, we look between current front and the next front and look at delta_costs
}
dq.push_front(i);
// shrink right
while (cur_cost > k) {
// dq.back() is the one that decides that the value at right is to make it increasing
cur_cost -= (nums[dq.back()] - nums[right]);
if (dq.back() == right) dq.pop_back();
right--;
}
ans += (right - i + 1);
}
return ans;
#undef int
}Problems ( as DP optimisations )
Max subsequence sum with elements at max k distance apart
int constrainedSubsetSum(vector<int>& nums, int k) {
const int INF = (int)2e9;
int n = nums.size();
deque<int> dq;
vector<int> dp(n, -INF);
auto push = [&](int idx) {
// max so decreasing
while (!dq.empty() && dp[dq.back()] <= dp[idx])
dq.pop_back();
dq.emplace_back(idx);
if (dq.front() == idx - k)
dq.pop_front();
};
// f(i) = ans for subarray[0..i] s.t. you pick i
// f(i) = nums[i] + max( 0, f(j) | j = [i-k,i-1] )
for (int i = 0; i < n; i++) {
dp[i] = nums[i] + max(dq.empty() ? -INF : dp[dq.front()], 0);
push(i);
}
return *max_element(dp.begin(), dp.end());
}Max Value of equation ( variable window max, adhoc )
Link: https://leetcode.com/problems/max-value-of-equation/int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
int n = points.size();
// the expression if you iterate over x(i) in inc order s.t i<j, is
// yi-xi+yj+xj observation: if some i,j pair don'st satisfy the
// constraint xj-xi<=k, you can discard it forever as any other xj ahead
// of it > current xj and won't satify as well ( this is my discard
// condition ) now I just need the max{ yi-xi } in the window
auto idx_val = [&](int idx) { return points[idx][1] - points[idx][0]; };
deque<int> dq;
auto push = [&](int idx) {
// max so dec
// no duplicates needed here
while (!dq.empty() && idx_val(dq.back()) <= idx_val(idx))
dq.pop_back();
dq.emplace_back(idx); // increasing indexes
};
auto del = [&](int idx) {
if (!dq.empty() && dq.front() == idx)
dq.pop_front();
};
const int INF = (int)2e9;
int ans = -INF;
push(0);
for (int r = 1; r < n; r++) {
// clean up, dependent on r
while (!dq.empty() && points[r][0] - points[dq.front()][0] > k)
del(dq.front());
if (!dq.empty())
ans = max(ans, idx_val(dq.front()) + points[r][0] + points[r][1]);
push(r);
}
assert(ans != -INF); // problem asserts
return ans;
}Delivering boxes from storage to ports (:star:)
Link: https://leetcode.com/problems/delivering-boxes-from-storage-to-ports/This was a very tricky one, so you start with the DP formulation
is simply how many times does the port change sequetially, +2 is for the storate to first port and last port to storage.
Now note that the inner loop i basically so you can basically maintain the minimums in a priority_queue as the first solution.
int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
#define int long long
int n = boxes.size();
vector<int> trips(n), pref(n);
pref[0] = boxes[0][1];
trips[0] = 0;
for (int i = 1; i < n; i++) {
trips[i] = trips[i - 1] + (boxes[i][0] != boxes[i - 1][0]);
pref[i] = pref[i - 1] + boxes[i][1];
}
/*
dp(i) = trips[i] + (- trips[j-1] + dp[j-1] for window start at j )
this can be parameterised over j
*/
vector<int> dp(n);
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> pq; // max value, index of start window
pq.push({0, 0}); // 0 max value of dp(-1) - trips(-1), index 0
for (int i = 0; i < n; i++) {
// if just this i..i is the segment you need to push that
if (i)
pq.push({dp[i - 1] - trips[i], i});
// always pick the best but dicard what's not possible first
while (true) {
assert(!pq.empty());
auto [_, j] = pq.top();
// is j to i good
int wt = pref[i] - (j ? pref[j - 1] : 0);
bool ok = (i - j + 1 <= maxBoxes && wt <= maxWeight);
if (!ok) {
pq.pop();
} else {
break;
}
}
assert(!pq.empty());
auto [mn_val, _] = pq.top();
dp[i] = trips[i] + mn_val + 2;
}
return dp[n - 1];
#undef int
}Once this is done, optimise to deqeue by noting the additional observation that if some j..i window is bad, there can be no further i’ > i where j..i’ is good, so once a left boundary is invalidated, it can be discarded forever. This gives you a sliding window minimum structure.
int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
#define int long long
int n = boxes.size();
vector<int> trips(n), pref(n);
pref[0] = boxes[0][1];
trips[0] = 0;
for (int i = 1; i < n; i++) {
trips[i] = trips[i - 1] + (boxes[i][0] != boxes[i - 1][0]);
pref[i] = pref[i - 1] + boxes[i][1];
}
/*
dp(i) = trips[i] + (- trips[j-1] + dp[j-1] for window start at j )
this can be parameterised over j
*/
vector<int> dp(n);
deque<int> dq;
auto val_at = [&](int i) {
return (i ? dp[i - 1] : 0) - trips[i];
};
auto push = [&](int i) {
int val = val_at(i);
// min so increasing
while (!dq.empty() && val_at(dq.back()) >= val) dq.pop_back();
dq.emplace_back(i);
};
for (int i = 0; i < n; i++) {
// if just this i..i is the segment you need to push that
push(i);
while (true) {
assert(!dq.empty());
int j = dq.front();
// is j to i good
int wt = pref[i] - (j ? pref[j - 1] : 0);
bool ok = (i - j + 1 <= maxBoxes && wt <= maxWeight);
if (!ok) {
dq.pop_front();
} else {
break;
}
}
assert(!dq.empty());
dp[i] = trips[i] + val_at(dq.front()) + 2;
}
return dp[n - 1];
#undef int
}If you can make an “implicit” array of ( parameterised by i ) and maintain its minimas that is the dp optimisation here.
Jump Game VI ( fixed length window max as dp optim )
int maxResult(vector<int>& v, int k) {
int n = v.size();
vector<int> dp(n);
deque<int> q;
auto push = [&](int idx) {
// max so dec, no need to keep equals as well
while (!q.empty() && dp[idx] >= dp[q.back()]) q.pop_back();
q.push_back(idx);
// can just clean up here as boundary is "fixed"
if (q.front() == idx - k) q.pop_front();
};
// f(i) = max score st I am at i, so v(i) is always there
// f(i) = v(i) + max f(j) | j=i-k..i-1
for (int i = 0; i < n; i++) {
dp[i] = v[i] + (q.empty() ? 0 : dp[q.front()]);
push(i);
}
return dp.back();
}Minimum number of coins for fruits ( a minor variation over jump game 6 )
Link: https://leetcode.com/problems/minimum-number-of-coins-for-fruits
int minimumCoins(vector<int>& v) {
// rephrase:
// for cost(i) I can jump from i, next i => i+i, what is min cost to jump till n-1
// now this is similar to jump game 6 except min
// NOTE: problem description is incorrect, if you take the i index fruit, you can
// takee the next i+1 fruits for free
/*
f(i) = I'm at i, where can I jump from => j+j+1>=i => j >= (i-1)/2 => j >= i//2
f(i) = min dp(j-1) + cost(j) | j=(i+2)//2..i-1
f(0) = cost(0)
*/
int n = v.size();
vector<int> dp(n);
deque<int> q;
auto val_at = [&](int idx) {
return v[idx] + (idx ? dp[idx - 1] : 0);
};
auto push = [&](int idx) {
// min so inc, no need to keep equals as well
int cur_val = val_at(idx);
while (!q.empty() && cur_val <= val_at(q.back())) q.pop_back();
q.push_back(idx);
};
for (int i = 0; i < n; i++) {
push(i);
// invalid vals
int valid_start = i / 2;
while (!q.empty() && q.front() < valid_start) q.pop_front();
dp[i] = val_at(q.front());
}
return dp.back();
}Maximum partitions such that sum is increasing ( dp with additional state HARD )
Link: https://leetcode.com/problems/find-maximum-non-decreasing-array-lengthNote that is increasing. Trick here is to observe the greedy that for the same maximum , it’s always better to have the smallest last partition sum .
O(n^2)
int findMaximumLength(vector<int>& nums) {
// rephrase
// op => any subarray => sum(subarray)
// max len of increasing ( non strict ) array after any number of such ops
// properties of the optimal solution
// (a...)(b...)(c...) is optimal, unfolding...
// sum(a...) <= sum(b...) <= sum(c...)
// maximum no of partitions I can make such that the sums are increasing
// greedy properties, you DON'T want to merge as it decreases length
// attempt: binary search? I don't think that applies here
// f(i) => solution for 0..i
// when I'm at i, I can choose to merge j..i s.t sum(j..i) >= parition ending at j-1 if you consider 0..j-1, lest this be last(j-1)
// greedy => for the same length, you want the last(j) to be as small as possible
// also note f(i) is increasing, f(i+1)>=f(i) as the numbers are >0 so you can just take f(i) and merge in nums[i+1] to get a plausible f(i+1)
int n = nums.size();
vector<int> pref(n);
pref[0] = nums[0];
for (int i = 1; i < n; i++)
pref[i] = pref[i - 1] + nums[i];
vector<int> dp(n);
vector<int> last(n);
dp[0] = 1;
last[0] = nums[0];
for (int i = 1; i < n; i++) {
dp[i] = dp[i - 1]; // always possible
last[i] = last[i - 1] + nums[i];
// j..i is my merge
for (int j = 0; j <= i; j++) {
// note that increasing j is guaranteed to give you a smaller last(i) as positive elements
int sum = pref[i] - (j ? pref[j - 1] : 0);
int prev_part = (j ? last[j - 1] : 0);
if (sum >= prev_part) {
int tans = 1 + (j ? dp[j - 1] : 0);
if (tans > dp[i]) {
dp[i] = tans;
last[i] = sum;
} else if (tans == dp[i]) {
last[i] = min(last[i], sum);
}
}
}
}
return dp.back();
}Split condition for j..i is
Also note that by monotonicity of , we want the maximum that satisfies this condition, this can be made an implict array with cost(i) = sum(i-1) + last(i-1) and we want to find the maximum j s.t. cost(j) ⇐ sum(i).
Also, note that so maximising j also minimises last(i) for the same f(i).
int findMaximumLength(vector<int>& nums) {
#define int long long
int n = nums.size();
vector<int> pref(n);
pref[0] = nums[0];
for (int i = 1; i < n; i++)
pref[i] = pref[i - 1] + nums[i];
vector<int> dp(n);
vector<int> last(n);
// cost(i) = dp(i) + pref(i);
const int INF = (int)1e18;
deque<int> dq;
auto val_at = [&](int idx) {
if (idx == 0) return -INF; // you can treat last(i) as -INF
return pref[idx - 1] + last[idx - 1];
};
auto push = [&](int idx) {
int cur_val = val_at(idx);
// in my q, I want to satisfy cost(i) <= pref[i] so keep mins
// and then discard
// min so inc
while (!dq.empty() && val_at(dq.back()) >= cur_val) dq.pop_back();
dq.emplace_back(idx);
};
// observation: once some j is popped for some j..i, it's never needed again
for (int i = 0; i < n; i++) {
push(i); // i..i
// if after popping, the next_element still satisfies the contraints, I should use that and discard current
// I'm trying to find max j s.t cost <= pref[i]
auto can_pop = [&]() {
return dq.size() > 1 && pref[i] >= val_at(dq[1]);
};
while (!dq.empty() && can_pop()) dq.pop_front();
assert(!dq.empty()); // 0 would never be popped
int j = dq.front();
last[i] = pref[i] - (j ? pref[j - 1] : 0);
dp[i] = 1 + (j ? dp[j - 1] : 0);
}
// summarising
// f(i) = max(1, f(j) + 1) | j = max j in 0..i s.t. j..i is valid partition => pref(i) - pref(j-1) >= last(j-1)
return dp.back();
#undef int
}Problem ( as binary search optimisation )
Maximum number of tasks you can assign ( montone window to pick max and min of candidates )
https://leetcode.com/problems/maximum-number-of-tasks-you-can-assignint maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
#define int long long
/*
observation: easiest tasks should be done first as if an easy task cannot be done then no hard task can be done as well
observation: pick the easiest task and the worst worker, if cannot do, try giving a pill, if the pill works you get 1 extra
task for you pill, note that pill should only be given if the task is failing. Saving the pill is never good as this is an
equivalent exchange, if if there was some other choice that too would give just one extra task being done by using the pill
WRONG: as you are wasting the "extra strength"
Case: tasks : 5 6, workers: 4 5, pill => 1 of strength 2
matching t5 with w4+p2 is just one task, instead match t5 with w5 and use pill to complete the other task
observation: attempt to parameterise by k => for k tasks
pick easiest k tasks and strongest k workers
each task "must" be assigned so now if you pick the easiest and the weakest of the k, and if failing, use the weakest of pills ( tougher variation ) that is
just enough to get the task done, that is optimal
WRONG: as for the same case as above
observation: since each task needs to be done, let's start with the hardest task
I should save the pill and pick the strongest worker for it
if I need to use the pill, I should not waste the strongest worker and pick the weakest one that can do it with the pill
*/
int n = tasks.size(), m = workers.size();
int l = 0, r = min(n, m);
int ans = -1;
sort(tasks.begin(), tasks.end());
sort(workers.begin(), workers.end());
auto ok = [&](int k) {
// can I do k tasks
int cur_pills = pills;
deque<int> dq;
int wi = m - 1;
for (int i = k - 1; i >= 0; i--) {
int t = tasks[i];
// at any instant dq stores sorted list of workers who can do task(i) with/without pill
while (wi >= m - k && workers[wi] + strength >= t) dq.push_front(wi--);
if (dq.empty()) return false; // can't do
if (workers[dq.back()] >= t) {
dq.pop_back(); // strongest one that can do the task, since we have to do "all tasks" this is correct
// hardest task to the strongest, if it's not possible to map all k, then choosing anything else here is bad as it is
} else {
if (cur_pills > 0) {
cur_pills--;
dq.pop_front();
} else {
return false;
}
}
}
return true;
};
while (l <= r) {
int mid = l + (r - l) / 2;
if (ok(mid)) {
l = mid + 1;
ans = mid;
} else {
r = mid - 1;
}
}
return ans;
#undef int
}Observations
- If it’s not a fixed length window, you usually need a different function to remove expired elements as the condition is kind of adhoc
Monotonic Stack
A monotonic stack is “half” of a monotonic deque. You don’t have the pop_front and that’s all.
A generic implementation:
Variation 1 : The Candiate List approach
auto monotonic_stack_idx = [](const auto& arr, auto first, auto last, auto should_pop) {
int n = arr.size();
vector<int> res(n, -1);
vector<int> st;
for (auto it = first; it != last; ++it) {
while (!st.empty() && should_pop(arr[st.back()], *it)) {
st.pop_back();
}
int i = &(*it) - arr.data(); // can't just use - arr.start due to rev_pointer, I always want the distance ftom arr start
// deference pointer, get the elem address, arr.data() is arr start address
if (!st.empty()) res[i] = st.back(); // you can use top now
st.push_back(i);
}
return res;
};Variation 2 : The Waiting Room approach
auto monotonic_stack_idx = [](const auto& arr, auto first, auto last, auto should_pop) {
int n = arr.size();
vector<int> res(n, -1);
vector<int> st;
for (auto it = first; it != last; ++it) {
int current_idx = &(*it) - arr.data();
// WAITING ROOM LOGIC:
// While stack is not empty and current element resolves the waiting element
// (i.e., current > arr[stack_top])
while (!st.empty() && should_pop(arr[st.back()], *it)) {
int waiting_idx = st.back();
st.pop_back();
res[waiting_idx] = current_idx;
}
st.push_back(current_idx);
}
return res;
};Modern C++ should_pop : the signature is bool should_pop(T stack_last, T cur) where T is the type of elements in arr.
Want greater ⇒ pop when stack_last <= cur ⇒ should pop is std::less_equal<T>()
Want smaller ⇒ pop when stack_last >= cur ⇒ should pop is std::greater_equal<T>()
You can discard the equals if you want strict monotonicity.
A chain of thought to remember: I want the first greater to left, so I want to keep popping while the stack top is less than or equal to current. Observation, if my current number is larger than the stack top, the stack top can never be the answer for any future element as well, so pop it. This keeps a mono decreasing stack.
You send in reverse iterators when you want the next element (higher or lower) to the right.
Problems
Next greater element in circular array
Link: https://leetcode.com/problems/next-greater-element-ii/You can loop twice since these are elements and not sum.
vector<int> nextGreaterElements(vector<int>& nums) {
auto monotonic_stack_idx = [](const vector<int>& arr) {
int n = arr.size();
vector<int> res(n, -1);
vector<int> st;
for (int idx = 2 * n - 1; idx >= 0; idx--) {
int i = (idx >= n ? idx - n : idx);
while (!st.empty() && arr[st.back()] <= arr[i]) {
st.pop_back();
}
if (!st.empty()) res[i] = st.back(); // you can top top now
st.push_back(i);
}
return res;
};
auto ngr = monotonic_stack_idx(nums);
int n = nums.size();
vector<int> ans(n);
for (int i = 0; i < n; i++) {
ans[i] = ngr[i];
if (ans[i] != -1) ans[i] = nums[ans[i]];
}
return ans;
}Max - min over all ranges
long long subArrayRanges(vector<int>& arr) {
// rehphrase:
// max - min over all subarray ranges
// observation: can use the "linearity" trick
// sum over max - min = sum over max - sum over min for all ranges
// for each element I need to find, how many ranges would this element be the max of and the min of
// can use first smaller eq and first greater equal to left and right
// handling duplicates is hard
// use the asymmetric stack trick
// say when you look to left you consider equal ones in range
// but right you exclude the equal ones
auto monotonic_stack_idx = [](const auto& arr, auto first, auto last, auto should_pop) {
int n = arr.size();
vector<int> res(n, -1);
vector<int> st;
for (auto it = first; it != last; ++it) {
int i = &(*it) - arr.data();
// Pop while invariant is violated
while (!st.empty() && should_pop(arr[st.back()], *it)) {
st.pop_back();
}
if (!st.empty()) res[i] = st.back();
st.push_back(i);
}
return res;
};
int n = arr.size();
auto sml_left = monotonic_stack_idx(arr, arr.begin(), arr.end(), greater_equal<int>());
auto sml_right = monotonic_stack_idx(arr, arr.rbegin(), arr.rend(), greater<int>());
auto gt_left = monotonic_stack_idx(arr, arr.begin(), arr.end(), less_equal<int>());
auto gt_right = monotonic_stack_idx(arr, arr.rbegin(), arr.rend(), less<int>());
#define int long long
int ans = 0;
for (int i = 0; i < n; i++) {
// what range would this element be the min in
int left = sml_left[i] == -1 ? 0 : sml_left[i] + 1;
int right = sml_right[i] == -1 ? n - 1 : sml_right[i] - 1;
if (left <= i && i <= right) ans -= arr[i] * (i - left + 1) * (right - i + 1);
// what would this be max of
left = gt_left[i] == -1 ? 0 : gt_left[i] + 1;
right = gt_right[i] == -1 ? n - 1 : gt_right[i] - 1;
if (left <= i && i <= right) ans += arr[i] * (i - left + 1) * (right - i + 1);
}
return ans;
#undef int
}Max + min over all subrrays of len at max k
Similar to previous except the k bound is a subproblem in itself. Subproblem: for (i..k..j) what is the number of ranges with length ⇐ len and containing k index ( note k is not the k in problem here )
long long minMaxSubarraySum(vector<int>& arr, int k) {
// observation
// relate to another problem that was sum of max - min over all ranges instead of just k length
// this additional constraint is range must be at max k
// now this is easy to handle as you can just limit the start and end to be within that k range
// each element within this range
#define int long long
auto monotonic_stack_idx = [](const auto& arr, auto first, auto last, auto should_pop) {
int n = arr.size();
vector<int> res(n, -1);
vector<int> st;
for (auto it = first; it != last; ++it) {
int i = &(*it) - arr.data();
// Pop while invariant is violated
while (!st.empty() && should_pop(arr[st.back()], *it)) {
st.pop_back();
}
if (!st.empty()) res[i] = st.back();
st.push_back(i);
}
return res;
};
int n = arr.size();
auto sml_left = monotonic_stack_idx(arr, arr.begin(), arr.end(), greater_equal<int>());
auto sml_right = monotonic_stack_idx(arr, arr.rbegin(), arr.rend(), greater<int>());
auto gt_left = monotonic_stack_idx(arr, arr.begin(), arr.end(), less_equal<int>());
auto gt_right = monotonic_stack_idx(arr, arr.rbegin(), arr.rend(), less<int>());
auto count_solns = [](int xbound, int ybound, int s) {
// no of solns for x + y <= s where x in [0,xbound] and y in [0,ybound]
auto f = [](int a) {
if (a < 0) return 0ll;
// solns for x+y<=a, unbounded
// idea is to add a slack : x + y + slack = a
// now this is starts and bars, divided a into 3 bins >=0 allowed in each
// a+3-1 choose 3-1 => a + 2 choose 2
return (a + 2) * (a + 1) / 2;
};
int ans = f(s) // all solutions
- f(s - xbound - 1) // where x > xbound, change to x' = x + xbound+1, and now x>=0 again
- f(s - ybound - 1) // where y > bounds
+ f(s - xbound - ybound - 2); // add where both > bounds
return ans;
};
int ans = 0;
for (int i = 0; i < n; i++) {
// what range would this element be the min in
int left = sml_left[i] == -1 ? 0 : sml_left[i] + 1;
int right = sml_right[i] == -1 ? n - 1 : sml_right[i] - 1;
int lcap = min(k - 1ll, i - left);
int rcap = min(k - 1ll, right - i);
if (left <= i && i <= right) {
int valid_ranges = count_solns(lcap, rcap, k - 1);
ans += arr[i] * valid_ranges;
}
// what would this be max of
left = gt_left[i] == -1 ? 0 : gt_left[i] + 1;
right = gt_right[i] == -1 ? n - 1 : gt_right[i] - 1;
lcap = min(k - 1ll, i - left);
rcap = min(k - 1ll, right - i);
if (left <= i && i <= right) {
int valid_ranges = count_solns(lcap, rcap, k - 1);
ans += arr[i] * valid_ranges;
}
}
return ans;
#undef int
}min(i..j)*sum(i..j) over all ranges
Link: https://leetcode.com/problems/sum-of-total-strength-of-wizardsint totalStrength(vector<int>& nums) {
// f(i..j) = min(i..j) * sum(i..j)
// observation: I recall this pattern
// where one element is at extrema (sum) and you move such that other is maximised as well (min)
// though this isn't useful here
// sum f(i..j) over all ranges
// contribution idea, for each element i, what ranges would it be the minimum of
// can use the asymettric trick to handle duplicates
// let if be l.i.r, sum over ranges here is a tricky
// for any ri to the right, left could be l..i so for each
// pref[ri] - (pref can be any from l-1 to i-1) => each will be one range ending at ri
// cnt_left * pref[ri] - sum_pref(l-1..i-1)
// now sum over ri
// cnt_left * sum_pref(i..ri) - sum_pref(l-1..i-1) * cnt_right
// prefix sums of prefix sums needed
#define int long long
int n = nums.size();
// note: don't try to make it in one go, 2p(i-1) + nums(i) is wrong as the first p(i) is not the same as the second p(i)
// try to make second order prefix sum for 1 2 3 to see the flaw
vector<int> pref(n), ppref(n);
pref[0] = ppref[0] = nums[0];
const int mod = (int)1e9 + 7;
for (int i = 1; i < n; i++) pref[i] = (pref[i - 1] + nums[i]) % mod;
for (int i = 1; i < n; i++) ppref[i] = (ppref[i - 1] + pref[i]) % mod;
auto sum = [&](int i, int j) -> int {
assert(i <= j);
int ret = (j >= 0 ? ppref[j] : 0) - (i > 0 ? ppref[i - 1] : 0);
ret = (ret % mod + mod) % mod;
return ret;
};
auto monotonic_stack_idx = [](const auto& arr, auto first, auto last, auto should_pop) {
int n = arr.size();
vector<int> res(n, -1);
vector<int> st;
for (auto it = first; it != last; ++it) {
int i = &(*it) - arr.data();
while (!st.empty() && should_pop(arr[st.back()], *it)) {
st.pop_back();
}
if (!st.empty()) res[i] = st.back();
st.push_back(i);
}
return res;
};
auto sml_left = monotonic_stack_idx(nums, nums.begin(), nums.end(), greater_equal<int>()); // extend including equals
auto sml_right = monotonic_stack_idx(nums, nums.rbegin(), nums.rend(), greater<int>()); // don't include equals
int ans = 0;
for (int i = 0; i < n; i++) {
int left = sml_left[i] == -1 ? 0 : sml_left[i] + 1;
int right = sml_right[i] == -1 ? n - 1 : sml_right[i] - 1;
if (left <= i && i <= right) {
int cnt_left = i - left + 1;
int cnt_right = right - i + 1;
int tans = (cnt_left * sum(i, right) - cnt_right * sum(left - 1, i - 1)) % mod;
tans = (nums[i] * tans) % mod;
tans = (tans + mod) % mod;
(ans += tans) %= mod;
}
}
return ans;
#undef int
}Largest Rectangle in Histogram
Link: https://leetcode.com/problems/largest-rectangle-in-histogramFor the current index element as height, how far can I extend to the left and right?
int largestRectangleArea(vector<int>& h) {
auto monotonic_stack_idx = [](const vector<int>& arr, auto first, auto last, auto should_pop) {
int n = arr.size();
vector<int> res(n, -1);
vector<int> st;
for (auto it = first; it != last; ++it) {
int i = &(*it) - arr.data();
while (!st.empty() && should_pop(arr[st.back()], *it)) {
st.pop_back();
}
if (!st.empty()) res[i] = st.back();
st.push_back(i);
}
return res;
};
auto sml = monotonic_stack_idx(h, h.begin(), h.end(), greater_equal<int>());
auto smr = monotonic_stack_idx(h, h.rbegin(), h.rend(), greater_equal<int>());
int n = h.size();
int ans = 0;
for (int i = 0; i < n; i++) {
int left = sml[i];
int right = smr[i];
if (right == -1) right = n;
int width = right - left - 1;
ans = max(ans, h[i] * width);
}
return ans;
}Max of min(i..j)*sum(i..j)
Link: https://leetcode.com/problems/maximum-subarray-min-productNotice the patter of relation to largest rectangle in histogram. Min across ranges times another property that is increasing with length.
int maxSumMinProduct(vector<int>& nums) {
#define int long long
// let f(i,j) = min(i..j) * sum(i..j)
// note that nums >= 1 so increasing length is always better for sum
// min(i..j) & all ranges
// relate to histogram largest area
// for each i, say that if this is my minimum, what is the max I can extend
// impl note: I accidentally had auto arr instead of auto& arr
// in this case since the iterators and array copied were different
// &(*it) - arr.data() goes out of bounds
auto monotonic_stack_idx = [](auto& arr, auto first, auto last, auto should_pop) {
int n = arr.size();
vector<int> res(n, -1);
vector<int> st;
for (auto it = first; it != last; ++it) {
int i = &(*it) - arr.data();
while (!st.empty() && should_pop(arr[st.back()], *it)) {
st.pop_back();
}
if (!st.empty()) res[i] = st.back();
st.push_back(i);
}
return res;
};
auto sml = monotonic_stack_idx(nums, nums.begin(), nums.end(), greater_equal<int>());
auto smr = monotonic_stack_idx(nums, nums.rbegin(), nums.rend(), greater_equal<int>());
int n = nums.size();
const int mod = (int)1e9 + 7;
int ans = 0;
vector<int> pref(n);
pref[0] = nums[0];
for (int i = 1; i < n; i++) pref[i] = pref[i - 1] + nums[i];
for (int i = 0; i < n; i++) {
int l = sml[i] == -1 ? 0 : sml[i] + 1;
int r = smr[i] == -1 ? n - 1 : smr[i] - 1;
if (l <= r) {
int sum = pref[r] - (l ? pref[l - 1] : 0);
ans = max(ans, nums[i] * sum);
}
}
return ans % mod;
#undef int
}Subarray with min(i..j)*len > k ( same idea of iterating over minimms )
int validSubarraySize(vector<int>& nums, int threshold) {
#define int long long
// rephrase
// find any i..j s.t. min(i..j) > thres/len
// observation
// for a given minimum, you always want the maximum length as this improves satisfiability
auto monotonic_stack_idx = [](const auto& arr, auto first, auto last, auto should_pop) {
int n = arr.size();
vector<int> res(n, -1);
vector<int> st;
for (auto it = first; it != last; ++it) {
while (!st.empty() && should_pop(arr[st.back()], *it)) {
st.pop_back();
}
int i = &(*it) - arr.data(); // can't just use - arr.start due to rev_pointer, I always want the distance ftom arr start
// deference pointer, get the elem address, arr.data() is arr start address
if (!st.empty()) res[i] = st.back(); // you can use top now
st.push_back(i);
}
return res;
};
int n = nums.size();
auto sml_left = monotonic_stack_idx(nums, nums.begin(), nums.end(), greater_equal<int>());
auto sml_right = monotonic_stack_idx(nums, nums.rbegin(), nums.rend(), greater_equal<int>());
for (int i = 0; i < n; i++) {
int left = sml_left[i] == -1 ? 0 : sml_left[i] + 1;
int right = sml_right[i] == -1 ? n - 1 : sml_right[i] - 1;
int len = right - left + 1;
if (nums[i] * len > threshold) return len;
}
return -1;
#undef int
}Maximum area of 1s in a binary matrix
Link: https://leetcode.com/problems/maximal-rectangle/For any row, if you look up and collapse all the 1s above into heights, you get a histogram. So the answer for a row is largest rectangle in histogram for that row. The full solution then is just max over all rows.
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int n = matrix.size(), m = matrix[0].size();
vector<int> heights(m, 0);
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
heights[j] = (matrix[i][j] == '0') ? 0 : heights[j] + 1;
}
ans = max(ans, largestRectangleArea(heights));
}
return ans;
}
int largestRectangleArea(vector<int>& h) {
auto monotonic_stack_idx = [](const vector<int>& arr, auto first, auto last, auto should_pop) {
int n = arr.size();
vector<int> res(n, -1);
vector<int> st;
for (auto it = first; it != last; ++it) {
int i = &(*it) - arr.data();
while (!st.empty() && should_pop(arr[st.back()], *it)) {
st.pop_back();
}
if (!st.empty()) res[i] = st.back();
st.push_back(i);
}
return res;
};
auto sml = monotonic_stack_idx(h, h.begin(), h.end(), greater_equal<int>());
auto smr = monotonic_stack_idx(h, h.rbegin(), h.rend(), greater_equal<int>());
int ans = 0, n = h.size();
for (int i = 0; i < n; i++) {
int left = sml[i];
int right = (smr[i] == -1) ? n : smr[i];
ans = max(ans, h[i] * (right - left - 1));
}
return ans;
}Count of 1 filled submatrices in a binary matrix ( extension of maximum area of 1s )
int numSubmat(vector<vector<int>>& mat) {
int n = mat.size(), m = mat[0].size();
auto monotonic_stack_idx = [](const vector<int>& arr, auto first, auto last, auto should_pop) {
int n = arr.size();
vector<int> res(n, -1);
vector<int> st;
for (auto it = first; it != last; ++it) {
int i = &(*it) - arr.data();
// Pop while invariant is violated
while (!st.empty() && should_pop(arr[st.back()], *it)) {
st.pop_back();
}
if (!st.empty()) res[i] = st.back();
st.push_back(i);
}
return res;
};
vector<int> h(m, 0); // Histogram heights
int ans = 0;
for (int i = 0; i < n; i++) {
// add above above to build bars
for (int j = 0; j < m; j++)
h[j] = (mat[i][j] == 0) ? 0 : h[j] + 1;
// find less than equal to left
auto left = monotonic_stack_idx(h, h.begin(), h.end(), greater<int>());
vector<int> counts(m, 0);
for (int j = 0; j < m; j++) {
// you need 2 points for a rectangle, the bottom right is (i,j)
int prev_idx = left[j];
// consider
// 1 4 2 as heights, count from prev are the ones where you extend width
// all the way to the current j bar, those are limited by prev height[prev_idx]
// for all others, top left is beyond prev_idx, you can choose any of the points
// in width as the start and any of the points in height[j] as the height
// each is one rectangle
int count_from_prev = (prev_idx == -1) ? 0 : counts[prev_idx];
int width = (prev_idx == -1) ? (j + 1) : (j - prev_idx);
counts[j] = count_from_prev + (h[j] * width);
ans += counts[j];
}
}
return ans;
}Remove Duplicates such that Lexicographically Smallest ( stack trick )
Link: https://leetcode.com/problems/remove-duplicate-lettersRephrase: lexicographically smallest subsequence such that all chars appear once.
The main idea is to greedily make the string characters to be in ascending order as much as you can. The while loop is basically, if my current character is smaller than what I built, and I can get the prev character that I’m going to remove later, I should pop it. Note that the build string is the best one possible on the prefix, and done tracks what characters are included till now, so if done you skip.
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<int> freq(200), done(200);
string ans = "";
for(char c: s) freq[c]++;
for(char c:s){
freq[c]--; // I track how many times does c appear after current pos so at top
if(done[c]) continue;
while(!ans.empty() && ans.back()>c && freq[ans.back()]>0){
done[ans.back()] = 0;
ans.pop_back();
}
ans.push_back(c);
done[c] = 1;
}
return ans;
}
};Lexico min subseq of size k with atleast rep of 'c' characters
Similar approach as others of the same lexico min of size k type problems.
string smallestSubsequence(string s, int k, char letter, int reps) {
// observation
// lexico smallest and atlest "reps" k, so I need to choose which one I keep and which ones to drop
// can use a similar "can_drop" approach as other lexico min subseq related problems
int n = s.size();
string built;
// of the k chars, I need k - reps of other kind\
// divide into letter and non letter branches
int letter_can_drop = count(s.begin(), s.end(), letter) - reps;
int other_can_drop = n - k; // this include letter as well
for (char c : s) {
while (!built.empty() && c < built.back()) {
if (built.back() == letter && letter_can_drop && other_can_drop) {
built.pop_back();
letter_can_drop--;
other_can_drop--; // note both counted here as u need to make lenght k atleast
} else if (built.back() != letter && other_can_drop) {
built.pop_back();
other_can_drop--;
} else {
break;
}
}
built.push_back(c);
}
// resize such that I have the letter reps
// so start from back as better to delete the larger ones and delete non letter ones
int del = (int)built.size() - k;
int reps_left = reps;
assert(del >= 0);
string ans = "";
for (int i = (int)built.size() - 1; i >= 0; i--) {
if (built[i] == letter && reps_left) {
ans.push_back(built[i]);
reps_left--;
} else if (del)
del--;
else
ans.push_back(built[i]);
}
reverse(ans.begin(), ans.end());
return ans;
}Maximum number as a subsequence merge of two numbers
Link: https://leetcode.com/problems/create-maximum-number/A dp solution with states is obvious but is too slow. When dp fails and it’s usually a mix of brute + greedy/bin search. Nothing to search for here though.
But can brute force over (i,j) where you pick i elements from num1 and j elements from num2 such that i+j=k.
Subproblem : maximum subsequence of length k from a single array The idea to solve this problem is simple, you use a stack (which represents you current set) and a greedy where if the current one > stack end and you can still satisfy the length requirement, you pop the stack end and push current. Don’t forget to resize here. Link: https://leetcode.com/problems/find-the-most-competitive-subsequence This problem above is exactly this subproblem.
The other part is the merge where if the starting elems are equal you need to check further ahead aka take the star from lexicographically larger array. See comment for a case.
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int n1 = nums1.size(), n2 = nums2.size();
// dp will fail
// usually in such cases look for brute + greedy/bin optim
// brute over i,j pairs where we pick i from first array and j from second
// note that i + j = k, so you just need one loop
auto best_subseq = [&](const auto& v, int elems) {
int n = v.size();
vector<int> built;
// note that we always add to the stack but how many can we forego
// as discarded
int drop_upto = v.size() - elems;
for (int x : v) {
while (!built.empty() && drop_upto > 0 && built.back() < x) {
built.pop_back();
drop_upto--;
}
built.push_back(x);
}
// note that this can have more elems
built.resize(elems); // NOTE: don't forget it's easy to miss this step
// case where it's entirel decreasing I'll never pop and can have more than elems no of elements
return built;
};
auto merge = [&](const auto& a, const auto& b) {
vector<int> tans;
tans.reserve(k);
auto as = a.begin(), bs = b.begin();
while ((int)tans.size() < k) {
// this is same as < but allows me to use ranges instead, or I can use one of the newer features like
// spans to compare with no copying
if (lexicographical_compare(as, a.end(), bs, b.end()))
tans.emplace_back(*bs++);
else
tans.emplace_back(*as++);
}
return tans;
};
vector<int> ans;
// i<=k and i<=n1
// i+j = k
// j = k-i, j<=n2
// k-i<=n2 => i<= k - n2
int start = max(0, k - n2);
int end = min(k, n1);
for (int i = start; i <= end; i++) {
vector<int> p1 = best_subseq(nums1, i), p2 = best_subseq(nums2, k - i);
// now we want to merge
// NOTE: the merge is trickier, you want to pick from the subseq that is lexicographically larger
// case: v1 = {6,0}, v2 = {6,7}, taking from v1 => {0} and {6,7} so you build 6,6
// when you could pick from v2 and build 6,7
vector<int> tans = merge(p1, p2);
if (tans > ans) ans = tans;
}
return ans;
}Minimum possible number after removing exactly k digits ( subproblem of prev problem with some edge cases )
Edge cases like leading zeros and all digits removed are easy to miss.string removeKdigits(string num, int k) {
int drop_upto = k;
string built;
for (char c : num) {
while (!built.empty() && drop_upto > 0 && c < built.back()) {
drop_upto--;
built.pop_back();
}
built.push_back(c);
}
// don't forget as if it's increasing you can have a larger length
built.resize((int)num.size() - k);
built.erase(0, built.find_first_not_of('0'));
if (built.empty()) built = "0";
return built;
}Check a 132 subsequence existence ( challenge: concise )
Link: https://leetcode.com/problems/132-patternclass Solution {
public:
bool find132pattern(vector<int>& nums) {
// observation
// you cannot just take the minimum and the maximum in the prefix as it's not 31 or 13, it has to be 13
// the then is 132, iterate over 2s and find the maximum index candidate for 3, then if the prefix min
// prior to 3 is less than 2, that's your solution
// a trivial solution
// is to use prefix mins and a first greater to left array aka mono dec stack
// Note: if you remember the trapping rainwater problem or ig some other
// a 3-2 can always be retrieved as the popped and inserted pair when making a min dq
int n = (int)nums.size();
const int INF = (int)1e9+10;
stack<pair<int,int>> stk;
int pref_mn = INF;
for(int i = 0;i<n;i++){
int num2 = nums[i];
while(!stk.empty() && stk.top().first<=num2){
stk.pop();
}
// the loop condition handles num3>num2 the pair of {num3, min prior to num3} handles num3>num1
// remaining is num1<num2
if(!stk.empty()){
auto[num3,num1] = stk.top();
if(num1<num2) return true;
}
stk.push({num2,pref_mn});
pref_mn = min(pref_mn, nums[i]);
}
return false;
}
};
Maximum number of partitions such that sorting partitions = sorted array
Link: https://leetcode.com/problems/max-chunks-to-make-sorted-iiAn easier solution is based on prefix and suffix max/min arrays.
A valid boundary is where prefix_max[i] <= suffix_min[i+1].
Note that the boundaries way is very very versatile for these type of problems.
An alternative is to use a monotonic stack.
int maxChunksToSorted(vector<int>& nums) {
// rephrase:
// max number of partitions such that sorting the paritions = fully sorted array
// basically the array inversion sets are localilsed into chunks and I need the min range for each such inversion range
// related to longest contiguous segment to sort problem except I need shortest
// observation: for any sorted segment, break into individual elements
// observation: you need to sort prefix if max in pref > cur element, similar for descending
// observation: a boundary is when max of prefix <= min of suffix, so if you keep suffix mins you can do it easily in O(n) space
// alternative:
// mono increasing stack that stores the current partition
// if you get a smaller element x, you want to keep the stack back as that's the largest element, similar to pref_max as above
// but you want to keep on "consuming" till back > x as you need to sort this range so the the cur element and the largest so far
// are in correct positions
// note that among equals you want the "last one" only
// so you append when = but don't pop equals
// each largest element signifies a "consumption" so size of stack is the answer
// to get the actual segment, you can store for each element in the stack the min index of the elements it has consumed
stack<int> stk;
for (int x : nums) {
if (stk.empty() || x >= stk.top())
stk.push(x);
else {
int last = stk.top();
while (!stk.empty() && stk.top() > x) stk.pop();
stk.push(last);
}
}
return stk.size();
}Span of <= elems
Link: https://leetcode.com/problems/online-stock-spanI want initially doing indexes of what was popped but that’s wrong as some other element earlier could have popped few elems that apply to you as well. So once you maintain monotonicity, look at the top and it’s index in the full array, you want one after.
class StockSpanner {
public:
stack<pair<int,int>> stk;
int index = 0;
StockSpanner() {
}
int next(int price) {
while(!stk.empty() && stk.top().first<=price)
stk.pop();
int ans = stk.empty()?index+1:index-stk.top().second;
stk.push({price,index++});
return ans;
}
};Sum of subarray minimums ( simple but rem asymmetric stacks )
Link: https://leetcode.com/problems/sum-of-subarray-minimumsint sumSubarrayMins(vector<int>& arr) {
#define int long long
// for each elem, look at what range could this be the minimum of
// so look at less to left and right
auto monotonic_stack_idx = [](const auto& arr, auto first, auto last, auto should_pop) {
int n = arr.size();
vector<int> res(n, -1);
vector<int> st;
for (auto it = first; it != last; ++it) {
while (!st.empty() && should_pop(arr[st.back()], *it)) {
st.pop_back();
}
int i = &(*it) - arr.data(); // can't just use - arr.start due to rev_pointer, I always want the distance ftom arr start
// deference pointer, get the elem address, arr.data() is arr start address
if (!st.empty()) res[i] = st.back(); // you can use top now
st.push_back(i);
}
return res;
};
int n = arr.size();
const int mod = (int)1e9 + 7;
// so on the left end I take the smaller element while on the right I take smaller or equal
// case 1 2 2 2
vector<int> sml_left = monotonic_stack_idx(arr, arr.begin(), arr.end(), greater_equal<int>());
vector<int> sml_right = monotonic_stack_idx(arr, arr.rbegin(), arr.rend(), greater<int>());
int ans = 0;
for (int i = 0; i < n; i++) {
int l = sml_left[i], r = sml_right[i];
l = l == -1 ? 0 : l + 1;
r = r == -1 ? n - 1 : r - 1;
if (l <= i && i <= r) {
ans += (i - l + 1) * (r - i + 1) * arr[i];
ans %= mod;
}
}
return ans;
#undef int
}Maximum width ramp ( farthest small instead of nearest small )
Idea is to never pop but keep decreasing elements. Basically, you would always pick the first if you could but you move ahead only when you need a smaller one. The stack is mono so can binary search.
int maxWidthRamp(vector<int>& nums) {
// so in the prefix I want the first element <= cur elem ( not near small )
// observation: if I keep increasing elems, I can never pop
// if I keep decreasing elems, basically you take the 0th elem if you can but only if you can't you would move ahead
// in which case you want to move to a smaller element so mono dec stack where on equals the first index is stored
// except if the elemnts later increase, I never want to pop
// can binary search this stack
int n = nums.size();
vector<pair<int, int>> stk;
int ans = 0;
for (int i = 0; i < n; i++) {
// now u can bin search
// decreasing so rev iterators, I want first > so I can do prev
auto it = upper_bound(stk.rbegin(), stk.rend(), pair<int, int>{nums[i], n});
if (it != stk.rbegin()) {
it = prev(it);
ans = max(ans, i - it->second);
}
if (stk.empty() || nums[i] < stk.back().first) stk.emplace_back(nums[i], i);
}
return ans;
}Improvement to : built the decreasing stack first, then iterate in reverse.
int maxWidthRamp(vector<int>& nums) {
// so in the prefix I want the first element <= cur elem ( not near small )
// observation: if I keep increasing elems, I can never pop
// if I keep decreasing elems, basically you take the 0th elem if you can but only if you can't you would move ahead
// in which case you want to move to a smaller element so mono dec stack where on equals the first index is stored
// except if the elements later increase, I never want to pop
int n = nums.size();
vector<pair<int, int>> stk;
for (int i = 0; i < n; i++)
if (stk.empty() || nums[i] < stk.back().first)
stk.emplace_back(nums[i], i);
// now for j<i and nums[j]<=nums[i] I want the maximum i, then iterate in reverse
// for this you always want to use the first j <= this, which would also be the largest one possible
// in the stack, any smallest ones you can pop, since they would have both a higher j and smaller i
int ans = 0;
for (int i = n - 1; i >= 0; i--) {
// note that I also only want the prefix
while (!stk.empty() && stk.back().second >= i) stk.pop_back();
while (!stk.empty() && stk.back().first <= nums[i]) {
ans = max(ans, i - stk.back().second);
stk.pop_back();
}
}
return ans;
}Longest binary array with 1s > 0s
Link: https://leetcode.com/problems/longest-well-performing-interval/A bit complicated but based off of the previous max ramp idea
int longestWPI(vector<int>& hours) {
// rephrase:
// convert to bool array by transform: a(i) > 8
// needed is longest subarray j..i s.t sum(j..i) > ceil(len of subarray/2)
// p(i) - p(j-1) > (i-j+1)/2
// 2p(i) - 2p(j-1) - i + j - 1 > 0
// 2p(i) - i - { 2p(j-1) - (j-1) } > 0
// let f(x) = 2p(x) - x
// f(i) > f(j-1) and we want the minimum j here
// when you reach i, push in f(i-1)
// now you want of the set that satisfies in the prefix, the farthest
// you would take the first element if you could, you move ahead to satisfy < f(i) => keep decreasing as indexes increase
// when can you pop forever?
// farthest to loop in reverse i (if you get the best range, you can discard forever)
// 8 6 2, let's say you used 6, any further would have lesser i, so you can just discard 6, 2 and any smaller
vector<pair<int, int>> stk;
stk.emplace_back(1, 0); // f(j-1),j
// f(-1) = 2p(-1)-(-1) = 1
int n = hours.size();
for (int& x : hours) x = (x > 8);
int pref = 0;
for (int i = 0; i < n - 1; i++) {
pref += hours[i];
int fi = 2 * pref - i;
if (stk.back().first > fi)
stk.emplace_back(fi, i + 1);
}
int ans = 0;
pref += hours.back();
for (int i = n - 1; i >= 0; i--) {
int fi = 2 * pref - i;
pref -= hours[i];
while (!stk.empty() && stk.back().second > i) stk.pop_back();
while (!stk.empty() && stk.back().first < fi) {
ans = max(ans, i - stk.back().second + 1);
stk.pop_back();
}
}
return ans;
}A simpler trick is to transform the array to +1/-1 instead of 1/0. Observation then is that the delta in prefix sums is only by 1 at each step, so for current sum i, you want to find the first occurence of sum i-1 (i-x is even better but this would come after i-1).
int longestWPI(vector<int>& hours) {
int res = 0, score = 0, n = hours.size();
unordered_map<int, int> seen;
for (int i = 0; i < n; ++i) {
score += hours[i] > 8 ? 1 : -1;
if (score > 0) {
res = i + 1;
} else {
if (seen.find(score) == seen.end())
seen[score] = i;
if (seen.find(score - 1) != seen.end())
res = max(res, i - seen[score - 1]);
}
}
return res;
}Number of visible people in queue ( count while pop trick )
Link: https://leetcode.com/problems/number-of-visible-people-in-a-queue/vector<int> canSeePersonsCount(vector<int>& nums) {
// observation
// for any i, the lookup range is till next greater
// for each i..j, I need to answer the lis query ( wrong X )
// it's not lis, you have no choice, you must find the increasing range
// basically I need to find the "steps"
// observation
// if I maintain a monotonically increasing stack
// observation
// moving from right to left is easier
// because then anything beyond the last element ( the largest ) is not needed
// and when you get a larger element you can just pop out the rest
// can binary search over the stack to find the answer for each i
// optim to O(n)
// build the same way, mono increasing stack from right to left
// except when you insert a(i), the number of elements popped is you answer
int n = nums.size();
vector<int> ans(n), stk;
for (int i = n - 1; i >= 0; i--) {
while (!stk.empty() && nums[i] > stk.back())
stk.pop_back(), ans[i]++;
ans[i] += !stk.empty(); // if it's not empty you see one more person
stk.push_back(nums[i]);
}
return ans;
}int totalSteps(vector<int>& nums) {
// observation
// each op deletes all consecutive inversions
// a larger element will swallow all the elemnts to its right that are < it
// so makes sense to start from right
// no of steps needed will only increase as you move left
// just maintain the current state of suffix after applying the operations needed
// so that it is sorted
// case 6 1 4 3 5
// when you are at 6, stack would look like 1 3 5
// you need 3 moves to swallow these, ans is to maxxed not summed
// note that 3 is implicity swalloed by 3 and does not contributed
// attempt 1:
// initially I did a max(ans, tans)
// but since the operations happen in parallel across, case can be made where it's wrong
// even though you may have 20 elements forward, you don't need 20 moves as while the
// elements ahead were being eaten, this element too was at work
// case: 8 2 3 12 11
// suff 11 => 0 moves
// suff 12 => 1 moves
// suff 3 12 => 1 moves
// suff 2 3 12 => 0 moves
// suff 8 12 => 2 moves
// actual is just 1 move => 8 12
// the idea of max was correct, but let's say if the moves to make sum suffix is 5
// that means you get upto 5 free moves, where you can just say for this one I can merge it with those 5
// and not increment
stack<pair<int, int>> stk; // elem, steps to make suffix till here
int ans = 0, n = nums.size();
for (int i = n - 1; i >= 0; i--) {
int tans = 0;
while (!stk.empty() && nums[i] > stk.top().first) {
// getting till here I needed top.second moves, but I am removing one more as well
// so whichever is higher
tans = max(tans + 1, stk.top().second);
stk.pop();
}
stk.push({nums[i], tans});
ans = max(ans, tans);
}
return ans;
}2nd next greater element ( can only be done as "waiting room" variation )
The idea is basically a “stages” based approach. waiting_0 are elements looking for first greater while waiting_1 are elements looking for second greater.
vector<int> secondGreaterElement(vector<int>& nums) {
/*
waiting room based approach
in my waiting stack, since I want next greater to right, I want the smallest at the top
so that whenever I process, all candidates are at the top of the stack
*/
int n = nums.size();
stack<int> waiting_0, waiting_1;
vector<int> ans(n, -1);
for (int i = 0; i < n; i++) {
// first match with watiting_1
while (!waiting_1.empty() && nums[i] > nums[waiting_1.top()]) {
ans[waiting_1.top()] = nums[i];
waiting_1.pop();
}
// now move the waiting 0 to the waiting 1
// note that top of waiting_1 <= nums[i] by previous loop
// so all elems in waiting_1 <= nums[i]
assert(waiting_1.empty() || nums[i] <= nums[waiting_1.top()]);
vector<int> to_move; // this is increasing as stack was descreasing
while (!waiting_0.empty() && nums[i] > nums[waiting_0.top()]) {
// waiting 1.. (all>=nums[i]) ... what I popped ...<nums[i]
// but waiting_0 is increasing and I want to append a reversed list
to_move.push_back(waiting_0.top());
waiting_0.pop();
}
// lc does not have "ranges" else this would be much cleaner
for (auto it = to_move.rbegin(); it != to_move.rend(); it++)
waiting_1.push(*it);
waiting_0.push(i);
}
return ans;
}Beautiful Towers ( maximum sum such that array is a "mountain" )
Link: https://leetcode.com/problems/beautiful-towers-ii/I solved a different variation first ( misread ) where I remove entire heights so recurrence refers to that. Modification is trivial.
long long maximumSumOfHeights(vector<int>& arr) {
// rephrase
// maximise sum h(i) such that h(i) is a mountain
// iterate over "peaks"
// f(i) = sum of h(i) such that range 0..i ( ending at i ) is increasing
// g(i) = sum of g(i) such that range i..n-1 is decreasing
// both can be computed as a recurrence relation
// f(i) = f(i-1) + h(i) if h(i) >= h(i-1)
// f(i) = f(k) + h(i) if h(i) < h(i-1) where k = first <= h(i) to the left
// initially I solved a different variation where you remove entire towers
// so these recurrences above reflect ^ version, but modifying is trivial
#define int long long
auto monotonic_stack_idx = [](const auto& arr, auto first, auto last, auto should_pop) {
int n = arr.size();
vector<int> res(n, -1);
vector<int> st;
for (auto it = first; it != last; ++it) {
while (!st.empty() && should_pop(arr[st.back()], *it)) {
st.pop_back();
}
int i = &(*it) - arr.data(); // can't just use - arr.start due to rev_pointer, I always want the distance ftom arr start
// deference pointer, get the elem address, arr.data() is arr start address
if (!st.empty()) res[i] = st.back(); // you can use top now
st.push_back(i);
}
return res;
};
int n = arr.size();
auto sml_left = monotonic_stack_idx(arr, arr.begin(), arr.end(), greater<int>());
auto sml_right = monotonic_stack_idx(arr, arr.rbegin(), arr.rend(), greater<int>());
vector<int> lsum(n), rsum(n);
lsum[0] = arr[0];
rsum.back() = arr.back();
for (int i = 1; i < n; i++) {
if (arr[i] >= arr[i - 1])
lsum[i] = lsum[i - 1] + arr[i];
else {
int seg = sml_left[i] == -1 ? i + 1 : i - sml_left[i];
lsum[i] = (sml_left[i] == -1 ? 0 : lsum[sml_left[i]]) + seg * arr[i];
}
}
for (int i = n - 2; i >= 0; i--) {
if (arr[i] >= arr[i + 1])
rsum[i] = rsum[i + 1] + arr[i];
else {
int seg = sml_right[i] == -1 ? n - i : sml_right[i] - i;
rsum[i] = (sml_right[i] == -1 ? 0 : rsum[sml_right[i]]) + seg * arr[i];
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, lsum[i] + rsum[i] - arr[i]);
}
return ans;
#undef int
}First greater to both h(i) and h(j) ( this one is tricky )
Link: https://leetcode.com/problems/find-building-where-alice-and-bob-can-meetvector<int> leftmostBuildingQueries(vector<int>& heights, vector<vector<int>>& queries) {
// observation
// same index greater type of problem, cannot do better than n log n which holds for this one as well
// online queries is harder
// attempt 1: I missed normalising queries that makes it much much easier
// observation, note that a and b are symmetric
// so can swap (ai, bi) where ai>bi, now all are ai <= bi
// do a line sweep, with queries of bi indices in reverse
// for each (ai,bi) push in bi first, now I'm looking for
// cases in my mono stack, where I can cut it by >= a(i)
// this I can binary search over and the first I find is nearest
// obs: if h(cur)>=h(stk top), it will satisfy condition for any that stk top does
// and it will be closer so stk top is never needed again
int qidx = 0;
for (auto& q : queries) {
q.push_back(qidx++);
if (q[0] > q[1]) swap(q[0], q[1]);
}
int qs = queries.size();
int n = heights.size();
vector<int> ans(qs, -1);
sort(queries.begin(), queries.end(), [](const auto& a, const auto& b) { return a[1] > b[1]; });
// NOTE: sort needs strict weak ordering so if equal, retured value must be false
vector<int> stk;
int stk_at = n;
for (auto& q : queries) {
if (q[0] == q[1]) {
// trivial case
// needed as i can't jump same heights but this case is valid
ans[q[2]] = q[1];
continue;
}
while (stk_at > q[1]) {
stk_at--;
// process this
// I need the stack to be decreasing in heights ( indexes are dec as well ) as I read from left to right
// as you would pick the closest one if you can and move ahead if u can't
while (!stk.empty() && heights[stk.back()] <= heights[stk_at]) {
stk.pop_back();
}
// obs: any newer value if it's higher than the current stack top, it will satisfy the condition as well
// and be closer
// case top is 2, now I have 5, 5 will satisfy any that had satisfied >= 2 ( larger height is always better )
stk.push_back(stk_at);
}
// now i bin search to find my needed one over these
int l = 0, r = (int)stk.size() - 1, found = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
// this is mono dec in heights, I want a closer index
if (heights[stk[mid]] > heights[q[0]]) { // not equals
found = mid;
l = mid + 1; // closer indexes are to the right
} else {
r = mid - 1;
}
}
if (found != -1) {
ans[q[2]] = stk[found];
}
}
return ans;
}