2444. Count Subarrays With Fixed Bounds

HardView on LeetCode

Array Sliding Window Monotonic Stack

Time: O(n)

Space: O(1)

Intuition

Count subarrays with at least k odd numbers. Complement: at most k-1 odd numbers. Answer = total - atMost(k-1).

Algorithm

1atMost(k) = count subarrays with <= k odd numbers using sliding window.
2Answer = atMost(n) - atMost(k-1)... wait: at least k = total - atMost(k-1).

Common Pitfalls

•Use atLeast(k) = total - atMost(k-1). Sliding window for atMost.

2444.cs

// Approach: Track last out-of-bound, last minK, last maxK indices; count valid left endpoints.
// Time: O(n) Space: O(1)

public class Solution
{
    public long CountSubarrays(int[] nums, int minK, int maxK)
    {
        long ans = 0;
        int badi = -1, mini = -1, maxi = -1, n = nums.Length;

        for (int i = 0; i < n; i++)
        {
            if (nums[i] < minK || nums[i] > maxK)
                badi = i;

            if (nums[i] == minK)
                mini = i;

            if (nums[i] == maxK)
                maxi = i;

            ans += Math.Max(0, Math.Min(mini, maxi) - badi);
            // Console.WriteLine("i value: " + i + " ans value: " + ans);
        }

        return ans;
    }
}

Was this solution helpful?