Plates Between Candles — Solution in Python, Java & C++
Plates Between Candles solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Plates Between Candles is a medium coding problem on arrays, strings and binary search, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Binary Search, Prefix Sum
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A long table is described by the string s: '*' is a plate and '|' is a candle. Positions are 0-indexed.
Each query queries[i] = [left, right] looks only at the section s[left..right] (inclusive). Within that section, a plate counts if there is at least one candle to its left and at least one candle to its right inside the same section.
Return an array whose i-th element is the number of counted plates for the i-th query.
Example 1
Input: s = "*|*|**|*", queries = [[0,7],[1,3],[2,5],[0,1]]
Output: [3,1,0,0]
Explanation: For `[0,7]` the outermost candles are at 1 and 6, enclosing the plates at 2, 4 and 5. The section `[2,5]` holds a single candle, so nothing is enclosed.
Example 2
Input: s = "||**||", queries = [[0,5],[2,3]]
Output: [2,0]
Constraints
3 <= s.length <= 10^5s consists of '*' and '|' characters1 <= queries.length <= 10^5queries[i].length == 20 <= left <= right < s.length
Hints for Plates Between Candles
Hint 1
Inside a section, only the leftmost and the rightmost candle matter: every plate between them is enclosed.
Hint 2
Precompute, for every index, the nearest candle at or to its right and the nearest candle at or to its left.
Hint 3
With a prefix count of plates, the answer for
[l, r]is the number of plates betweennextCandle[l]andprevCandle[r]— or 0 when those candles do not form a valid pair.
How to solve Plates Between Candles
A query's answer is the number of plates between the first candle at or after left and the last candle at or before right. Three precomputed arrays make each query O(1).
Approach
- Build
pre, wherepre[i]is the number of plates ins[0..i-1]. - Build
prevCandle[i], the index of the last candle at or beforei(or -1), with a left-to-right sweep. - Build
nextCandle[i], the index of the first candle at or afteri(or -1), with a right-to-left sweep. - For a query
[l, r], leta = nextCandle[l]andb = prevCandle[r]. If both exist anda < b, the answer ispre[b] - pre[a]; otherwise it is 0.
Why it works
A plate inside the section is enclosed exactly when it lies strictly between the section's leftmost candle a and rightmost candle b. nextCandle[l] is the leftmost candle of the section if it is not beyond r, and prevCandle[r] the rightmost if it is not before l; when a < b both are inside the section. The prefix difference counts plates in [a, b), and since s[a] is a candle that is exactly the plates strictly between them.
Complexity
- Time —
O(n + q) - Space —
O(n)
Pitfalls
- A section with zero or one candle encloses nothing — check
a < b, not just that both exist. - Use the candles inside the section, not the nearest candles outside it.
- Scanning each query directly is O(n·q) and too slow at the full limits.
Reference solution
Python
from typing import List
def platesBetweenCandles(s: str, queries: List[List[int]]) -> List[int]:
n = len(s)
pre = [0] * (n + 1)
for i, ch in enumerate(s):
pre[i + 1] = pre[i] + (1 if ch == "*" else 0)
prev_c = [-1] * n
last = -1
for i in range(n):
if s[i] == "|":
last = i
prev_c[i] = last
next_c = [-1] * n
last = -1
for i in range(n - 1, -1, -1):
if s[i] == "|":
last = i
next_c[i] = last
out = []
for l, r in queries:
a, b = next_c[l], prev_c[r]
out.append(pre[b] - pre[a] if a != -1 and b != -1 and a < b else 0)
return outJava
public static int[] platesBetweenCandles(String s, int[][] queries) {
int n = s.length();
int[] pre = new int[n + 1], prevC = new int[n], nextC = new int[n];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + (s.charAt(i) == '*' ? 1 : 0);
int last = -1;
for (int i = 0; i < n; i++) { if (s.charAt(i) == '|') last = i; prevC[i] = last; }
last = -1;
for (int i = n - 1; i >= 0; i--) { if (s.charAt(i) == '|') last = i; nextC[i] = last; }
int[] out = new int[queries.length];
for (int q = 0; q < queries.length; q++) {
int a = nextC[queries[q][0]], b = prevC[queries[q][1]];
out[q] = (a != -1 && b != -1 && a < b) ? pre[b] - pre[a] : 0;
}
return out;
}C++
vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
int n = s.size();
vector<int> pre(n + 1, 0), prevC(n, -1), nextC(n, -1);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + (s[i] == '*' ? 1 : 0);
int last = -1;
for (int i = 0; i < n; i++) { if (s[i] == '|') last = i; prevC[i] = last; }
last = -1;
for (int i = n - 1; i >= 0; i--) { if (s[i] == '|') last = i; nextC[i] = last; }
vector<int> out;
for (auto& q : queries) {
int a = nextC[q[0]], b = prevC[q[1]];
out.push_back((a != -1 && b != -1 && a < b) ? pre[b] - pre[a] : 0);
}
return out;
}JavaScript
var platesBetweenCandles = function(s, queries) {
var n = s.length;
var pre = new Array(n + 1).fill(0);
for (var i = 0; i < n; i++) pre[i + 1] = pre[i] + (s[i] === "*" ? 1 : 0);
var prevC = new Array(n), nextC = new Array(n), last = -1;
for (var i2 = 0; i2 < n; i2++) { if (s[i2] === "|") last = i2; prevC[i2] = last; }
last = -1;
for (var i3 = n - 1; i3 >= 0; i3--) { if (s[i3] === "|") last = i3; nextC[i3] = last; }
return queries.map(function (q) {
var a = nextC[q[0]], b = prevC[q[1]];
return a !== -1 && b !== -1 && a < b ? pre[b] - pre[a] : 0;
});
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.