algoadvance

Leetcode 795. Number of Subarrays with Bounded Maximum

Problem Statement

Given an integer array nums and two integers left and right, return the number of contiguous subarrays where the value of the maximum array element is in the range [left, right].

Clarifying Questions

  1. Input Constraints:
    • What is the range of values for the elements in nums?
    • What is the length range for the nums array?
    • Are left and right inclusive?
  2. Edge Cases:
    • How should we handle empty arrays?
    • What should we return if no subarray meets the criteria?

Code

#include <vector>

class Solution {
public:
    int numSubarrayBoundedMax(std::vector<int>& nums, int left, int right) {
        return countSubarrays(nums, right) - countSubarrays(nums, left - 1);
    }

private:
    int countSubarrays(std::vector<int>& nums, int bound) {
        int count = 0, current = 0;
        for (int num : nums) {
            if (num <= bound) {
                current++;
            } else {
                current = 0;
            }
            count += current;
        }
        return count;
    }
};

Strategy

To solve this problem effectively, we can break it down into simpler parts:

  1. Counting Function:
    • We define a helper function countSubarrays that counts the number of subarrays where the maximum element is less than or equal to a given bound.
    • It uses a sliding window approach to count contiguous subarrays.
  2. Core Logic:
    • Use the helper function to count subarrays up to the right bound and then subtract the count of subarrays up to left - 1.
    • This way, we determine the subarrays specifically within the [left, right] range by exclusion.

Time Complexity

The time complexity of this solution is O(n), where n is the length of the nums array. This is because we only iterate through the array a limited number of times (specifically, twice) to gather the required counts. Each element is processed in constant time during each iteration, making this approach efficient for large input sizes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI