Plates Between Candles

Leetcode Link

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 (at indices 6 and 7), 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

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

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

Solution

To find the number of plates for each query (qleft, qright), we set up an array candles to store the candles' indices, so that we could later do basic arithmetic on the indices to find the number of plates. First, we need to find the outside candles' indices in the input s, this can be done via binary search in candles. We will find left_pos and right_pos indicating the outside candle's position in s. Then, We know that the number of plates is given by the interval between the two bounding candles subtracted by the number of candles in between. With the indices left_pos and right_pos, we can derive the number of plates to be (candles[right_pos] - candles[left_pos]) - (right_pos - left_pos).

Implementation

def platesBetweenCandles(s, queries):
  candles = []
  for i in range(len(s)):
      if s[i] == '|': candles.append(i)

  res = []
  for qleft, qright in queries:
      left_pos, right_pos = -1, -1
      
      # 1. find index of first candle that comes after qleft
      left, right = 0, len(candles)-1
      while left <= right:
          mid = (left+right) // 2
          if candles[mid] >= qleft:
              right = mid - 1
              left_pos = mid
          else:
              left = mid + 1

      # 2. find index of last candle that comes before qright
      left, right = 0, len(candles)-1
      while left <= right:
          mid = (left+right) // 2
          if candles[mid] <= qright:
              left = mid + 1
              right_pos = mid
          else:
              right = mid - 1

      # result = range between two outermost candles - candle count in between
      if (left_pos != -1) & (right_pos!= -1) & (right_pos > left_pos):
          res.append((candles[right_pos] - candles[left_pos]) - (right_pos - left_pos))
      else:
          res.append(0)
  return res

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know

Plates Between Candles

Solution

Implementation

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Recommended Readings