# Plates Between Candles
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/plates-between-candles)
Canonical: https://scaleengineer.com/dsa/problems/plates-between-candles
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, String
---
## 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**.

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 is `2`, 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:**

![ex-1](https://assets.glich.co/dsa/plates-between-candles/image0.png) 

**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:**

![ex-2](https://assets.glich.co/dsa/plates-between-candles/image1.png) 

**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 <= 105`
* `s` consists of `'*'` and `'|'` characters.
* `1 <= queries.length <= 105`
* `queries[i].length == 2`
* `0 <= lefti <= righti < s.length`

# Approaches
## Brute Force Iteration
This is the most straightforward approach. For each query, we iterate through the given substring to find the boundaries (the first and last candles) and then count the plates between them.
**Time:** O(Q * N), where Q is the number of queries and N is the length of the string `s`. For each query, we might scan the substring, which can have a length of up to N. · **Space:** O(Q) or O(1), where Q is the number of queries. The space is dominated by the output array. Excluding the output, the space complexity is O(1).
**Pros:** Simple to understand and implement.; Requires minimal extra space.
**Cons:** Highly inefficient due to repeated scanning of the string.; Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
For every query `[left, right]`, we first need to identify the actual range of plates that are enclosed by candles within the substring `s[left...right]`. This involves a linear scan from `left` to `right` to find the index of the first candle, `firstCandle`, and another scan (or a continuation of the first) to find the index of the last candle, `lastCandle`. If we find at least two candles such that `firstCandle < lastCandle`, we then perform another iteration, this time from `firstCandle` to `lastCandle`, to count all the `'*'` characters. This count is the answer for the current query. If fewer than two candles are found in the range, the answer is 0. This process is repeated for every single query.

```java
class Solution {
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int q = queries.length;
        int[] ans = new int[q];
        for (int i = 0; i < q; i++) {
            int left = queries[i][0];
            int right = queries[i][1];
            
            int firstCandle = -1;
            for (int j = left; j <= right; j++) {
                if (s.charAt(j) == '|') {
                    firstCandle = j;
                    break;
                }
            }
            
            if (firstCandle == -1) {
                ans[i] = 0;
                continue;
            }
            
            int lastCandle = -1;
            // We can optimize this by just continuing the scan, but for clarity a separate loop is shown.
            for (int j = right; j >= firstCandle; j--) {
                if (s.charAt(j) == '|') {
                    lastCandle = j;
                    break;
                }
            }
            
            if (lastCandle == -1 || firstCandle >= lastCandle) {
                ans[i] = 0;
                continue;
            }
            
            int count = 0;
            for (int j = firstCandle + 1; j < lastCandle; j++) {
                if (s.charAt(j) == '*') {
                    count++;
                }
            }
            ans[i] = count;
        }
        return ans;
    }
}
```
### Algorithm
*   Initialize an integer array `answer` with the same size as `queries`.
*   Iterate through each query `[left, right]` in the `queries` array.
*   For each query, find the index of the first candle within the range `[left, right]`. Let's call it `firstCandle`. If no candle is found, the answer for this query is 0.
*   Similarly, find the index of the last candle within the range `[left, right]`. Let's call it `lastCandle`.
*   If `firstCandle` is not found or `firstCandle` is at or after `lastCandle`, the number of plates between candles is 0.
*   Otherwise, iterate from `firstCandle + 1` to `lastCandle - 1`.
*   Count the number of plate characters `'*'` in this inner range.
*   Store the count in the `answer` array for the current query.
*   After processing all queries, return the `answer` array.

## Precomputation with Binary Search
To optimize the brute-force approach, we can precompute the locations of all candles. For each query, we can then use binary search to quickly find the relevant candles that bound the plates, and a prefix sum array to count the plates between them in constant time.
**Time:** O(N + Q * log C), where N is the string length, Q is the number of queries, and C is the number of candles. Precomputation takes O(N). Each query involves two binary searches on the list of candle indices, taking O(log C) time. · **Space:** O(N), where N is the string length. We need O(C) space for `candleIndices` (where C is the number of candles, C <= N) and O(N) for `prefixPlates`.
**Pros:** Significantly faster than the brute-force approach for a large number of queries.; Efficiently handles sparse or dense distributions of candles.
**Cons:** The logarithmic time complexity per query makes it slightly slower than the optimal linear time solution.; Implementation of binary search to find the correct boundaries requires careful handling of edge cases.
### Explanation
This approach improves upon the brute force method by avoiding repeated scans of the string. We start by pre-processing the input string `s` in two ways. First, we create a list containing the indices of all candles. This allows us to focus only on the candle positions. Second, we create a prefix sum array that stores, for each index `i`, the cumulative count of plates up to that index. 

With these precomputed structures, we can process each query `[left, right]` much faster. We use binary search on our list of candle indices to find the effective boundaries for our plate count. Specifically, we find the first candle that is not before `left` and the last candle that is not after `right`. Once we have the indices of these two boundary candles, we can use our prefix sum array to find the number of plates between them in a single subtraction operation. This reduces the work per query from linear to logarithmic time.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length();
        List<Integer> candleIndices = new ArrayList<>();
        int[] prefixPlates = new int[n];
        int plateCount = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '*') {
                plateCount++;
            } else {
                candleIndices.add(i);
            }
            prefixPlates[i] = plateCount;
        }

        int[] ans = new int[queries.length];
        if (candleIndices.isEmpty()) {
            return ans; // All zeros if no candles
        }

        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];

            // Find first candle index >= left (lower_bound)
            int startIdx = Collections.binarySearch(candleIndices, left);
            if (startIdx < 0) {
                startIdx = -(startIdx + 1);
            }

            // Find last candle index <= right (upper_bound - 1)
            int endIdx = Collections.binarySearch(candleIndices, right);
            if (endIdx < 0) {
                endIdx = -(endIdx + 1) - 1;
            }

            if (startIdx < candleIndices.size() && endIdx >= 0 && startIdx < endIdx) {
                int leftCandlePos = candleIndices.get(startIdx);
                int rightCandlePos = candleIndices.get(endIdx);
                ans[i] = prefixPlates[rightCandlePos] - prefixPlates[leftCandlePos];
            }
        }
        return ans;
    }
}
```
### Algorithm
*   First, perform a precomputation step:
    *   Create a list, `candleIndices`, and populate it with the indices of all `'|'` characters in `s`.
    *   Create a prefix sum array, `prefixPlates`, of size `n` (where `n` is the length of `s`). `prefixPlates[i]` will store the count of `'*'` in the substring `s[0...i]`.
*   Initialize an `answer` array.
*   For each query `[left, right]`:
    *   Use binary search on `candleIndices` to find the index of the first candle at or after `left`. This is the `lower_bound` of `left`.
    *   Use binary search on `candleIndices` to find the index of the last candle at or before `right`. This can be found by searching for the `upper_bound` of `right` and taking the previous index.
    *   If valid left and right boundary candles are found and the left candle comes before the right one:
        *   Retrieve their actual string indices, `leftCandlePos` and `rightCandlePos`.
        *   The number of plates is calculated in O(1) using the prefix sum array: `prefixPlates[rightCandlePos] - prefixPlates[leftCandlePos]`.
    *   Otherwise, the answer is 0.
*   Return the `answer` array.

## Full Precomputation with Helper Arrays
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.
**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.
**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.
### Explanation
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:
1.  `prefixPlates`: As in the previous approach, `prefixPlates[i]` stores the cumulative number of plates up to index `i`.
2.  `nextCandle`: For each index `i`, `nextCandle[i]` stores the index of the first candle encountered when moving from `i` to the right. This can be computed with a single pass from right to left.
3.  `prevCandle`: For each index `i`, `prevCandle[i]` stores the index of the first candle encountered when moving from `i` to 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.

```java
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;
    }
}
```
### Algorithm
*   First, perform a full precomputation step in O(N) time:
    1.  Create a prefix sum array `prefixPlates` of size `n`. `prefixPlates[i]` stores the count of `'*'` in `s[0...i]`.
    2.  Create an array `prevCandle` of size `n`. `prevCandle[i]` stores the index of the closest candle to the left of or at index `i`. This is computed in a single pass from left to right.
    3.  Create an array `nextCandle` of size `n`. `nextCandle[i]` stores the index of the closest candle to the right of or at index `i`. This is computed in a single pass from right to left.
*   Initialize an `answer` array.
*   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.
*   Return the `answer` array.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> platesBetweenCandles(string s, vector<vector<int>> &queries) {
    int n = s.size();
    vector<int> presum(n + 1);
    for (int i = 0; i < n; ++i)
      presum[i + 1] = presum[i] + (s[i] == '*');
    vector<int> left(n);
    vector<int> right(n);
    for (int i = 0, l = -1; i < n; ++i) {
      if (s[i] == '|')
        l = i;
      left[i] = l;
    }
    for (int i = n - 1, r = -1; i >= 0; --i) {
      if (s[i] == '|')
        r = i;
      right[i] = r;
    }
    vector<int> ans(queries.size());
    for (int k = 0; k < queries.size(); ++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;
  }
};

```

### Python

```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 ans

```