FAANGPrep Sprint
Count Vowels in Ranges
Answer range queries counting the words that start and end with a vowel — one pass to build a prefix count, then one subtraction per query.
MediumSolve on LeetCode
Problem Understanding
You are given a string array words and a 2D array queries. Each query [l, r] asks for the number of strings in words[l...r] that start and end with a vowel.
We need to answer many queries efficiently.
Strategy
- Preprocessing: Create a boolean/integer array
is_validwhereis_valid[i] = 1ifwords[i]starts and ends with a vowel, else 0. - Prefix Sum: Compute prefix sum
Pofis_valid.P[i]= count of valid words inwords[0...i-1]. - Query: Answer for
[l, r]isP[r+1] - P[l].
Vowels: a, e, i, o, u
Interactive Visualization
5 WORDS · 3 QUERIES
ALLOCATE PREFIX
words
aba
0
bcb
1
ece
2
aa
3
e
4
valid (0/1)
-
0
-
1
-
2
-
3
-
4
prefix
0
0
0
1
0
2
0
3
0
4
0
5
Query
—
Answer
—
ans
No query answered yet
Allocate prefix with 6 zeros: prefix[i] will count the vowel strings among the first i words
Next
"aba" starts with 'a' and ends with 'a': both vowels, so it counts
Words
Queries
See how we can answer multiple range queries in O(1) time after O(N) preprocessing.