← leetcode

Count Non-Decreasing Subarrays After K Operations

· Hard

LeetCode problem 3420

the trick in the question is that after k operations, the ideal subarray gets formed in blocks.

since you can only make numbers bigger, each number has to rise to at least the biggest number before it (e.g. 6 3 1 2 7 4 => 6 6 6 6 7 7 which consists of two blocks, one starting at 6 and the other at 7).

blocks also make it fast to add a number on the left, e.g. the window 3 1 2 is the single block 3 3 3, at a cost of 3.

adding a 6 on the left swallows the whole block, so all three numbers rise from 3 to 6. that adds 3 * (6 - 3) = 9, one multiplication for the whole block instead of one step per number, so the new cost is 12, for 6 6 6 6.

the difficulty in this question lies in the ability to store blocks.

in our case, we decided to use a deque since that allows us to track blocks at both ends of the window, storing the index where each block starts:

  • the front of the deque is the leftmost block
    • where a new number on the left swallows blocks from the front.
  • the back of the deque is the rightmost block:
    • when the window costs more than k, right moves left,
    • when the rightmost block is empty, it's removed from the back.

code link to code

class Solution {
public:
    long long countNonDecreasingSubarrays(vector<int>& nums, int k) {
        const int n{static_cast<int>(nums.size())};
        long long count{0};
        long long cost{0};
        int right{n - 1};

        deque<int> blocks;

        for (int left{right}; left >= 0; --left) {
            while (!blocks.empty() && nums[blocks.front()] <= nums[left]) {
                const int start{blocks.front()};
                blocks.pop_front();

                const int stop{blocks.empty() ? right + 1 : blocks.front()};

                cost += static_cast<long long>(stop - start) * (nums[left] - nums[start]);
            }

            blocks.push_front(left);

            while (cost > k) {
                cost -= nums[blocks.back()] - nums[right];

                if (blocks.back() == right) {
                    blocks.pop_back();
                }
                --right;
            }

            count += right - left + 1;
        }
        return count;
    }
};

complexity link to complexity

  • Time: O(n)
  • Space: O(n)

learnings link to learnings

class Solution {
public:
    long long countNonDecreasingSubarrays(vector<int>& nums, int k) {
        // main issue:
        // 6 3 1 doesnt work
        // X 3 1 2 try this => how to calculate using O(1) or O(log(n))

        long long ans{};
        vector<long long> cases (1e5+1, 0);

        cases[1] = 1;
        for (int i = 2; i < 1e5+1; ++i) {
            cases[i] = cases[i-1] + i;
        }

        int length{}, curr_mx{nums[0]}, ops_used{}, carry_over{};

        int left{}, right{1};
        while (right < nums.size()) {
            if (curr_mx <= nums[right]) {
                curr_mx = nums[right];
            } else {
                ops_used += curr_mx - nums[right];

                if (ops_used > k) {
                    ans += cases[right - left];

                    left = right;
                    curr_mx = nums[right];
                    ops_used = 0;
                    carry_over = 0;
                    while (left > 0) {
                        int difference = nums[left-1] - curr_mx;
                        if (difference > 0) {
                            int new_ops{difference * (right-left+1)};
                            if (new_ops + ops_used + carry_over <= k) {
                                ops_used += new_ops + carry_over;
                                curr_mx = nums[left-1];
                                carry_over = 0;
                            } else {
                                break;
                            }
                        } else if (nums[left-1] < curr_mx) {
                            carry_over += curr_mx + nums[left-1];
                        }
                        --left;
                    }

                    ans -= cases[right-left];
                }
            }
            ++right;
        }

        return ans + cases[right-left];
    }
};

i think this is where i got to originally, before i had to phone an (orange) friend (claude).

issue is, i knew the solution had something to do with trying to make everything a "block" (e.g. 6 3 1 2 would have to turn into a block of 6 6 6 6 to satisfy the non-decreasing rule), meaning if left and right denote the bounds of our window, we can simply make an O(1) update when we increment right for the next number that comes along.

the issue is that when i was trying to traverse from the start, when our window uses more than k operations to stay non-decreasing, it's hard to? impossible to? properly update the remainder of the array in constant time (e.g. with the case 6 3 4 1, it becomes the block 6 6 6 6, but incrementing the left pointer and updating the block becomes impossible (?) since you have to update every single value inside of the array & they might not even be the same value, e.g. removing the initial 6 makes it impossible to instantly convert 3 4 1 to 3 4 4 without having some sort of stored data).

i think from that, i should have realised that you should not traverse from the start, but traverse from the end, which is what "my" new answer does.

time taken link to time taken

  • DNF
    • cut me some slack please thank you