Plates Between Candles
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
The most efficient approach involves pre-calculating all the necessary information to answer each query in constant time. We can precompute not only the prefix sums of plates but also the positions of the nearest candles for every index in the string.
Algorithm
- First, perform a full precomputation step in O(N) time:
- Create a prefix sum array
prefixPlatesof sizen.prefixPlates[i]stores the count of'*'ins[0...i]. - Create an array
prevCandleof sizen.prevCandle[i]stores the index of the closest candle to the left of or at indexi. This is computed in a single pass from left to right. - Create an array
nextCandleof sizen.nextCandle[i]stores the index of the closest candle to the right of or at indexi. This is computed in a single pass from right to left.
- Create a prefix sum array
- Initialize an
answerarray. - For each query
[left, right]:- Find the effective left boundary candle index:
startCandle = nextCandle[left]. - Find the effective right boundary candle index:
endCandle = prevCandle[right]. - Check if these boundaries are valid and if
startCandle < endCandle. - If they are, the number of plates is
prefixPlates[endCandle] - prefixPlates[startCandle]. This is an O(1) operation. - If the boundaries are not valid, the answer is 0.
- Find the effective left boundary candle index:
- Return the
answerarray.
Walkthrough
This approach achieves the optimal time complexity by performing a thorough precomputation. The key idea is to answer every query in constant time by having all the required information readily available in lookup tables (arrays).
We create three auxiliary arrays:
prefixPlates: As in the previous approach,prefixPlates[i]stores the cumulative number of plates up to indexi.nextCandle: For each indexi,nextCandle[i]stores the index of the first candle encountered when moving fromito the right. This can be computed with a single pass from right to left.prevCandle: For each indexi,prevCandle[i]stores the index of the first candle encountered when moving fromito the left. This is computed with a pass from left to right.
After this O(N) precomputation, each query [left, right] can be resolved instantly. The true left boundary is nextCandle[left], and the true right boundary is prevCandle[right]. If these boundaries are valid, the plate count is a simple lookup and subtraction using the prefixPlates array.
class Solution { public int[] platesBetweenCandles(String s, int[][] queries) { int n = s.length(); int[] prefixPlates = new int[n]; int count = 0; for (int i = 0; i < n; i++) { if (s.charAt(i) == '*') { count++; } prefixPlates[i] = count; } int[] prevCandle = new int[n]; int lastCandle = -1; for (int i = 0; i < n; i++) { if (s.charAt(i) == '|') { lastCandle = i; } prevCandle[i] = lastCandle; } int[] nextCandle = new int[n]; int firstCandle = -1; for (int i = n - 1; i >= 0; i--) { if (s.charAt(i) == '|') { firstCandle = i; } nextCandle[i] = firstCandle; } int[] ans = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int left = queries[i][0]; int right = queries[i][1]; int startCandle = nextCandle[left]; int endCandle = prevCandle[right]; if (startCandle != -1 && endCandle != -1 && startCandle < endCandle) { ans[i] = prefixPlates[endCandle] - prefixPlates[startCandle]; } else { ans[i] = 0; } } return ans; }}Complexity
Time
O(N + Q). The precomputation takes three passes over the string, which is O(N). Each of the Q queries is then answered in O(1) time.
Space
O(N), where N is the string length. We use three arrays of size N for precomputation.
Trade-offs
Pros
Extremely fast, with constant time per query.
This is the most optimal solution in terms of time complexity.
Cons
Requires more space than other approaches due to the three helper arrays.
Solutions
Solution
class Solution {public int[] platesBetweenCandles(String s, int[][] queries) { int n = s.length(); int[] presum = new int[n + 1]; for (int i = 0; i < n; ++i) { presum[i + 1] = presum[i] + (s.charAt(i) == '*' ? 1 : 0); } int[] left = new int[n]; int[] right = new int[n]; for (int i = 0, l = -1; i < n; ++i) { if (s.charAt(i) == '|') { l = i; } left[i] = l; } for (int i = n - 1, r = -1; i >= 0; --i) { if (s.charAt(i) == '|') { r = i; } right[i] = r; } int[] ans = new int[queries.length]; for (int k = 0; k < queries.length; ++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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.