Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

1063. Number of Valid Subarrays

Time: $O(n)$

Space: $O(n)$

			


class Solution {
 public:
  int validSubarrays(vector<int>& nums) {
    // For each num in nums, each element x in the stack can be the leftmost
    // Element s.t. [x, num] forms a valid subarray, so the stack.size() is
    // The # of valid subarrays ending at curr num
    //
    // E.g. nums = [1, 3, 2]
    // Num = 1, stack = [1] -> valid subarray is [1]
    // Num = 3, stack = [1, 3] -> valid subarrays are [1, 3], [3]
    // Num = 2, stack = [1, 2] -> valid subarrays are [1, 3, 2], [2]
    int ans = 0;
    stack<int> stack;

    for (const int num : nums) {
      while (!stack.empty() && stack.top() > num)
        stack.pop();
      stack.push(num);
      ans += stack.size();
    }

    return ans;
  }
};




			


class Solution {
  public int validSubarrays(int[] nums) {
    // For each num in nums, each element x in the stack can be the leftmost
    // Element s.t. [x, num] forms a valid subarray, so the stack.size() is
    // The # of valid subarrays ending at curr num
    //
    // E.g. nums = [1, 3, 2]
    // Num = 1, stack = [1] -> valid subarray is [1]
    // Num = 3, stack = [1, 3] -> valid subarrays are [1, 3], [3]
    // Num = 2, stack = [1, 2] -> valid subarrays are [1, 3, 2], [2]
    int ans = 0;
    Deque<Integer> stack = new ArrayDeque<>();

    for (final int num : nums) {
      while (!stack.isEmpty() && stack.peek() > num)
        stack.pop();
      stack.push(num);
      ans += stack.size();
    }

    return ans;
  }
}




			


class Solution:
  def validSubarrays(self, nums: List[int]) -> int:
    # For each num in nums, each element x in the stack can be the leftmost
    # Element s.t. [x, num] forms a valid subarray, so the len(stack) is
    # The # Of valid subarrays ending at curr num
    #
    # E.g. nums = [1, 3, 2]
    # Num = 1, stack = [1] . valid subarray is [1]
    # Num = 3, stack = [1, 3] . valid subarrays are [1, 3], [3]
    # Num = 2, stack = [1, 2] . valid subarrays are [1, 3, 2], [2]
    ans = 0
    stack = []

    for num in nums:
      while stack and stack[-1] > num:
        stack.pop()
      stack.append(num)
      ans += len(stack)

    return ans