Plates Between Candles

Plates Between Candles

What is this problem about?

The Plates Between Candles problem gives you a string of plates ('*') and candles ('|'). For each query [l, r], count the number of plates between the leftmost and rightmost candles in the substring s[l..r]. This coding problem precomputes prefix plate counts and nearest candle positions for O(1) per query. The array, binary search, string, and prefix sum interview pattern is the core.

Why is this asked in interviews?

Amazon, Oracle, Google, and Adobe ask this because it tests offline query optimization — precomputing structures to answer many queries efficiently. The combination of prefix sums and nearest candle arrays gives O(n) preprocessing and O(1) per query.

Algorithmic pattern used

Prefix sums + nearest candle precomputation. Precompute: prefix_plates[i] = plates in s[0..i-1]. left_candle[i] = nearest candle at or before index i. right_candle[i] = nearest candle at or after index i. For query [l, r]: find lc = right_candle[l] (first candle in range), rc = left_candle[r] (last candle in range). If lc < rc: plates = prefix_plates[rc] - prefix_plates[lc+1] (plates strictly between). Else: 0 plates.

Example explanation

s="|||". prefix_plates=[0,1,2,2,3,4,4,5,6,7,7]. Query [2,8]: s[2..8]="|". right_candle[2]=8? No: s[8]='|'. Wait: s="|||" — indices 0-9. s[2]='|', s[5]='|', s[9]='|'. right_candle[2]=2. left_candle[8]=5. Plates between indices 2 and 5: prefix_plates[5]-prefix_plates[3]=4-2=2.

Common mistakes candidates make

• Computing left/right candle positions for each query (O(n) per query instead of O(1)).
• Off-by-one in plate count between candles: exclude the candles themselves.
• Not handling queries with no candles in range (return 0).
• Incorrect prefix sum indexing (0-indexed vs 1-indexed).

Interview preparation tip

"Count elements between boundaries" problems always precompute: (1) prefix counts of the element type, (2) nearest boundary positions. The pair (right_candle[l], left_candle[r]) gives the innermost boundaries of the query range. Practice similar problems: "count elements between two specific values in range," "count words between punctuation." Precomputation is the universal optimization strategy for multi-query problems.