Count Prime-Gap Balanced Subarrays - Practice Coding Problems

Count Prime-Gap Balanced Subarrays - Problem

Array Math Queue Sliding Window Number Theory Monotonic Queue Medium

You are given an integer array nums and an integer k.

A subarray is called prime-gap balanced if:

It contains at least two prime numbers, and
The difference between the maximum and minimum prime numbers in that subarray is less than or equal to k.

Return the count of prime-gap balanced subarrays in nums.

Note: A subarray is a contiguous non-empty sequence of elements within an array. A prime number is a natural number greater than 1 with only two factors, 1 and itself.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,5,7], k = 4

› Output: 6

💡 Note: All subarrays with ≥2 primes: [2,3] gap=1≤4✓, [2,3,5] gap=3≤4✓, [2,3,5,7] gap=5>4✗, [3,5] gap=2≤4✓, [3,5,7] gap=4≤4✓, [5,7] gap=2≤4✓. Total: 6 valid subarrays (note: [2,3,5,7] has gap 7-2=5 > 4)

Example 2 — Small Gap

$ Input: nums = [3,5,11,13], k = 2

› Output: 2

💡 Note: Subarrays with ≥2 primes: [3,5] gap=2≤2✓, [3,5,11] gap=8>2✗, [5,11] gap=6>2✗, [11,13] gap=2≤2✓. Only 2 valid subarrays

Example 3 — Few Primes

$ Input: nums = [2,4,6,3], k = 10

› Output: 1

💡 Note: Only primes are 2 and 3. Only one subarray contains both: [2,4,6,3] with gap 3-2=1≤10✓. Total: 1 valid subarray

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 1000
0 ≤ k ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array with numbers and gap limit k

Process

Find subarrays with ≥2 primes and max-min prime ≤ k

Output

Count of valid prime-gap balanced subarrays

Key Takeaway

🎯 Key Insight: Only consider prime numbers and use gap constraint to efficiently prune invalid subarrays

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to recognize this as a subarray counting problem with constraints on prime numbers. The optimal approach uses sliding window with prime preprocessing to avoid redundant calculations. Time: O(n² × √m), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Subarrays	O(n³ × √m)	O(1)	Check every possible subarray and count primes with valid gap
Optimized Sliding Window	O(n² × √m)	O(n)	Use sliding window with prime preprocessing to efficiently count valid subarrays

Brute Force - Check All Subarrays — Algorithm Steps

Generate all possible subarrays
For each subarray, find all prime numbers
Check if at least 2 primes exist and max-min ≤ k

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Create all possible contiguous subarrays

Find Primes

Identify prime numbers in each subarray

Check Gap

Verify if max-min prime difference ≤ k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int isPrime(int n) {
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int solution(int* nums, int numsSize, int k) {
    int count = 0;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i; j < numsSize; j++) {
            int primes[1000];
            int primeCount = 0;
            
            for (int idx = i; idx <= j; idx++) {
                if (isPrime(nums[idx])) {
                    primes[primeCount++] = nums[idx];
                }
            }
            
            if (primeCount >= 2) {
                int maxPrime = primes[0];
                int minPrime = primes[0];
                for (int p = 0; p < primeCount; p++) {
                    if (primes[p] > maxPrime) maxPrime = primes[p];
                    if (primes[p] < minPrime) minPrime = primes[p];
                }
                if (maxPrime - minPrime <= k) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    char* zelmoricad = line;  // Store input midway
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(zelmoricad + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³ × √m)

O(n²) subarrays, each takes O(n) to scan, and O(√m) to check if number m is prime

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables for counting

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler