2055. Plates Between Candles

Problem

https://leetcode.com/problems/plates-between-candles/description/

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, 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:

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:

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

Approach 1: Bruteforce to perform a linear scan for each query

For each query (left,right) we can search for plates in the string and return the count. Following will be steps.

1. For left , find the closest candle to the right, let’s say i.
2. For right , find the closest candle to the left, let’s say j.
3. Find out the number of plates between i and j .
4. For each query, time complexity would be O(n)
5. For total queries, time complexity would be O(q*n)

Following is the code for reference.

/**
 * @param {string} s
 * @param {number[][]} queries
 * @return {number[]}
 */
var platesBetweenCandles = function (s, queries) {
    const n = s.length;
    const search = (left, right) => {
        // closest candle to left
        let i = left;
        while (s[i] !== '|' && i <= right) {
            i++;
        }
        if (s[i] !== '|' || i > right) {
            return 0;
        }
        // closest candle to right
        let j = right;
        while (s[j] !== '|' && j >= left) {
            j--;
        }
        if (s[j] !== '|' || j < left) {
            return 0;
        }
        // i & j points to candle, now count the platest
        let count = 0;
        while (i <= j) {
            if (s[i] === '*') {
                count++;
            }
            i++;
        }
        return count;
    }
    return queries.map(([left, right]) => search(left, right));
};

Approach 2: Improve the search for the candle using a binary search and prefix sum

The intuition behind this approach.

1. To search faster, we can apply binary search.
2. To apply binary search, we need search space in monotonic increasing order.
3. We can count the number of plates and candles form left to right and build the prefix sum. This will make input monotonic increasing and then we can do a binary search to find out the closes candle and count the plates using the prefix sum.

How to apply the algorithm?

1. Build prefix sum of <plates_count, candles_count> from left to right.
2. For given query (left, right) , if we have candles at left/right then no need to search.
3. Else we will search using binary search for the closest candle.

/**
 * @param {string} s
 * @param {number[][]} queries
 * @return {number[]}
 */
var platesBetweenCandles = function (s, queries) {
    const n = s.length;
    const prefix = [[0, 0]]; //[plates, candle]
    for (const chr of s) {
        const [p, c] = prefix[prefix.length - 1];
        const i = chr === '*' ? p + 1 : p;
        const j = chr === '|' ? c + 1 : c;
        prefix.push([i, j]);
    }
    prefix.shift(); // remove the first which was added as placeholder
    const lowerBound = (start, end, key) => {
        let left = start;
        let right = end;
        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);
            if (prefix[mid][1] < key) {
                // candle not found on mid, keep moving right
                left = mid + 1;
            } else if ((prefix[mid][1] > key)) {
                // candle not found on mid, keep moving left
                right = mid - 1;
            } else {
                // candle found, keep moving to left for lower candle count
                right = mid - 1;
            }
        }
        return left <= end ? left : start;
    }
    
    const search = (left, right) => {
        let start = left;
        let end = right;
        if (s[start] === '*') {
            // Search for one higher candles to right
            start = lowerBound(start, end, prefix[start][1] + 1);
        }
        if (s[end] === '*') {
            // Search for same candles to left
            end = lowerBound(start, end , prefix[end][1]);
        }
        return prefix[end][0] - prefix[start][0];
    }
    return queries.map(([left, right]) => search(left, right));
};

Approach 3: Use the prefix sum to precompute the answer

We will build following three arrays

1. prev_candle: Index of the previous candle, if not found then -1
2. next_candle: Index of next candle, if not found then -1
3. prefixSum: Prefix sum of plates.

 index     :   0  1  2  3  4  5  6  7  8  9
   s       :  '*  *  |  *  *  |  *  *  *  |'

 prev      :  -1 -1  2  2  2  5  5  5  5  9
 next      :   2  2  2  5  5  5  9  9  9  9

 prefixSum :   1  2  2  3  4  4  5  6  7  7

For given query (i,j) , we can find answer in three steps.

1. Find the next candle index for i , start = next[i]
2. Find the previous candle index for j , end = prev[j]
3. Get the plates to count as prefixSum[end] — prefixSum[start]

/**
 * @param {string} s
 * @param {number[][]} queries
 * @return {number[]}
 */
var platesBetweenCandles = function (s, queries) {
    const n = s.length;
    const prevCandle = new Array(n).fill(-1);
    const nextCandle = new Array(n).fill(-1);
    const prefixSumPlates = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        prevCandle[i] = s[i] === '|' ? i : (i === 0 ? -1 : prevCandle[i - 1]);
        const j = n - i - 1;
        nextCandle[j] = s[j] === '|' ? j : (j === n - 1 ? -1 : nextCandle[j + 1]);
        prefixSumPlates[i] = (i === 0) ? (s[i] === '*' ? 1 : 0) : (s[i] === '*' ? prefixSumPlates[i - 1] + 1 : prefixSumPlates[i - 1]);
    }
    return queries.map(([i, j]) => {
        const start = nextCandle[i] < i || nextCandle[i] > j ? 0 : nextCandle[i];
        const end = prevCandle[j] < i  || prevCandle[j] > j ? 0 : prevCandle[j];
        return prefixSumPlates[end] - prefixSumPlates[start];
    });
};

This post is based on the Leetcode solution https://leetcode.com/problems/plates-between-candles/solutions/1586720/intuition-explained-prefix-sum-and-binary-search-c-clean-code/.

Happy coding :-)