Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1063.html

1063. Number of Valid Subarrays

Level

Hard

Description

Given an array A of integers, return the number of non-empty continuous subarrays that satisfy the following condition:

The leftmost element of the subarray is not larger than other elements in the subarray.

Example 1:

Input: [1,4,2,5,3]

Output: 11

Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

Example 2:

Input: [3,2,1]

Output: 3

Explanation: The 3 valid subarrays are: [3],[2],[1].

Example 3:

Input: [2,2,2]

Output: 6

Explanation: There are 6 valid subarrays: [2],[2],[2],[2,2],[2,2],[2,2,2].

Note:

  1. 1 <= A.length <= 50000
  2. 0 <= A[i] <= 100000

Solution

The basic idea is, for any index i in nums, if there exists an index j such that i < j and nums[i] > nums[j], then the subarray that starts from index i and ends at index greater than or equal to j is not valid. Therefore, for each index i, find the minimum index j such that i < j and nums[i] > nums[j], and the longest valid subarray that starts from index i ends at index j - 1. If such an index j does not exist, then the subarray from index i to the end of the array is valid.

Use two stacks, a number stack and an index stack, to store numbers from nums and indices, respectively. Loop over nums from left to right. For each number in nums, if the stacks are empty or the element at the top of the number stack is less than or equal to the current number, then the previous subarray can be extended. If the element at the top of the number stack is greater than the current number, then the current number cannot be in the previous subarray since the current number will make the previous subarray invalid. While the top element of the stack is greater than the current number, pop the number and the index from both stacks, and the maximum end index of the previous subarray (the start index of the subarray is the popped index from the index stack) is the current index minus 1. After the popping operations (it is possible that popping operations are not needed at some indices), push the current number and the current index into the two stacks. After all the numbers in nums are visited, while the stacks are not empty, pop elements from both stacks, and for each popped index, the maximum end index of the subarray is nums.length - 1.

For example, given nums = [1,4,2,5,3], the end indices of the subarrays are [4,1,4,3,4]. That is, the subarrays starting from numbers 1, 2 and 3 can end at the last index, and the subarrays starting from numbers 4 and 5 have the same end index at the start index.

For each index i, if the subarray starting from index i have the maximum end index j, then the longest subarray has length j - i + 1. The subarrays that starts from index i with lengths 1, 2, …, j - i + 1 are all valid, so add j - i + 1 to the total number of valid subarrays. Finally, return the total number of valid subarrays.

  • class Solution {
    public int validSubarrays(int[] nums) {
        Stack<Integer> numStack = new Stack<Integer>();
        Stack<Integer> indexStack = new Stack<Integer>();
        int length = nums.length;
        int[] endIndices = new int[length];
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            while (!numStack.isEmpty() && numStack.peek() > num) {
                numStack.pop();
                int prevIndex = indexStack.pop();
                endIndices[prevIndex] = i - 1;
            }
            numStack.push(num);
            indexStack.push(i);
        }
        while (!numStack.isEmpty()) {
            numStack.pop();
            int prevIndex = indexStack.pop();
            endIndices[prevIndex] = length - 1;
        }
        int subarraysCount = 0;
        for (int i = 0; i < length; i++) {
            int curLength = endIndices[i] - i + 1;
            subarraysCount += curLength;
        }
        return subarraysCount;
    }
}

All Problems

All Solutions