Plates Between Candles
Plates Between Candles is a medium arrays & hashing problem solved with the prefix sum strategy pattern.
The best approach, optimal (prefix sums + nearest candles), runs in O(n + q) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan each query) up.
Problem
A table is described by a string s made of plates '*' and candles '|'. You also get a list of queries, where queries[i] = [left, right] names the substring s[left..right] (both ends included).
For each query, count the plates in that substring that sit between two candles of the same substring, meaning there is at least one candle to the plate’s left and at least one candle to its right, both inside [left, right].
Return an array with the answer to each query.
Examples
Example 1
- Input
s = "*|**|*|*", queries = [[0, 7], [1, 3], [2, 6]]- Output
[3, 0, 1]- Why
- In [0, 7] the outer candles are at 1 and 6, with 3 plates between them. [1, 3] holds only one candle. In [2, 6] the candles at 4 and 6 enclose 1 plate.
Example 2
- Input
s = "|***|**|", queries = [[0, 7], [1, 6], [0, 4]]- Output
[5, 0, 3]- Why
- The whole string has candles at 0 and 7 with 5 plates inside. [1, 6] contains only the candle at 4. [0, 4] has 3 plates between the candles at 0 and 4.
Constraints
3 <= s.length <= 10^5scontains only'*'and'|'1 <= queries.length <= 10^5queries[i] = [left, right]with0 <= left <= right < s.length
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan each query) | O(n · q) | O(1) |
| Optimal (prefix sums + nearest candles) | O(n + q) | O(n) |
1Brute force (scan each query)
O(n · q)Each of the q queries may scan the whole string.O(1)Only pointers and a counter besides the output.For each query, move a pointer from left to the first candle and another from right back to the last candle. If they cross or meet, the answer is 0; otherwise count the plates between them.
- For a query [l, r], advance l while s[l] is a plate, and move r left while s[r] is a plate.
- If l >= r, the answer is 0.
- Otherwise count the '*' characters between l and r.
class Solution {
public int[] platesBetweenCandles(String s, int[][] queries) {
int[] answer = new int[queries.length];
for (int k = 0; k < queries.length; k++) {
int l = queries[k][0], r = queries[k][1];
while (l <= r && s.charAt(l) == '*') l++;
while (r >= l && s.charAt(r) == '*') r--;
int count = 0;
for (int i = l; i < r; i++) {
if (s.charAt(i) == '*') count++;
}
answer[k] = count;
}
return answer;
}
}class Solution:
def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
answer = []
for l, r in queries:
while l <= r and s[l] == '*':
l += 1
while r >= l and s[r] == '*':
r -= 1
count = 0
for i in range(l, r):
if s[i] == '*':
count += 1
answer.append(count)
return answerclass Solution {
public:
vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
vector<int> answer(queries.size());
for (int k = 0; k < (int)queries.size(); k++) {
int l = queries[k][0], r = queries[k][1];
while (l <= r && s[l] == '*') l++;
while (r >= l && s[r] == '*') r--;
int count = 0;
for (int i = l; i < r; i++) {
if (s[i] == '*') count++;
}
answer[k] = count;
}
return answer;
}
};function platesBetweenCandles(s, queries) {
const answer = new Array(queries.length);
for (let k = 0; k < queries.length; k++) {
let l = queries[k][0], r = queries[k][1];
while (l <= r && s[l] === '*') l++;
while (r >= l && s[r] === '*') r--;
let count = 0;
for (let i = l; i < r; i++) {
if (s[i] === '*') count++;
}
answer[k] = count;
}
return answer;
}2Optimal (prefix sums + nearest candles)
O(n + q)Three linear passes over s, then O(1) per query.O(n)Three arrays of length about n.Precompute three arrays: prefix[i] = plates in s[0..i-1], nextCandle[i] = the first candle at index >= i, and prevCandle[i] = the last candle at index <= i. For a query, the outer candles are a = nextCandle[left] and b = prevCandle[right]; if both exist and a < b, the answer is prefix[b] - prefix[a].
- Build prefix with prefix[i + 1] = prefix[i] + (s[i] == '*' ? 1 : 0).
- Fill prevCandle left to right and nextCandle right to left, using -1 when there is no candle.
- For each query, look up a and b; if a != -1, b != -1 and a < b, answer prefix[b] - prefix[a], else 0.
class Solution {
public int[] platesBetweenCandles(String s, int[][] queries) {
int n = s.length();
int[] prefix = new int[n + 1];
int[] prevCandle = new int[n];
int[] nextCandle = new int[n];
int last = -1;
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + (s.charAt(i) == '*' ? 1 : 0);
if (s.charAt(i) == '|') last = i;
prevCandle[i] = last;
}
last = -1;
for (int i = n - 1; i >= 0; i--) {
if (s.charAt(i) == '|') last = i;
nextCandle[i] = last;
}
int[] answer = new int[queries.length];
for (int k = 0; k < queries.length; k++) {
int a = nextCandle[queries[k][0]];
int b = prevCandle[queries[k][1]];
if (a != -1 && b != -1 && a < b) answer[k] = prefix[b] - prefix[a];
}
return answer;
}
}class Solution:
def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
n = len(s)
prefix = [0] * (n + 1)
prev_candle = [-1] * n
next_candle = [-1] * n
last = -1
for i, ch in enumerate(s):
prefix[i + 1] = prefix[i] + (1 if ch == '*' else 0)
if ch == '|':
last = i
prev_candle[i] = last
last = -1
for i in range(n - 1, -1, -1):
if s[i] == '|':
last = i
next_candle[i] = last
answer = []
for l, r in queries:
a, b = next_candle[l], prev_candle[r]
if a != -1 and b != -1 and a < b:
answer.append(prefix[b] - prefix[a])
else:
answer.append(0)
return answerclass Solution {
public:
vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
int n = s.size();
vector<int> prefix(n + 1, 0), prevCandle(n), nextCandle(n);
int last = -1;
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + (s[i] == '*' ? 1 : 0);
if (s[i] == '|') last = i;
prevCandle[i] = last;
}
last = -1;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == '|') last = i;
nextCandle[i] = last;
}
vector<int> answer(queries.size(), 0);
for (int k = 0; k < (int)queries.size(); k++) {
int a = nextCandle[queries[k][0]];
int b = prevCandle[queries[k][1]];
if (a != -1 && b != -1 && a < b) answer[k] = prefix[b] - prefix[a];
}
return answer;
}
};function platesBetweenCandles(s, queries) {
const n = s.length;
const prefix = new Array(n + 1).fill(0);
const prevCandle = new Array(n);
const nextCandle = new Array(n);
let last = -1;
for (let i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + (s[i] === '*' ? 1 : 0);
if (s[i] === '|') last = i;
prevCandle[i] = last;
}
last = -1;
for (let i = n - 1; i >= 0; i--) {
if (s[i] === '|') last = i;
nextCandle[i] = last;
}
const answer = new Array(queries.length).fill(0);
for (let k = 0; k < queries.length; k++) {
const a = nextCandle[queries[k][0]];
const b = prevCandle[queries[k][1]];
if (a !== -1 && b !== -1 && a < b) answer[k] = prefix[b] - prefix[a];
}
return answer;
}Edge cases to test
- A range with no candle or a single candle: the answer is 0
- Plates at the ends of the range that are outside the outer candles must not be counted
- A string with no plates at all
- A range of length 1
Hints
Hint 1
Only plates between the leftmost and rightmost candle inside the range count. Find those two candles first.
Hint 2
Precompute, for every index, the nearest candle at or to its right and at or to its left.
Hint 3
With a prefix count of plates, the plates between two candle positions a <= b is prefix[b] - prefix[a].
FAQ
What is the best time complexity for Plates Between Candles?
Optimal (prefix sums + nearest candles) runs in O(n + q) time and O(n) extra space. Three linear passes over s, then O(1) per query.
Which pattern does Plates Between Candles use?
It is a arrays & hashing problem that uses the prefix sum strategy pattern. Other problems with the same pattern: Subarray Sum Equals K, Subarray with given XOR, Range Sum Query - Immutable.
Is there a brute force solution for Plates Between Candles?
Yes. Brute force (scan each query) takes O(n · q) time and O(1) space. For each query, move a pointer from left to the first candle and another from right back to the last candle.
Which edge cases should I test for Plates Between Candles?
A range with no candle or a single candle: the answer is 0; Plates at the ends of the range that are outside the outer candles must not be counted; A string with no plates at all; A range of length 1.