Count Subarrays With Fixed Bounds

Count Subarrays With Fixed Bounds

What is this problem about?

The "Count Subarrays With Fixed Bounds interview question" is a difficult counting task. You are given an array and two integers, minK and maxK. A subarray is considered valid if its minimum element is exactly minK and its maximum element is exactly maxK, and all elements are within the range [minK, maxK]. You need to count the total number of such valid subarrays.

Why is this asked in interviews?

Tech giants like Adobe, Google, and Meta ask the "Count Subarrays With Fixed Bounds coding problem" because it requires tracking three different "last seen" indices simultaneously. It is a true test of linear-time logic and the ability to handle multiple constraints in a single pass. It evaluations "Sliding Window interview pattern" and "Two Pointers" skills at a high level.

Algorithmic pattern used

This problem is solved using a Single Pass with Boundary Tracking.

1. Invalid Index: Keep track of the last index badIdx where an element was outside the range [minK, maxK].
2. Min/Max Tracking: Keep track of the most recent index minIdx where minK was seen and maxIdx where maxK was seen.
3. Logic: For every index i:
   • If arr[i] is out of range, update badIdx = i.
   • If arr[i] == minK, update minIdx = i.
   • If arr[i] == maxK, update maxIdx = i.
   • The number of valid subarrays ending at i is max(0, min(minIdx, maxIdx) - badIdx). This formula calculates how many starting points exist between the last "bad" element and the first occurrence of both required bounds.

Example explanation

Array: [1, 3, 5, 2, 7, 5], minK=1, maxK=5

• i=0 (1): minIdx=0, badIdx=-1. (No max seen yet).
• i=1 (3): OK.
• i=2 (5): maxIdx=2.
  • Valid start points: min(0, 2) - (-1) = 1. Subarray: [1, 3, 5].
• i=3 (2): OK.
  • Valid start points: min(0, 2) - (-1) = 1. Subarray: [1, 3, 5, 2].
• i=4 (7): badIdx=4. (Resetting). Result: 2.

Common mistakes candidates make

• Multiple Passes: Trying to solve the min and max constraints separately.
• Complex Windowing: Using a full sliding window with frequency maps when only the "last seen" positions are needed.
• Integer Overflow: Forgetting that the number of valid subarrays can be $O(N^2)$, which requires a 64-bit return type.

Interview preparation tip

Practice problems where you track the "last valid" or "last invalid" index. This "Two Pointers interview pattern" is a powerful way to solve complex subarray constraints in $O(N)$ time with $O(1)$ extra space.