LC-3420 Hard LeetCode

3420. Count Non-Decreasing Subarrays After K Operations

Array Stack Segment Tree Queue Sliding Window Monotonic Stack Monotonic Queue

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 20% Topics: Array, Stack, Segment Tree, Queue, Sliding Window, Monotonic Stack, Monotonic Queue

View full problem on LeetCode

Reading material

Arrays & Hashing 12 min Stacks & Queues 11 min Segment & Fenwick Trees 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

import collections


# mono deque, two pointers, sliding window
class Solution(object):
    def countNonDecreasingSubarrays(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        result = cnt = 0
        dq = collections.deque()
        right = len(nums)-1
        for left in reversed(xrange(len(nums))):
            while dq and nums[dq[-1]] < nums[left]:
                l = dq.pop()
                r = dq[-1]-1 if dq else right
                cnt += (r-l+1)*(nums[left]-nums[l])
            dq.append(left)
            while cnt > k:
                cnt -= nums[dq[0]]-nums[right]
                if dq[0] == right:
                    dq.popleft()
                right -= 1
            result += right-left+1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT