Plates Between Candles solution and explanation
9 more videos on this problem
2055. Plates Between Candles | LEETCODE BIWEEKLY CONTEST 64 | LEETCODE | CODE EXPLAINERcode Explainer · 11:48 · 5K views
LeetCode 2055. Plates Between Candles - O(n + q)Kacy Codes · 16:31 · 5K views
2055. Plates Between Candles (Leetcode Medium)Programming Live with Larry · 11:56 · 3K views
【每日一题】LeetCode 2055. Plates Between CandlesHuifeng Guan · 12:24 · 1K views
Leetcode 2055: Plates Between CandlesNail the Tech Interview · 21:41 · 1K views
5900 | Plates Between Candles | LeetCode Biweekly Contest 64Gaurav Agrawal · 13:56 · 1K views
Plates between candles - leetcode 2055Algorhythm · 18:41 · 663 views
Leetcode 2055DailyLeetcode · 13:53 · 599 views
Plates Between Candles solution leetcodepreetam chatterjee · 0:13 · 64 views
LeetCode 2055: Plates Between CandlesAlitaCode · 34:02 · 17 views
The problem
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 is2, 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 <= 105sconsists of'*'and'|'characters.1 <= queries.length <= 105queries[i].length == 20 <= 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.
def platesBetweenCandles(s, queries):
n = len(s)
prefix_sum = [0] * n
left_candle = [-1] * n
right_candle = [-1] * n
# Compute prefix sums of plates
plate_count = 0
for i in range(n):
if s[i] == '*':
plate_count += 1
prefix_sum[i] = plate_count
if s[i] == '|':
left_candle[i] = i
elif i > 0:
left_candle[i] = left_candle[i - 1]
# Compute right candle positions
for i in range(n - 1, -1, -1):
if s[i] == '|':
right_candle[i] = i
elif i < n - 1:
right_candle[i] = right_candle[i + 1]
# Answer each query
results = []
for left, right in queries:
left = right_candle[left]
right = left_candle[right]
if left == -1 or right == -1 or left >= right:
results.append(0)
else:
results.append(prefix_sum[right] - prefix_sum[left])
return resultsfunction platesBetweenCandles(s, queries) {
const n = s.length;
const prefixSum = Array(n).fill(0);
const leftCandle = Array(n).fill(-1);
const rightCandle = Array(n).fill(-1);
let plateCount = 0;
for (let i = 0; i < n; i++) {
if (s[i] === '*') {
plateCount += 1;
}
prefixSum[i] = plateCount;
leftCandle[i] = (s[i] === '|') ? i : (i > 0 ? leftCandle[i - 1] : -1);
}
for (let i = n - 1; i >= 0; i--) {
rightCandle[i] = (s[i] === '|') ? i : (i < n - 1 ? rightCandle[i + 1] : -1);
}
const results = [];
for (const [left, right] of queries) {
const l = rightCandle[left];
const r = leftCandle[right];
if (l === -1 || r === -1 || l >= r) {
results.push(0);
} else {
results.push(prefixSum[r] - prefixSum[l]);
}
}
return results;
}#include <stdlib.h>
#include <string.h>
int* platesBetweenCandles(char *s, int** queries, int queriesSize, int* queriesColSize, int* returnSize){
int n = strlen(s);
int* prefixSum = (int*)calloc(n, sizeof(int));
int* leftCandle = (int*)calloc(n, sizeof(int));
int* rightCandle = (int*)calloc(n, sizeof(int));
int plateCount = 0;
for (int i = 0; i < n; i++) {
plateCount += (s[i] == '*');
prefixSum[i] = plateCount;
leftCandle[i] = (s[i] == '|') ? i : (i > 0 ? leftCandle[i - 1] : -1);
}
for (int i = n - 1; i >= 0; i--) {
rightCandle[i] = (s[i] == '|') ? i : (i < n - 1 ? rightCandle[i + 1] : -1);
}
int* result = (int*)malloc(queriesSize * sizeof(int));
*returnSize = queriesSize;
for (int i = 0; i < queriesSize; i++) {
int left = queries[i][0];
int right = queries[i][1];
left = rightCandle[left];
right = leftCandle[right];
if (left == -1 || right == -1 || left >= right) {
result[i] = 0;
} else {
result[i] = prefixSum[right] - prefixSum[left];
}
}
free(prefixSum);
free(leftCandle);
free(rightCandle);
return result;
}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.
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.
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.
import java.util.ArrayList;
import java.util.List;
public class PlatesBetweenCandles {
public int[] platesBetweenCandles(String s, int[][] queries) {
int n = s.length();
List<Integer> candles = new ArrayList<>();
int[] prefixSum = new int[n];
int plateCount = 0;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '*') {
plateCount++;
} else if (s.charAt(i) == '|') {
candles.add(i);
}
prefixSum[i] = plateCount;
}
int[] result = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int left = queries[i][0], right = queries[i][1];
int leftIndex = binarySearch(candles, left, true);
int rightIndex = binarySearch(candles, right, false);
if (leftIndex == -1 || rightIndex == -1 || leftIndex >= rightIndex) {
result[i] = 0;
} else {
result[i] = prefixSum[candles.get(rightIndex)] - prefixSum[candles.get(leftIndex)];
}
}
return result;
}
private int binarySearch(List<Integer> candles, int target, boolean isLeft) {
int start = 0, end = candles.size() - 1;
int result = -1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (candles.get(mid) >= target) {
result = mid;
if (isLeft) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
start = mid + 1;
}
}
return isLeft ? result : (result != -1 ? end : -1);
}
}using System;
using System.Collections.Generic;
public class Solution {
public int[] PlatesBetweenCandles(string s, int[][] queries) {
int n = s.Length;
List<int> candles = new List<int>();
int[] prefixSum = new int[n];
int plateCount = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '*') plateCount++;
else if (s[i] == '|') candles.Add(i);
prefixSum[i] = plateCount;
}
int[] results = new int[queries.Length];
for (int i = 0; i < queries.Length; i++) {
int left = queries[i][0], right = queries[i][1];
int l = FindPosition(candles, left, true);
int r = FindPosition(candles, right, false);
if (l == -1 || r == -1 || l >= r) {
results[i] = 0;
} else {
results[i] = prefixSum[candles[r]] - prefixSum[candles[l]];
}
}
return results;
}
private int FindPosition(List<int> candles, int target, bool isLeft) {
int low = 0, high = candles.Count - 1, result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (candles[mid] >= target) {
result = mid;
if (isLeft) high = mid - 1;
else low = mid + 1;
} else {
low = mid + 1;
}
}
return isLeft ? result : (result != -1 ? low : -1);
}
}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.
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.
Approach 3: Default Approach
class Solution {
public:
vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
int n = s.size();
vector<int> presum(n + 1);
for (int i = 0; i < n; ++i) presum[i + 1] = presum[i] + (s[i] == '*');
vector<int> left(n);
vector<int> right(n);
for (int i = 0, l = -1; i < n; ++i) {
if (s[i] == '|') l = i;
left[i] = l;
}
for (int i = n - 1, r = -1; i >= 0; --i) {
if (s[i] == '|') r = i;
right[i] = r;
}
vector<int> ans(queries.size());
for (int k = 0; k < queries.size(); ++k) {
int i = right[queries[k][0]];
int j = left[queries[k][1]];
if (i >= 0 && j >= 0 && i < j) ans[k] = presum[j] - presum[i + 1];
}
return ans;
}
};func platesBetweenCandles(s string, queries [][]int) []int {
n := len(s)
presum := make([]int, n+1)
for i := range s {
if s[i] == '*' {
presum[i+1] = 1
}
presum[i+1] += presum[i]
}
left, right := make([]int, n), make([]int, n)
for i, l := 0, -1; i < n; i++ {
if s[i] == '|' {
l = i
}
left[i] = l
}
for i, r := n-1, -1; i >= 0; i-- {
if s[i] == '|' {
r = i
}
right[i] = r
}
ans := make([]int, len(queries))
for k, q := range queries {
i, j := right[q[0]], left[q[1]]
if i >= 0 && j >= 0 && i < j {
ans[k] = presum[j] - presum[i+1]
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| 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. |
| Binary Search with Precomputed Candles | Time Complexity: O(n + q * log k), where k is the number of candles in the string. |
| Default Approach | – |
Complexity analysis
| 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 |
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.