2444. Count Subarrays With Fixed Bounds


Problem Description

You are provided with an array of integers called nums, and two specific integers known as minK and maxK. The goal is to find and count the number of subarrays within nums that adhere to two criteria:

  • The smallest number in the subarray is exactly minK.
  • The largest number in the subarray is exactly maxK.

To clarify, a subarray is defined as a contiguous segment of the array. It is essential to understand that any subarray meeting these conditions is considered a "fixed-bound subarray". The solution requires you to return the total count of such fixed-bound subarrays.

Intuition

The problem is essentially asking us to isolate segments of the nums array where the range of values is strictly bounded between minK and maxK (both inclusive). To solve this, we need to keep track of certain positions within our array:

  • The most recent positions where minK and maxK were found, since these will be the bounds of our subarrays.
  • The last position where a value outside the acceptable range (less than minK or greater than maxK) was encountered because this will help us determine the starting point of a new possible subarray.

We iterate through the array while tracking these positions. For each new element:

  1. If the current element is out of bounds (< minK or > maxK), we mark the current position as the starting point for future valid subarrays.
  2. If the current element is equal to minK, we update the position tracking minK.
  3. If the current element is equal to maxK, we update the position tracking maxK.

The key insight here is that a new valid subarray can be formed at each step if the most recent minK and maxK are found after the last out-of-bounds value. The length of each new subarray added will be from the latest out-of-bound index until the minimum of the indices where minK and maxK were most recently found.

By performing these steps for each element, we are effectively counting all possible fixed-bound subarrays without having to explicitly list or generate them. This makes the solution efficient as it has a linear complexity with respect to the length of the input array.

Solution Approach

The solution approach can be broken down into a few distinct steps that relate to the iteration over the nums array:

  1. Initialization: We start by initializing three pointers j1, j2, and k to -1.

    • j1 will keep track of the most recent position where minK has been found.
    • j2 will keep track of the most recent position where maxK has been found.
    • k signifies the most recent index before the current position where a number not within the minK and maxK range was discovered.
  2. Iteration and Tracking: The program iterates over the array nums using a for-loop, with the variable i representing the index, and v the value at each index.

    • If v is not within the range [minK, maxK] (v < minK or v > maxK), we update k to the current index i, since valid subarrays cannot extend beyond this point.

    • If v equals minK, we update j1 to be the current index i. Similarly, if v equals maxK, we update j2.

    • Key Algorithm: After updating the pointers, we calculate the additional number of valid subarrays that include the element v at index i, by calculating max(0, min(j1, j2) - k). This effectively counts the number of new subarrays where minK and maxK are the minimum and maximum values respectively, and which do not include any out-of-bound elements before k.

  3. Incremental Summation: We accumulate this count in ans with ans += max(0, min(j1, j2) - k).

  4. Result: After the loop concludes, ans holds the total number of fixed-bound subarrays that can be found in nums. We return ans as the final result.

By employing pointers to keep track of recent occurrences of minK and maxK, and the cut-off point for valid subarrays (k), the solution efficiently leverages a sliding window technique to count subarrays without actually constructing them. The use of pointers (j1, j2, and k) to delineate bounds of subarrays is a common pattern in array processing problems and is a cornerstone of this solution's efficiency since it means we only need to iterate through the array once, giving us a time complexity of O(n).

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider the following array nums, with minK set to 2 and maxK set to 5:

1nums = [1, 2, 3, 4, 5, 1, 2, 5, 3]
2minK = 2
3maxK = 5

Now let's walk through the procedure step-by-step:

  1. Initialization:

    • j1 = -1 (most recent minK position)
    • j2 = -1 (most recent maxK position)
    • k = -1 (last out-of-bound position)
    • ans = 0 (accumulator for the count of valid subarrays)
  2. Iteration and Tracking:

    inums[i]Actionj1j2kValid Subarray lengthans
    01out of range, update k to i-1-10max(0, min(-1, -1) - 0) = 00
    12minK found, update j1 to i1-10max(0, min(1, -1) - 0) = 00
    23within range, no pointer update1-10max(0, min(1, -1) - 0) = 00
    34within range, no pointer update1-10max(0, min(1, -1) - 0) = 00
    45maxK found, update j2 to i140max(0, min(1, 4) - 0) = 11
    51out of range, update k to i145max(0, min(1, 4) - 5) = 01
    62minK found, update j1 to i645max(0, min(6, 4) - 5) = 01
    75maxK found, update j2 to i675max(0, min(6, 7) - 5) = 12
    83within range, no pointer update675max(0, min(6, 7) - 5) = 13

Upon completion, ans = 3, which is the total count of fixed-bound subarrays within nums that have minK as their minimum and maxK as their maximum.

The fixed-bound subarrays accounted for in this example are:

  • [2, 3, 4, 5] starting at index 1
  • [2, 5] starting at index 6
  • [2, 5, 3] starting at index 6

Each time we encounter a valid subarray, we update our accumulator ans, which eventually gives us the count of all valid subarrays by the time we reach the end of the array.

Python Solution

1from typing import List
2
3class Solution:
4    def count_subarrays(self, nums: List[int], min_k: int, max_k: int) -> int:
5        # Initialize pointers for tracking the positions of min_k, max_k, and out-of-range elements
6        last_min_k = last_max_k = last_out_of_range = -1
7      
8        # Initialize the counter for the valid subarrays
9        valid_subarrays_count = 0
10      
11        # Iterate through the list, checking each number against min_k and max_k
12        for index, value in enumerate(nums):
13            # Invalidate the subarray if the value is out of the specified range
14            if value < min_k or value > max_k:
15                last_out_of_range = index
16
17            # Update the last seen index for min_k, if found
18            if value == min_k:
19                last_min_k = index
20
21            # Update the last seen index for max_k, if found
22            if value == max_k:
23                last_max_k = index
24          
25            # Add to the count the number of valid subarrays ending with the current element
26            # which is determined by the smallest index among last_min_k and last_max_k after the 
27            # last out-of-range element
28            valid_subarrays_count += max(0, min(last_min_k, last_max_k) - last_out_of_range)
29      
30        # Return the total count of valid subarrays
31        return valid_subarrays_count
32

Java Solution

1class Solution {
2    public long countSubarrays(int[] nums, int minK, int maxK) {
3        long totalCount = 0; // Variable to store the total count of subarrays
4        int lastMinIndex = -1; // Index of the last occurrence of minK
5        int lastMaxIndex = -1; // Index of the last occurrence of maxK
6        int lastInvalidIndex = -1; // Index of the last element not in [minK, maxK]
7
8        // Iterate over each element in the array
9        for (int currentIndex = 0; currentIndex < nums.length; ++currentIndex) {
10            // If the current element is outside of the [minK, maxK] range, update lastInvalidIndex
11            if (nums[currentIndex] < minK || nums[currentIndex] > maxK) {
12                lastInvalidIndex = currentIndex;
13            }
14
15            // If the current element is equal to minK, update lastMinIndex
16            if (nums[currentIndex] == minK) {
17                lastMinIndex = currentIndex;
18            }
19
20            // If the current element is equal to maxK, update lastMaxIndex
21            if (nums[currentIndex] == maxK) {
22                lastMaxIndex = currentIndex;
23            }
24
25            // Calculate the number of valid subarrays ending at the current index
26            // It is the distance between the last invalid index and the minimum of the last occurrences of minK and maxK
27            totalCount += Math.max(0, Math.min(lastMinIndex, lastMaxIndex) - lastInvalidIndex);
28        }
29
30        return totalCount; // Return the total count of valid subarrays
31    }
32}
33

C++ Solution

1class Solution {
2public:
3    // Counts and returns the number of subarrays where the minimum value is at least minK and the maximum value is at most maxK.
4    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
5        long long answer = 0; // Variable to store the final count of subarrays
6        int lastMinIndex = -1; // Index of the last occurrence of minK
7        int lastMaxIndex = -1; // Index of the last occurrence of maxK
8        int lastIndexOutsideRange = -1; // Index of the last number that is outside the [minK, maxK] range
9
10        // Iterate through the array to count valid subarrays
11        for (int i = 0; i < nums.size(); ++i) {
12            // If current element is outside the [minK, maxK] range, update the index
13            if (nums[i] < minK || nums[i] > maxK) lastIndexOutsideRange = i;
14            // If current element equals minK, update the index of the last occurrence of minK
15            if (nums[i] == minK) lastMinIndex = i;
16            // If current element equals maxK, update the index of the last occurrence of maxK
17            if (nums[i] == maxK) lastMaxIndex = i;
18
19            // Count subarrays ending at index i which have minK and maxK within them
20            answer += max(0, min(lastMinIndex, lastMaxIndex) - lastIndexOutsideRange);
21        }
22
23        return answer; // Return the total count of valid subarrays
24    }
25};
26

Typescript Solution

1function countSubarrays(nums: number[], minK: number, maxK: number): number {
2    let result = 0; // This will hold the final count of subarrays
3    let minIndex = -1; // Stores the latest index of the element equal to minK
4    let maxIndex = -1; // Stores the latest index of the element equal to maxK
5    let invalidIndex = -1; // Stores the latest index of the element outside of the [minK, maxK] range
6
7    nums.forEach((number, index) => {
8        if (number === minK) {
9            minIndex = index; // Update minIndex when we find an element equal to minK
10        }
11        if (number === maxK) {
12            maxIndex = index; // Update maxIndex when we find an element equal to maxK
13        }
14        if (number < minK || number > maxK) {
15            invalidIndex = index; // Update invalidIndex for numbers outside the range
16        }
17
18        // Calculate the number of valid subarrays that end at the current index
19        result += Math.max(Math.min(minIndex, maxIndex) - invalidIndex, 0);
20    });
21
22    return result; // Return the total count of valid subarrays
23}
24

Time and Space Complexity

The provided code snippet is designed to count the number of subarrays within an array nums where the minimum element is minK and the maximum element is maxK. To analyze the computational complexity, we will examine the time taken by each component of the code and then aggregate these components to get the final complexity.

Time Complexity:

The time complexity of the code can be determined by analyzing the for loop since it is the only part of the code that iterates through the list of elements.

  • The for loop iterates through each element of nums exactly once, meaning the loop runs for n iterations, where n is the number of elements in nums.
  • Inside the for loop, the code performs constant-time checks and assignments (such as comparison, assignment, and max operations), and these do not depend on the size of the input.

Because there are no nested loops or recursive calls, the time complexity is directly proportional to the number of elements in the nums list.

Therefore, the time complexity of the code is O(n).

Space Complexity:

For space complexity, we look at the extra space required by the algorithm, not including the input and output:

  • The code uses a fixed number of variables (j1, j2, k, ans, and i), and no additional data structures that grow with the input size are used.
  • The space required for these variables is constant and does not scale with the size of the input list nums.

As a result, the space complexity of the code is O(1), meaning it requires a constant amount of extra space.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫