Skip to main content
Talentd

Plates Between Candles - Solution & Explanation

MediumArrayStringBinary SearchPrefix Sum10 min readAsked at: Amazon, Oracle, Adobe
Practice this problem

Problem Statement

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.

  • For example, 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:

ex-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:

ex-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 <= 105
  • s consists of '*' and '|' characters.
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 0 <= lefti <= righti < s.length

Approach Overview

Problem 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 1: Prefix Sum with Two-Pass Preprocessing

This approach involves preprocessing the input string with two arrays, one for prefix sums of plates and two others to find the nearest left and right candles from any position. This preprocessing enables efficient query execution.

In the Python implementation, we first calculate a prefix_sum to track the cumulative number of plates ('*') up to every position. left_candle and right_candle arrays are used to quickly find the nearest candle positions on the left and right of each index. For each query, use these precomputed arrays to determine the number of plates located strictly between the nearest candles.

Code

PythonJavaScriptC

Python

JavaScript

C

Complexity

Time Complexity: O(n + q), where n is the length of the string and q is the number of queries.
Space Complexity: O(n) due to the auxiliary arrays used for preprocessing.

Try this approach in the editor →

Approach 2: Binary Search with Precomputed Candles

This approach leverages a list of precomputed candle positions and uses binary search to efficiently determine the spans of plates that are bounded by candles for each query.

The Java code uses a list to store the indices of the candles found in the string. It leverages binary search to swiftly pinpoint the leftmost and rightmost candle indices valid within the range of each query. The prefix sum array is used to calculate the number of plates, since it provides cumulative counts of plates up to specific indices.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n + q * log k), where k is the number of candles in the string.
Space Complexity: O(n), due to the prefix sums and candle caches.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Sum with Two-Pass Preprocessing

Time Complexity: O(n + q), where n is the length of the string and q is the number of queries.
Space Complexity: O(n) due to the auxiliary arrays used for preprocessing.

Binary Search with Precomputed Candles

Time Complexity: O(n + q * log k), where k is the number of candles in the string.
Space Complexity: O(n), due to the prefix sums and candle caches.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 CandlesO(n + q)O(n)Best general solution when many queries must be answered efficiently
Binary Search on Candle IndicesO(n + q log n)O(n)Good when candle positions are stored separately and binary search is convenient

Video Solution

2055. Plates Between Candles | LEETCODE BIWEEKLY CONTEST 64 | LEETCODE | CODE EXPLAINER • code Explainer • 5,678 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Plates Between Candles easy or hard?
Plates Between Candles is considered a medium difficulty problem. The challenge is recognizing that repeated range queries require preprocessing with prefix sums and boundary tracking instead of scanning each query range.
How to solve Plates Between Candles in O(n)?
Precompute a prefix sum array counting plates and track the nearest candle to the left and right for every position. For a query [l, r], shift l to the nearest right candle and r to the nearest left candle. The number of plates between them is prefix[r] minus prefix[l], giving constant-time queries after O(n) preprocessing.
Plates Between Candles Python or Java solution?
Most implementations use a prefix sum array plus nearest candle preprocessing. The logic is language-independent and commonly written in Python, Java, JavaScript, C, or C#. After preprocessing, each query simply subtracts two prefix values to count plates between candle boundaries.
What is the best approach for Plates Between Candles?
The prefix sum with nearest candle preprocessing is the most efficient approach. It builds a prefix count of plates and two arrays that store the closest candle to the left and right of every index. Each query then becomes a constant-time subtraction between two prefix values, giving O(n + q) total complexity.
What data structure is used in Plates Between Candles?
The main structures are prefix sum arrays and helper arrays storing nearest candle indices. Some solutions also store candle positions in a sorted list and apply binary search to locate boundaries for each query.
What is the time complexity of Plates Between Candles?
The optimal solution runs in O(n + q) time where n is the string length and q is the number of queries. Preprocessing the prefix sums and nearest candles takes O(n), and each query is answered in O(1). A binary search alternative runs in O(n + q log n).
Is Plates Between Candles asked at Google, Amazon, or Meta?
This style of query-processing problem appears frequently in interviews at large companies such as Amazon and Google. It tests prefix sums, preprocessing techniques, and efficient range queries over arrays or strings.

Ready to solve this problem?

Practice Plates Between Candles with our built-in code editor and test cases.

Practice on FleetCode
Previous

Can Make Palindrome from Substring

Next

Find First and Last Position of Element in Sorted Array