hard Number of Valid Subarrays

Problem Statement

Given an integer array nums, return the total count of non-empty subarrays within nums where each subarray must have its first element as the smallest among all its elements.

A subarray is a Contiguous part of an array.

Examples

• Example 1:

  • Input: nums = [4, 3, 1]
  • Expected Output: 3
  • Justification: The valid subarrays are [4], [3], and [1]. Each subarray consists of a single element, satisfying the condition since there's no smaller element than the first.

• Example 2:

  • Input: nums = [1, 3, 2, 4, 1]
  • Expected Output: 10
  • Justification: The valid subarrays are [1], [1, 3], [1, 3, 2], [1, 3, 2, 4], [1, 3, 2, 4, 1], [3], [2], [2, 4], [4], and [1].

• Example 3:

  • Input: nums = [3, 3, 3]
  • Expected Output: 6
  • Justification: The valid subarrays are [3], [3], [3], [3, 3], [3, 3], and [3, 3, 3]. Since all elements are equal, all subarrays starting with any element satisfy the condition.

Solution

To solve this problem, we can use a stack to keep track of elements in a way that helps us quickly determine the number of valid subarrays ending with each element of the array. The crux of this approach lies in understanding that a valid subarray can be extended by elements larger than or equal to its first element without violating the condition. This makes a stack an ideal data structure for maintaining a sequence of elements where each new element can potentially form new valid subarrays with the preceding ones.

Our approach is effective because it efficiently iterates through the array once, leveraging the stack to manage the elements in a way that minimizes unnecessary comparisons. Each element is pushed onto the stack only once and popped only once, ensuring that we keep our operations to a minimum while accurately counting the valid subarrays.

Step-by-step Algorithm

1. Initialize a Stack: Start by creating an empty stack. This stack will be utilized to store the indices of elements from the input array nums. The stack helps in tracking the elements that are in non-decreasing order from the current index being processed.

2. Initialize Count Variable: Set up a variable, count, to keep a cumulative total of valid subarrays discovered throughout the iteration of the array. Initialize count to 0.

3. Iterate Through the Array:

   • Loop over each element in nums using an index variable i. For each i, perform the following:
     • Maintain Stack for Non-Decreasing Order: While the stack is not empty and the element at nums[stack.peek()] is greater than nums[i], pop elements from the stack. This ensures that the stack only contains indices of elements that are in non-decreasing order up to the current index i.
     • Push Current Index onto Stack: Push the current index i onto the stack. This action signifies that nums[i] is now the last element of a valid subarray ending at i.
     • Update Count: Increment the count by the current size of the stack. The size of the stack represents the number of valid subarrays that end at the current element.

4. Return the Total Count: After completing the iteration over the array, return the count variable. This variable now contains the total number of valid subarrays within nums.

Algorithm Walkthrough

Let's consider the Input: nums = [1, 3, 2, 4, 1].

• Start: stack = [], count = 0

• i=0 (nums[i] = 1):

  • Stack is empty, so push 0.
  • stack = [0]
  • Increment count by stack size (1).
  • count = 1

• i=1 (nums[i] = 3):

  • 3 is greater than 1 (nums[stack.peek()]), so push 1.
  • stack = [0, 1]
  • Increment count by stack size (2).
  • count = 3

• i=2 (nums[i] = 2):

  • 2 is less than 3 (nums[stack.peek()]), pop 1.
  • stack = [0], then push 2.
  • stack = [0, 2]
  • Increment count by stack size (2).
  • count = 5

• i=3 (nums[i] = 4):

  • 4 is greater than 2 (nums[stack.peek()]), so push 3.
  • stack = [0, 2, 3]
  • Increment count by stack size (3).
  • count = 8

• i=4 (nums[i] = 1):

  • 1 is less than 4 (nums[stack.peek()]), pop 3.
  • 1 is less than 2 (nums[stack.peek()]), pop 2.
  • stack = [1], then push 4.
  • stack = [1, 4]
  • Increment count by stack size (2).
  • count = 10

The final count after the loop is 10.

Code

import java.util.Stack;

public class Solution {

  public int validSubarrays(int[] nums) {
    // Initialize a stack to store indices of elements
    Stack<Integer> stack = new Stack<>();
    // Initialize a variable to store the count of valid subarrays
    int count = 0;
    // Iterate through the array
    for (int i = 0; i < nums.length; i++) {
      // Remove indices from the stack where the corresponding element is greater than nums[i]
      while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
        stack.pop();
      }
      // Push the current index onto the stack
      stack.push(i);
      // Increment the count by the size of the stack (number of valid subarrays ending at index i)
      count += stack.size();
    }
    // Return the total count of valid subarrays
    return count;
  }

  public static void main(String[] args) {
    // Test cases
    Solution solution = new Solution();
    System.out.println(solution.validSubarrays(new int[] { 4, 3, 1 })); // Expected output: 3
    System.out.println(solution.validSubarrays(new int[] { 1, 3, 2, 4, 1 })); // Expected output: 10
    System.out.println(solution.validSubarrays(new int[] { 3, 3, 3 })); // Expected output: 6
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is , where (n) is the length of the input array nums. This efficiency is achieved because each element in the array is processed exactly once when it is pushed onto the stack and at most once when it is popped from the stack.

Space Complexity

The space complexity is in the worst case. This worst-case scenario occurs when the input array is sorted in non-decreasing order, causing all elements to be pushed onto the stack before any are popped.