LeetCode 2055 - Plates Between Candles

LeetCode Problem 2055

Difficulty: 🟡 Medium
Topics: Array, String, Binary Search, Prefix Sum

Solution

Problem Understanding

The problem gives us a string s made of two characters:

• '*' represents a plate
• '|' represents a candle

We are also given multiple queries, where each query specifies a substring of s using indices [left, right].

For every query, we must count how many plates are located between two candles inside that substring.

The important detail is that a plate only counts if there is:

• at least one candle to its left within the substring
• at least one candle to its right within the substring

This means plates outside the outermost candles in the queried range do not count.

For example, consider:

s = "**|**|***|"

For query [2, 9], the substring is:

|**|***|

The plates counted are all plates located between the first and last candle in that substring.

The constraints are very important:

• s.length can be up to 100000
• queries.length can also be up to 100000

A naive solution that scans every query character by character would be far too slow. In the worst case, that would require:

100000 * 100000 = 10^10

operations, which is not feasible.

The problem therefore strongly suggests preprocessing the string so that each query can be answered efficiently.

Several edge cases are important:

• A query may contain no candles at all
• A query may contain only one candle
• Candles may exist, but no plates lie between them
• Plates before the first candle or after the last candle should not be counted
• The substring boundaries may already start or end on candles

A correct solution must handle all of these situations carefully.

Approaches

Brute Force Approach

The most direct approach is to process every query independently.

For each query:

1. Extract the substring s[left:right+1]
2. Find the first candle in the substring
3. Find the last candle in the substring
4. Count plates between those two candles

This approach is correct because it directly follows the problem definition.

However, the runtime is too expensive. In the worst case, each query scans the entire string, producing:

• O(n) work per query
• O(n * q) total runtime

With both n and q up to 100000, this becomes far too slow.

Optimal Approach

The key observation is that queries are independent, but the string never changes.

That means we can preprocess useful information once and reuse it for all queries.

We use three preprocessing arrays:

1. prefix_plates

• prefix_plates[i] stores how many plates appear before index i
• This allows fast range counting

2. nearest_left_candle

• For every index, stores the closest candle at or to the left

3. nearest_right_candle

• For every index, stores the closest candle at or to the right

For each query:

• Find the first valid candle inside the range
• Find the last valid candle inside the range
• Use prefix sums to count plates between them

Each query can then be answered in constant time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × q)	O(1)	Scans every substring independently
Optimal	O(n + q)	O(n)	Uses prefix sums and nearest candle preprocessing

Algorithm Walkthrough

1. Build a prefix sum array for plates.

We create an array prefix_plates where:

prefix_plates[i + 1]

stores the number of '*' characters in s[0:i].

This allows us to count plates in any range instantly using subtraction. 2. Build the nearest left candle array.

Traverse from left to right.

Keep track of the most recent candle position.

For every index:

• if the character is a candle, update the latest candle position
• store that position in nearest_left_candle[i]

3. Build the nearest right candle array.

Traverse from right to left.

Keep track of the closest candle seen so far.

For every index:

• if the character is a candle, update the latest candle position
• store that position in nearest_right_candle[i]

4. Process each query.

For query [left, right]:

• Find the first candle inside the range:

start = nearest_right_candle[left]

• Find the last candle inside the range:

end = nearest_left_candle[right]

5. Validate the candle positions.

If:

• either candle does not exist
• or start >= end

then no valid enclosed plates exist, so the answer is 0. 6. Count plates between the candles.

Using prefix sums:

plates = prefix_plates[end] - prefix_plates[start]

This counts all plates strictly between the two candle positions.

Why it works

The algorithm works because every valid plate must lie between two candles.

For a query, the left boundary candle must be the first candle inside the range, and the right boundary candle must be the last candle inside the range.

Any plates outside those two candles cannot satisfy the problem condition.

The prefix sum array correctly counts plates between any two indices in constant time, and the nearest candle arrays guarantee we quickly locate the valid candle boundaries for every query.

Python Solution

from typing import List

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)

        # Prefix sum of plates
        prefix_plates = [0] * (n + 1)

        for i in range(n):
            prefix_plates[i + 1] = prefix_plates[i]
            if s[i] == '*':
                prefix_plates[i + 1] += 1

        # Nearest candle on the left
        nearest_left_candle = [-1] * n
        last_candle = -1

        for i in range(n):
            if s[i] == '|':
                last_candle = i
            nearest_left_candle[i] = last_candle

        # Nearest candle on the right
        nearest_right_candle = [-1] * n
        last_candle = -1

        for i in range(n - 1, -1, -1):
            if s[i] == '|':
                last_candle = i
            nearest_right_candle[i] = last_candle

        # Answer queries
        result = []

        for left, right in queries:
            start = nearest_right_candle[left]
            end = nearest_left_candle[right]

            if start == -1 or end == -1 or start >= end:
                result.append(0)
            else:
                plates = prefix_plates[end] - prefix_plates[start]
                result.append(plates)

        return result

The implementation follows the preprocessing strategy directly.

The first loop constructs the prefix sum array. Each entry stores the cumulative number of plates encountered so far.

The second loop computes the nearest candle to the left for every position. This allows queries to quickly locate the rightmost valid candle within the left boundary.

The third loop computes the nearest candle to the right for every position. This allows queries to quickly locate the leftmost valid candle within the right boundary.

Finally, each query is processed in constant time. The algorithm finds the candle boundaries and uses prefix sums to compute the number of enclosed plates.

Go Solution

func platesBetweenCandles(s string, queries [][]int) []int {
	n := len(s)

	// Prefix sum of plates
	prefixPlates := make([]int, n+1)

	for i := 0; i < n; i++ {
		prefixPlates[i+1] = prefixPlates[i]
		if s[i] == '*' {
			prefixPlates[i+1]++
		}
	}

	// Nearest candle on the left
	nearestLeft := make([]int, n)
	lastCandle := -1

	for i := 0; i < n; i++ {
		if s[i] == '|' {
			lastCandle = i
		}
		nearestLeft[i] = lastCandle
	}

	// Nearest candle on the right
	nearestRight := make([]int, n)
	lastCandle = -1

	for i := n - 1; i >= 0; i-- {
		if s[i] == '|' {
			lastCandle = i
		}
		nearestRight[i] = lastCandle
	}

	// Process queries
	result := make([]int, 0, len(queries))

	for _, query := range queries {
		left := query[0]
		right := query[1]

		start := nearestRight[left]
		end := nearestLeft[right]

		if start == -1 || end == -1 || start >= end {
			result = append(result, 0)
		} else {
			plates := prefixPlates[end] - prefixPlates[start]
			result = append(result, plates)
		}
	}

	return result
}

The Go implementation mirrors the Python solution closely.

Slices are used for all preprocessing arrays. Since the constraints guarantee values fit comfortably within standard integer ranges, regular int values are sufficient.

Unlike Python lists, Go slices require explicit allocation using make. Otherwise, the overall logic is identical.

Worked Examples

Example 1

s = "**|**|***|"
queries = [[2,5],[5,9]]

Step 1: Build Prefix Sum

Index	Character	Prefix Plates
0	*	1
1	*	2
2	|	2
3	*	3
4	*	4
5	|	4
6	*	5
7	*	6
8	*	7
9	|	7

Final prefix array:

[0,1,2,2,3,4,4,5,6,7,7]

Step 2: Nearest Left Candle

Index	Value
0	-1
1	-1
2	2
3	2
4	2
5	5
6	5
7	5
8	5
9	9

Step 3: Nearest Right Candle

Index	Value
0	2
1	2
2	2
3	5
4	5
5	5
6	9
7	9
8	9
9	9

Query [2,5]

start = nearest_right[2] = 2
end = nearest_left[5] = 5

Plate count:

prefix[5] - prefix[2]
= 4 - 2
= 2

Answer: 2

Query [5,9]

start = nearest_right[5] = 5
end = nearest_left[9] = 9

Plate count:

prefix[9] - prefix[5]
= 7 - 4
= 3

Answer: 3

Final output:

[2,3]

Example 2

s = "***|**|*****|**||**|*"
queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]

Query [1,17]

Substring:

**|**|*****|**||

First candle inside range is at index 3.

Last candle inside range is at index 16.

Using prefix sums:

plates = prefix[16] - prefix[3]
= 14 - 5
= 9

Answer: 9

Query [4,5]

Only one candle exists in the range.

No enclosed plates exist.

Answer: 0

Query [14,17]

Candles are adjacent.

No plates exist between them.

Answer: 0

Query [5,11]

Only one candle boundary exists.

Answer: 0

Query [15,16]

Two adjacent candles.

Answer: 0

Final output:

[9,0,0,0,0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + q)	Preprocessing takes O(n), each query takes O(1)
Space	O(n)	Three auxiliary arrays of size n are stored

The preprocessing phase scans the string three times, which is linear in the size of the string.

Each query only performs constant-time lookups and arithmetic operations, so processing all queries takes linear time in the number of queries.

The auxiliary arrays dominate the memory usage, producing linear space complexity.

Test Cases

from typing import List

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        n = len(s)

        prefix_plates = [0] * (n + 1)

        for i in range(n):
            prefix_plates[i + 1] = prefix_plates[i]
            if s[i] == '*':
                prefix_plates[i + 1] += 1

        nearest_left = [-1] * n
        last = -1

        for i in range(n):
            if s[i] == '|':
                last = i
            nearest_left[i] = last

        nearest_right = [-1] * n
        last = -1

        for i in range(n - 1, -1, -1):
            if s[i] == '|':
                last = i
            nearest_right[i] = last

        result = []

        for left, right in queries:
            start = nearest_right[left]
            end = nearest_left[right]

            if start == -1 or end == -1 or start >= end:
                result.append(0)
            else:
                result.append(prefix_plates[end] - prefix_plates[start])

        return result

sol = Solution()

# Provided example 1
assert sol.platesBetweenCandles(
    "**|**|***|",
    [[2, 5], [5, 9]]
) == [2, 3]

# Provided example 2
assert sol.platesBetweenCandles(
    "***|**|*****|**||**|*",
    [[1, 17], [4, 5], [14, 17], [5, 11], [15, 16]]
) == [9, 0, 0, 0, 0]

# No candles at all
assert sol.platesBetweenCandles(
    "******",
    [[0, 5]]
) == [0]

# Only candles
assert sol.platesBetweenCandles(
    "|||||",
    [[0, 4]]
) == [0]

# Plates outside candle boundaries should not count
assert sol.platesBetweenCandles(
    "**|**|**",
    [[0, 7]]
) == [2]

# Single candle only
assert sol.platesBetweenCandles(
    "***|***",
    [[0, 6]]
) == [0]

# Adjacent candles
assert sol.platesBetweenCandles(
    "|**||**|",
    [[0, 7]]
) == [4]

# Query containing exact candle boundaries
assert sol.platesBetweenCandles(
    "|***|",
    [[0, 4]]
) == [3]

# Minimal valid input
assert sol.platesBetweenCandles(
    "|*|",
    [[0, 2]]
) == [1]

# Query with no valid enclosing candles
assert sol.platesBetweenCandles(
    "*|***",
    [[0, 4]]
) == [0]

Test	Why
Example 1	Validates standard functionality
Example 2	Validates multiple edge scenarios
No candles	Ensures zero is returned correctly
Only candles	Ensures no plates are counted
Plates outside boundaries	Confirms only enclosed plates count
Single candle	Ensures two candles are required
Adjacent candles	Confirms zero-distance candle handling
Exact candle boundaries	Verifies inclusive query behavior
Minimal valid input	Tests smallest meaningful case
No enclosing candles	Ensures invalid ranges return zero

Edge Cases

Queries With No Candles

A substring may contain only plates and no candles at all.

For example:

s = "*****"
query = [0, 4]

Since there are no candle boundaries, no plate can possibly be enclosed between candles.

This case is handled because the nearest candle arrays return -1, and the implementation immediately returns 0.

Queries With Only One Candle

A substring may contain exactly one candle.

For example:

s = "***|***"
query = [0, 6]

Even though a candle exists, plates still cannot be enclosed because two candle boundaries are required.

The implementation detects this because the computed start and end positions either match or produce start >= end.

Plates Outside the Outer Candles

One of the easiest mistakes is accidentally counting plates that lie outside the valid candle boundaries.

For example:

s = "**|**|**"
query = [0, 7]

Only the two plates between the candles should count. The plates before the first candle and after the last candle must be ignored.

The implementation handles this correctly by first locating the inner candle boundaries and then counting only the plates strictly between those positions using prefix sums.