Plates Between Candles
- 2 min read
- Array
- LC-Medium
3 years ago
Solution
- Took me one hour but what the heck I did it
- Very easy to do this brute force
- To prevent recalculations, you need to precalculate 3 things, which tell you information about a specific index:
leftcontaining the index of the closest candle to the left, or the current index if it's a candlerightcontaining the index of the closest candle to the right, or the current index if it's a candlenum_candles_to_rightcontaining the number of candles to the right, not including the current index
- With the above 3 pieces of information, we can go through the queries and for each query and:
- Update the
startindex to the index of the candle closest to the right ofstart - Update the
endindex to the index of the candle closest to the left ofend- We are shortening the substring so that the bounds of it are both candles
- With the new
startandendindex, all we now need to know is how many candles are inside, so that we can get the number of plates - To get the number of plates in the current range, we can use the precalculated prefix sums.
- Update the
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
n = len(s)
left = [-1] * n # index of closest candle to the left
right = [-1] * n # index of closest candle to the right
num_candles_to_right = [0] * n
num_candles, closest_candle_index = 0, -1
for i in range(n):
if s[i] == '|':
num_candles += 1
closest_candle_index = i
left[i] = closest_candle_index
num_candles, closest_candle_index = 0, -1
for i in range(n - 1, -1, -1):
num_candles_to_right[i] = num_candles
if s[i] == '|':
num_candles += 1
closest_candle_index = i
right[i] = closest_candle_index
ans = []
for start, end in queries:
if start == end:
ans.append(0)
continue
new_start = right[start]
new_end = left[end]
num_candles_in_window = num_candles_to_right[new_start] - num_candles_to_right[new_end]
num_candles = (new_end - new_start) - num_candles_in_window
ans.append(max(0, num_candles))
return ans