Watch 10 video solutions for Plates Between Candles, a medium level problem involving Array, String, Binary Search. This walkthrough by Kacy Codes has 5,540 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters '*' and '|' only, where a '*' represents a plate and a '|' represents a candle.
You are also given a 0-indexed 2D integer array queries where queries[i] = [lefti, righti] denotes the substring s[lefti...righti] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.
s = "||**||**|*", and a query [3, 8] denotes the substring "*||**|". The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.Return an integer array answer where answer[i] is the answer to the ith query.
Example 1:
Input: s = "**|**|***|", queries = [[2,5],[5,9]] Output: [2,3] Explanation: - queries[0] has two plates between candles. - queries[1] has three plates between candles.
Example 2:
Input: s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]] Output: [9,0,0,0,0] Explanation: - queries[0] has nine plates between candles. - The other queries have zero plates between candles.
Constraints:
3 <= s.length <= 105s consists of '*' and '|' characters.1 <= queries.length <= 105queries[i].length == 20 <= lefti <= righti < s.lengthProblem Overview: You get a string containing plates (*) and candles (|). For each query [l, r], count how many plates lie strictly between two candles inside that range. Plates that are not enclosed by candles do not count.
Approach 1: Prefix Sum with Two-Pass Preprocessing (O(n + q) time, O(n) space)
This is the optimal approach for most implementations. First build a prefix sum array where prefix[i] stores how many plates appear up to index i. Then preprocess two helper arrays: leftCandle[i] (nearest candle to the left) and rightCandle[i] (nearest candle to the right). For a query [l, r], move l to the nearest candle on the right and r to the nearest candle on the left. If valid candles exist, the answer is prefix[r] - prefix[l]. Each query becomes constant time after preprocessing, which makes this approach ideal when the query count is large.
Approach 2: Binary Search with Precomputed Candles (O(n + q log n) time, O(n) space)
Instead of storing nearest candles for every index, store the indices of all candles in a list while scanning the string once. For each query, use binary search to find the first candle index greater than or equal to l and the last candle index less than or equal to r. These two candles form the valid boundary. Once the boundaries are known, compute plates between them using a prefix plate count. Binary search keeps the query logic clean and works well when you already maintain sorted candle positions.
Approach 3: Direct Range Scan (Brute Force) (O(n * q) time, O(1) space)
For every query, iterate from l to r, track the first and last candles, and count plates between them. This approach uses simple iteration over the array/string characters. The logic is straightforward but inefficient because the same range segments are repeatedly scanned for different queries.
Recommended for interviews: The prefix sum with two-pass preprocessing is the expected solution. It shows you can combine prefix aggregation with boundary preprocessing to reduce per-query work to O(1). Mentioning the brute-force approach demonstrates baseline reasoning, but implementing the prefix-sum optimization signals strong problem-solving and scalability awareness.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Range Scan (Brute Force) | O(n * q) | O(1) | Useful for understanding the problem or when constraints are very small |
| Prefix Sum with Nearest Candles | O(n + q) | O(n) | Best general solution when many queries must be answered efficiently |
| Binary Search on Candle Indices | O(n + q log n) | O(n) | Good when candle positions are stored separately and binary search is convenient |