2055. Plates Between Candles LeetCode Solution

Last updated: February 26, 2025

In this guide, you will get 2055. Plates Between Candles LeetCode Solution with the best time and space complexity. The solution to Plates Between Candles problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Plates Between Candles solution in C++
Plates Between Candles solution in Java
Plates Between Candles solution in Python
Additional Resources

2055. Plates Between Candles LeetCode Solution image

Problem Statement of Plates Between Candles

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:

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

Complexity Analysis

Time Complexity: O(n + q\log n)
Space Complexity: O(n)

2055. Plates Between Candles LeetCode Solution in C++

class Solution {
 public:
  vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
    vector<int> ans;
    vector<int> indices;  // indices of '|'

    for (int i = 0; i < s.length(); ++i)
      if (s[i] == '|')
        indices.push_back(i);

    for (const vector<int>& query : queries) {
      const int left = query[0];
      const int right = query[1];
      const int l = ranges::lower_bound(indices, left) - indices.begin();
      const int r = ranges::upper_bound(indices, right) - indices.begin() - 1;
      if (l < r) {
        const int lengthBetweenCandles = indices[r] - indices[l] + 1;
        const int numCandles = r - l + 1;
        ans.push_back(lengthBetweenCandles - numCandles);
      } else {
        ans.push_back(0);
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2055. Plates Between Candles LeetCode Solution in Java

class Solution {
  public int[] platesBetweenCandles(String s, int[][] queries) {
    int[] ans = new int[queries.length];
    List<Integer> indices = new ArrayList<>(); // indices of '|'

    for (int i = 0; i < s.length(); ++i)
      if (s.charAt(i) == '|')
        indices.add(i);

    for (int i = 0; i < queries.length; ++i) {
      final int left = queries[i][0];
      final int right = queries[i][1];
      final int l = firstGreaterEqual(indices, left);
      final int r = firstGreaterEqual(indices, right + 1) - 1;
      if (l < r) {
        final int lengthBetweenCandles = indices.get(r) - indices.get(l) + 1;
        final int numCandles = r - l + 1;
        ans[i] = lengthBetweenCandles - numCandles;
      }
    }

    return ans;
  }

  private int firstGreaterEqual(List<Integer> indices, int target) {
    final int i = Collections.binarySearch(indices, target);
    return i < 0 ? -i - 1 : i;
  }
}
// code provided by PROGIEZ

2055. Plates Between Candles LeetCode Solution in Python

class Solution:
  def platesBetweenCandles(self, s: str, queries: list[list[int]]) -> list[int]:
    ans = []
    indices = [i for i, c in enumerate(s) if c == '|']  # indices of '|'

    for left, right in queries:
      l = bisect.bisect_left(indices, left)
      r = bisect.bisect_right(indices, right) - 1
      if l < r:
        lengthBetweenCandles = indices[r] - indices[l] + 1
        numCandles = r - l + 1
        ans.append(lengthBetweenCandles - numCandles)
      else:
        ans.append(0)

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents