'2025/04/26'에 해당되는 글 1건

Leetcode Problem:

• Count Subarrays With Fixed Bounds

Summary

• Count the number of fixed-bound subarrays in a given array where the minimum and maximum values are within a specified range.

Approach

• The approach used is to maintain two pointers (jmin and jmax) to track the minimum and maximum values within the current window, and another pointer (jbad) to track the first bad element
• The result is updated by summing up the number of valid subarrays that can be formed with the current window.

Complexity

• O(n)

Explanation

• The time complexity is O(n) because each element in the array is visited once
• The space complexity is O(1) because only a constant amount of space is used to store the pointers and the result.

Solution Code:

class Solution {
public:
        long long countSubarrays(vector& A, int minK, int maxK) {
        long res = 0, jbad = -1, jmin = -1, jmax = -1, n = A.size();
        for (int i = 0; i < n; ++i) {
            if (A[i] < minK || A[i] > maxK) jbad = i;
            if (A[i] == minK) jmin = i;
            if (A[i] == maxK) jmax = i;
            res += max(0L, min(jmin, jmax) - jbad);
        }
        return res;
    }
};