Plates Between Candles

Medium
1230.

Plates Between Candles

Plates Between Candles is a medium coding problem on arrays, strings and binary search, asked in Amazon, Google and Meta interviews.

A long table is described by the string s: '*' is a plate and '|' is a candle. Positions are 0-indexed.

Each query queries[i] = [left, right] looks only at the section s[left..right] (inclusive). Within that section, a plate counts if there is at least one candle to its left and at least one candle to its right inside the same section.

Return an array whose i-th element is the number of counted plates for the i-th query.

Example 1

Input
s = "*|*|**|*", queries = [[0,7],[1,3],[2,5],[0,1]]
Output
[3,1,0,0]
Explanation
For `[0,7]` the outermost candles are at 1 and 6, enclosing the plates at 2, 4 and 5. The section `[2,5]` holds a single candle, so nothing is enclosed.

Example 2

Input
s = "||**||", queries = [[0,5],[2,3]]
Output
[2,0]

Constraints

  • 3 <= s.length <= 10^5
  • s consists of '*' and '|' characters
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= left <= right < s.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number[][]} queries
 * @return {number[]}
 */
var platesBetweenCandles = function(s, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Plates Between Candles — Solution in Python, Java & C++

Plates Between Candles solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Plates Between Candles is a medium coding problem on arrays, strings and binary search, asked in Amazon, Google and Meta interviews.

Problem statement

A long table is described by the string s: '*' is a plate and '|' is a candle. Positions are 0-indexed.

Each query queries[i] = [left, right] looks only at the section s[left..right] (inclusive). Within that section, a plate counts if there is at least one candle to its left and at least one candle to its right inside the same section.

Return an array whose i-th element is the number of counted plates for the i-th query.

Example 1

Input: s = "*|*|**|*", queries = [[0,7],[1,3],[2,5],[0,1]]
Output: [3,1,0,0]
Explanation: For `[0,7]` the outermost candles are at 1 and 6, enclosing the plates at 2, 4 and 5. The section `[2,5]` holds a single candle, so nothing is enclosed.

Example 2

Input: s = "||**||", queries = [[0,5],[2,3]]
Output: [2,0]

Constraints

  • 3 <= s.length <= 10^5
  • s consists of '*' and '|' characters
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= left <= right < s.length

Hints for Plates Between Candles

  1. Hint 1

    Inside a section, only the leftmost and the rightmost candle matter: every plate between them is enclosed.

  2. Hint 2

    Precompute, for every index, the nearest candle at or to its right and the nearest candle at or to its left.

  3. Hint 3

    With a prefix count of plates, the answer for [l, r] is the number of plates between nextCandle[l] and prevCandle[r] — or 0 when those candles do not form a valid pair.

How to solve Plates Between Candles

A query's answer is the number of plates between the first candle at or after left and the last candle at or before right. Three precomputed arrays make each query O(1).

Approach

  1. Build pre, where pre[i] is the number of plates in s[0..i-1].
  2. Build prevCandle[i], the index of the last candle at or before i (or -1), with a left-to-right sweep.
  3. Build nextCandle[i], the index of the first candle at or after i (or -1), with a right-to-left sweep.
  4. For a query [l, r], let a = nextCandle[l] and b = prevCandle[r]. If both exist and a < b, the answer is pre[b] - pre[a]; otherwise it is 0.

Why it works

A plate inside the section is enclosed exactly when it lies strictly between the section's leftmost candle a and rightmost candle b. nextCandle[l] is the leftmost candle of the section if it is not beyond r, and prevCandle[r] the rightmost if it is not before l; when a < b both are inside the section. The prefix difference counts plates in [a, b), and since s[a] is a candle that is exactly the plates strictly between them.

Complexity

  • Time — O(n + q)
  • Space — O(n)

Pitfalls

  • A section with zero or one candle encloses nothing — check a < b, not just that both exist.
  • Use the candles inside the section, not the nearest candles outside it.
  • Scanning each query directly is O(n·q) and too slow at the full limits.

Reference solution

Python

from typing import List

def platesBetweenCandles(s: str, queries: List[List[int]]) -> List[int]:
    n = len(s)
    pre = [0] * (n + 1)
    for i, ch in enumerate(s):
        pre[i + 1] = pre[i] + (1 if ch == "*" else 0)
    prev_c = [-1] * n
    last = -1
    for i in range(n):
        if s[i] == "|":
            last = i
        prev_c[i] = last
    next_c = [-1] * n
    last = -1
    for i in range(n - 1, -1, -1):
        if s[i] == "|":
            last = i
        next_c[i] = last
    out = []
    for l, r in queries:
        a, b = next_c[l], prev_c[r]
        out.append(pre[b] - pre[a] if a != -1 and b != -1 and a < b else 0)
    return out

Java

public static int[] platesBetweenCandles(String s, int[][] queries) {
    int n = s.length();
    int[] pre = new int[n + 1], prevC = new int[n], nextC = new int[n];
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + (s.charAt(i) == '*' ? 1 : 0);
    int last = -1;
    for (int i = 0; i < n; i++) { if (s.charAt(i) == '|') last = i; prevC[i] = last; }
    last = -1;
    for (int i = n - 1; i >= 0; i--) { if (s.charAt(i) == '|') last = i; nextC[i] = last; }
    int[] out = new int[queries.length];
    for (int q = 0; q < queries.length; q++) {
        int a = nextC[queries[q][0]], b = prevC[queries[q][1]];
        out[q] = (a != -1 && b != -1 && a < b) ? pre[b] - pre[a] : 0;
    }
    return out;
}

C++

vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
    int n = s.size();
    vector<int> pre(n + 1, 0), prevC(n, -1), nextC(n, -1);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + (s[i] == '*' ? 1 : 0);
    int last = -1;
    for (int i = 0; i < n; i++) { if (s[i] == '|') last = i; prevC[i] = last; }
    last = -1;
    for (int i = n - 1; i >= 0; i--) { if (s[i] == '|') last = i; nextC[i] = last; }
    vector<int> out;
    for (auto& q : queries) {
        int a = nextC[q[0]], b = prevC[q[1]];
        out.push_back((a != -1 && b != -1 && a < b) ? pre[b] - pre[a] : 0);
    }
    return out;
}

JavaScript

var platesBetweenCandles = function(s, queries) {
    var n = s.length;
    var pre = new Array(n + 1).fill(0);
    for (var i = 0; i < n; i++) pre[i + 1] = pre[i] + (s[i] === "*" ? 1 : 0);
    var prevC = new Array(n), nextC = new Array(n), last = -1;
    for (var i2 = 0; i2 < n; i2++) { if (s[i2] === "|") last = i2; prevC[i2] = last; }
    last = -1;
    for (var i3 = n - 1; i3 >= 0; i3--) { if (s[i3] === "|") last = i3; nextC[i3] = last; }
    return queries.map(function (q) {
        var a = nextC[q[0]], b = prevC[q[1]];
        return a !== -1 && b !== -1 && a < b ? pre[b] - pre[a] : 0;
    });
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings