Skip to content

2055. Plates Between Candles 👍

  • Time: $O(n + q\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
    vector<int> ans;
    vector<int> A;  // Indices of '|'

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

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

    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
  public int[] platesBetweenCandles(String s, int[][] queries) {
    int[] ans = new int[queries.length];
    List<Integer> A = new ArrayList<>(); // Indices of '|'

    for (int i = 0; i < s.length(); ++i)
      if (s.charAt(i) == '|')
        A.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(A, left);
      final int r = firstGreaterEqual(A, right + 1) - 1;
      if (l < r) {
        final int lengthBetweenCandles = A.get(r) - A.get(l) + 1;
        final int numCandles = r - l + 1;
        ans[i] = lengthBetweenCandles - numCandles;
      }
    }

    return ans;
  }

  private int firstGreaterEqual(List<Integer> A, int target) {
    int l = 0;
    int r = A.size();
    while (l < r) {
      final int m = (l + r) / 2;
      if (A.get(m) >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
    ans = []
    A = [i for i, c in enumerate(s) if c == '|']  # Indices of '|'

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

    return ans

Approach 2: Linear

  • Time: $O(n + q)$
  • Space: $O(n + q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
 public:
  vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
    const int n = s.length();
    vector<int> ans;
    vector<int> closestLeftCandle(n);
    vector<int> closestRightCandle(n);
    vector<int> candleCount(n);  // candleCount[i] := # of candles in s[0..i]
    int candle = -1;
    int count = 0;

    for (int i = 0; i < n; ++i) {
      if (s[i] == '|') {
        candle = i;
        ++count;
      }
      closestLeftCandle[i] = candle;
      candleCount[i] = count;
    }

    candle = -1;
    for (int i = n - 1; i >= 0; --i) {
      if (s[i] == '|')
        candle = i;
      closestRightCandle[i] = candle;
    }

    for (const vector<int>& q : queries) {
      const int left = q[0];
      const int right = q[1];
      const int l = closestRightCandle[left];
      const int r = closestLeftCandle[right];
      if (l == -1 || r == -1 || l > r) {
        ans.push_back(0);
      } else {
        const int lengthBetweenCandles = r - l + 1;
        const int numCandles = candleCount[r] - candleCount[l] + 1;
        ans.push_back(lengthBetweenCandles - numCandles);
      }
    }

    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
  public int[] platesBetweenCandles(String s, int[][] queries) {
    final int n = s.length();
    int[] ans = new int[queries.length];
    int[] closestLeftCandle = new int[n];
    int[] closestRightCandle = new int[n];
    int[] candleCount = new int[n]; // candleCount[i] := # of candles in s[0..i]
    int candle = -1;
    int count = 0;

    for (int i = 0; i < n; ++i) {
      if (s.charAt(i) == '|') {
        candle = i;
        ++count;
      }
      closestLeftCandle[i] = candle;
      candleCount[i] = count;
    }

    candle = -1;
    for (int i = n - 1; i >= 0; --i) {
      if (s.charAt(i) == '|')
        candle = i;
      closestRightCandle[i] = candle;
    }

    for (int i = 0; i < queries.length; ++i) {
      final int left = queries[i][0];
      final int right = queries[i][1];
      final int l = closestRightCandle[left];
      final int r = closestLeftCandle[right];
      if (i == -1 || r == -1 || l > r)
        continue;
      final int lengthBetweenCandles = r - l + 1;
      final int numCandles = candleCount[r] - candleCount[l] + 1;
      ans[i] = lengthBetweenCandles - numCandles;
    }

    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
  def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
    n = len(s)
    ans = []
    closestLeftCandle = [0] * n
    closestRightCandle = [0] * n
    candleCount = [0] * n  # candleCount[i] := # Of candles in s[0..i]
    candle = -1
    count = 0

    for i, c in enumerate(s):
      if c == '|':
        candle = i
        count += 1
      closestLeftCandle[i] = candle
      candleCount[i] = count

    candle = -1
    for i, c in reversed(list(enumerate(s))):
      if c == '|':
        candle = i
      closestRightCandle[i] = candle

    for left, right in queries:
      l = closestRightCandle[left]
      r = closestLeftCandle[right]
      if l == -1 or r == -1 or l > r:
        ans.append(0)
      else:
        lengthBetweenCandles = r - l + 1
        numCandles = candleCount[r] - candleCount[l] + 1
        ans.append(lengthBetweenCandles - numCandles)

    return ans