2055. Plates Between Candles

Approach 1: Binary Search

• Time: $O(n + q\log n)$
• Space: $O(n)$

C++JavaPython

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

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

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

Approach 2: Linear

• Time: $O(n + q)$
• Space: $O(n + q)$

C++JavaPython

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] := the number 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>& query : queries) {
      const int left = query[0];
      const int right = query[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;
  }
};

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] := the number 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;
  }
}

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] := the number 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