Count Prime-Gap Balanced Subarrays - Solution & Explanation

Problem Overview: You are given an integer array and need to count subarrays where the gaps between consecutive prime elements remain balanced. A prime gap is the distance between indices of adjacent prime numbers inside the subarray. The task is to efficiently count all subarrays where these gaps satisfy the balancing condition.

Approach 1: Brute Force with Prime Tracking (O(n²) time, O(n) space)

Enumerate every possible subarray using two nested loops. While expanding the right boundary, maintain a list of indices where elements are prime. Each time a new prime appears, compute the gap between it and the previous prime. Track the minimum and maximum gap seen in the current subarray and check if the balancing condition holds. This method directly simulates the definition but recomputes gaps frequently, making it too slow for large inputs.

Approach 2: Sliding Window + Monotonic Queues (O(n) time, O(n) space)

First determine which elements are prime using a fast primality check or a sieve from number theory. As you scan the array, maintain a sliding window over indices. Each time you encounter a prime, compute the gap between this index and the previous prime in the window. Store these gaps in two monotonic queues: one increasing queue for the minimum gap and one decreasing queue for the maximum gap.

While expanding the window, update both queues with the new gap. If the window becomes invalid (the maximum gap differs from the minimum gap), move the left pointer forward and remove outdated gaps from the queues. Because each gap enters and leaves the queues once, the total work is linear. This technique combines a sliding window with a monotonic queue to maintain range statistics in constant time.

The key insight is that the condition depends only on prime gaps, not the entire subarray. By maintaining the min and max gap incrementally, you avoid recomputing values for every subarray. Each pointer moves at most n times, so the scan remains efficient even for large arrays.

Recommended for interviews: Interviewers expect the sliding window with monotonic queues. The brute force approach shows you understand how prime gaps are defined and how subarrays are enumerated. The optimized window demonstrates mastery of range tracking inside a dynamic window, a common pattern in advanced array problems.