2055.plates-between-candle.md

2055. Plates Between Candles

Breakdowns

1. Given a string which contains ONLY plates, how to count the number of plates from a query?

We can use prefix sum to count the number of plates.

2. Given a string which contains ONLY plates and candles, how to count the number of plates?

We can use prefix sum to count the number of plates and candles, then return the number of plates - number of candles.

3. Given a string which contains ONLY plates and candles, how to count the number of plates between two candles?

This problem.

Binary Search + Prefix Sum

We are calculating the number of plates between two candles, what does "between two candles" mean? We are only allowed to count the * between two candles.

    // query
    <--------->
... * * | * * | ...
    X X   ^^^   
          Answer: 2

Given a query (L, R), we need to find the leftmost and rightmost candles between L and R.

... * * | * * | ...
        ^     ^ // leftmost and rightmost candles
    L         R    

We can use binary search to find the leftmost and rightmost candles:

• Leftmost: Search the first element that L <= candles.

... * * | ... | ... | * * *
        ^
    L                     R

• Rightmost: Search the last element that candles <= R.

... * * | ... | ... | * * *
                    ^
    L                     R

We can iterate through the string to get the positions of the candles,

How can we count the number of plates, we can use prefix sum to accumulate the number of plates.

0 1 2 3 4 5 6 7
* * * | * * | *
1 2 3 3 4 5 5 6

0-Indexed Implementation

fun platesBetweenCandles(s: String, queries: Array<IntArray>): IntArray {
    val candlePositions = mutableListOf<Int>()
    val prefixSum = IntArray(s.length)
    var sum = 0
    for (i in 0 until s.length) {
        val c = s[i]
        if (c == candle) {
            candlePositions.add(i)
        } else {
            sum++
        }
        prefixSum[i] = sum
    }
    val n = queries.size
    val answer = IntArray(n)
    for (q in queries.indices) {
        val (l, r) = queries[q]
        val leftmost = searchLeftmost(candlePositions, l)
        val rightmost = searchRightmost(candlePositions, r)
        
        if (leftmost == -1 || rightmost == -1) {
            continue
        } else {
            val left = candlePositions[leftmost]
            val right = candlePositions[rightmost]
            // check if the leftmost and rightmost candles are between l and r
            if (left in l..r && right in l..r) {
                answer[q] = prefixSum[candlePositions[rightmost]] - prefixSum[candlePositions[leftmost]]
            }
        }
    }
    return answer
}

1-Indexed Implementation (with Sentinel)

Using 1-indexed prefix sum with sentinel prefix[0] = 0 to avoid edge case handling.

fun platesBetweenCandles(s: String, queries: Array<IntArray>): IntArray {
    val n = s.length
    val candlePositions = mutableListOf<Int>()
    // 1-indexed: prefix[i] = count of plates in s[0..i-1]
    val prefix = IntArray(n + 1)
    for (i in 0 until n) {
        if (s[i] == '|') {
            candlePositions.add(i)
        }
        prefix[i + 1] = prefix[i] + if (s[i] == '*') 1 else 0
    }
    
    // Get count of plates in s[l..r]
    fun getPlates(l: Int, r: Int): Int = prefix[r + 1] - prefix[l]
    
    return IntArray(queries.size) { q ->
        val (l, r) = queries[q]
        val leftmost = searchLeftmost(candlePositions, l)
        val rightmost = searchRightmost(candlePositions, r)
        
        if (leftmost == -1 || rightmost == -1) {
            0
        } else {
            val left = candlePositions[leftmost]
            val right = candlePositions[rightmost]
            if (left in l..r && right in l..r && left < right) {
                getPlates(left, right)  // No edge case handling needed
            } else {
                0
            }
        }
    }
}

// Search the leftmost candle
/**
candles = [2, 3, 6]
range = 1
1 2 3 4 5 6 7 8 9
  | |     |
L    
Search the first element that "target <= positions[i]" = 2
    */
private fun searchLeftmost(positions: List<Int>, target: Int): Int {
    var left = 0
    var right = positions.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        val isValid = target <= positions[middle]
        if (isValid) right = middle - 1
        else left = middle + 1
    }
    return if (left in 0 until positions.size) left else -1
}

/**
candles = [2, 3, 6]
range = 9
1 2 3 4 5 6 7 8 9
  | |     |
                R    
Search the last element that "positions[i] <= target" = 6
 */
private fun searchRightmost(positions: List<Int>, target: Int): Int {
    var left = 0
    var right = positions.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        val isValid = positions[middle] <= target
        if (isValid) left = middle + 1
        else right = middle - 1
    }
    return if (right in 0 until positions.size) right else -1
}