Plates Between Candles — LeetCode 2055 Python Solution
MediumArrayStringBinary SearchPrefix Sum
- Problem
- #2055
- Pattern
- Prefix Sum
- Reading time
- 4 min
- Source
- leetcode.com
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.
Example
- Input
- s = "**|**|***|", queries = [[2,5],[5,9]]
- Output
- [2,3]
- Explanation
- - queries[0] has two plates between candles.
Python solution
Python
class Solution:
def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
n = len(s)
presum = [0] * (n + 1)
for i, c in enumerate(s):
presum[i + 1] = presum[i] + (c == '*')
left, right = [0] * n, [0] * n
l = r = -1
for i, c in enumerate(s):
if c == '|':
l = i
left[i] = l
for i in range(n - 1, -1, -1):
if s[i] == '|':
r = i
right[i] = r
ans = [0] * len(queries)
for k, (l, r) in enumerate(queries):
i, j = right[l], left[r]
if i >= 0 and j >= 0 and i < j:
ans[k] = presum[j] - presum[i + 1]
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(log n) or O(n log n) |
| Space | O(1) auxiliary |
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 2055. Plates Between Candles is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2055. Plates Between Candles?
- LeetCode 2055. Plates Between Candles is rated Medium on LeetCode.
- What topics does LeetCode 2055. Plates Between Candles cover?
- LeetCode 2055. Plates Between Candles is tagged Array, String, Binary Search and Prefix Sum on LeetCode.