Plates Between Candles

1class Solution {
2    // time O(n)
3    public int[] platesBetweenCandles(String s, int[][] queries) {
4        int[] prefixSum = new int[s.length()];
5        int count = 0;
6        int[] nearestLeftCandle = new int[s.length()];
7        int[] nearestRightCandle = new int[s.length()];
8        int lastLeftCandleIndex = -1;
9        int lastRightCandleIndex = -1;
10        for (int i = 0; i < s.length(); i++) {
11            // Count the number of stars so far at each index
12            if (s.charAt(i) == '*') {
13                count++;
14            }
15            prefixSum[i] = count;
16
17            // Keep track of indices for the nearest left and right candle
18            if (s.charAt(i) == '|') {
19                lastLeftCandleIndex = i;
20            }
21            nearestLeftCandle[i] = lastLeftCandleIndex;
22
23            if (s.charAt(s.length() - i - 1) == '|') {
24                lastRightCandleIndex = s.length() - i - 1;
25            }
26            nearestRightCandle[s.length() - i - 1] = lastRightCandleIndex;
27        }
28
29        int[] counts = new int[queries.length];
30        for (int i = 0; i < queries.length; i++) {
31            int[] query = queries[i];
32
33            int leftCandleIndex = nearestRightCandle[query[0]];
34            int rightCandleIndex = nearestLeftCandle[query[1]];
35
36            if (leftCandleIndex == -1 || rightCandleIndex == -1 || leftCandleIndex >= rightCandleIndex) {
37                counts[i] = 0;
38            }
39            else {
40                counts[i] = prefixSum[rightCandleIndex] - prefixSum[leftCandleIndex];
41            }
42        }
43
44        return counts;
45    }
46}