< Back





1063. Number of Valid Subarrays

Deceivingly hard question, and the description doesn't help. We aren't required to return the
actual subarrays, just the number of valid ones following the criteria. The criteria for a valid
subarray is that the leftmost element is less than all succeeding elements. To solve this, we use a
monotonically increasing stack.

Whenever we encounter a new element, if the current element at the top of the stack is greater than
the current element, we pop it off. Essentially, we've found the end of the valid subarray starting
from the element we've just popped from the top of the stack. The number of valid subarrays starting
from the index popped from the top of the stack and ending at the current element is the difference
between the index of the current element and the element popped from the top of the stack.

Once we've processed all elements, we're likely to have elements remaining on the monotonically
increasing stack. These elements have a number of valid subarrays that end at the end of the input
array - they will always be the lowest value, leftmost element in their subarray(s). We can
calculate the number of valid subarrays starting from these elements and ending at the end of the
input by subtract n, the length of the input, from the index of the elements popped in the
post-processing of the monotonic stack.

The solution is as follows:


  class Solution:
      def validSubarrays(self, nums: List[int]) -> int:
          n = len(nums)
          stack = []
          ans = 0

          for i in range(n):
              while stack and nums[i] < nums[stack[-1]]:
                  ans += i - stack.pop()

              stack.append(i)

          while stack:
              ans += n - stack.pop()

          return ans


_ Time Complexity:

  O(n) - We inspect all integers in the input.

_ Space Complexity:

  O(n) - We maintain a monotonically increasing stack.