Given an array of strings words, a word is a vowel string if it starts and ends with a vowel (a, e, i, o, u). For each query [l, r], count how many vowel strings appear in words[l..r] (inclusive).

Engineering takeaway. This is the classic range-query pattern — you see it in dashboards, analytics, and aggregations everywhere. The naive "loop over the range for every query" is correct but slow when both the array and the query count reach 10^5. A prefix sum precomputes cumulative totals once, so any range answer becomes a single subtraction. If you remember one technique from this post, make it this one.

Intuition

Each word is either a vowel string or it isn't — so we can collapse words into an array of 0s and 1s. The question becomes: "sum the values between two indices", which is the textbook use case for prefix sums.

For example, the prefix sum of [1, 2, 3, 4, 5] is [0, 1, 3, 6, 10, 15], where prefix[i] = prefix[i-1] + nums[i]. The sum between s and e is then prefix[e+1] - prefix[s].

Why the extra leading 0? It lets prefix[e+1] - prefix[s] work when s = 0, without a special case.

Approach

  1. Build a Set of vowels for O(1) lookups.
  2. Build prefixSum, where prefixSum[i] is the number of vowel strings among the first i words.
  3. For each query [l, r], answer prefixSum[r+1] - prefixSum[l].
function vowelStrings(words: string[], queries: number[][]): number[] {
  const vowelSet = new Set(["a", "e", "i", "o", "u"]);
 
  const prefixSum: number[] = [0];
  for (const word of words) {
    const isVowelString =
      vowelSet.has(word[0]) && vowelSet.has(word[word.length - 1]);
    prefixSum.push(prefixSum[prefixSum.length - 1] + (isVowelString ? 1 : 0));
  }
 
  return queries.map(([start, end]) => prefixSum[end + 1] - prefixSum[start]);
}

Complexity

  • Time: O(n + m) — one pass to build the prefix sum (n words), then O(1) per query (m queries).
  • Space: O(n) — for the prefix-sum array.

The lesson

Before you write a loop inside a loop, ask whether the query pattern is repeated and independent. If it is, precompute. Prefix sums are the simplest member of a family that includes 2D prefix sums, difference arrays, and Fenwick trees — all built on the same insight: pay once up front, answer queries instantly.