2055. Plates Between Candles
Problem Description
In this problem, we are given a string s
representing a table where '*'
characters signify plates and '|'
characters represent candles placed on the table. Alongside the string, we receive an array of queries queries
, with each query given as a pair of indices [left_i, right_i]
. This pair indicates a specific substring of s
ā from index left_i
to right_i
, inclusive.
The task is to determine how many plates are situated between candles within these substrings. It's important to note that a plate is only counted if it has at least one candle to its left and one candle to its right within the boundary of the substring defined by the query.
Our goal is to return an array of integers where each element corresponds to the count of plates between candles for each query in queries
.
Intuition
The brute force approach to solving this would entail scanning the substring for each query to count the plates between candles, which could lead to a significant amount of repeated work, especially with overlapping or similar queries.
To handle this problem efficiently, we employ a prefix sum array and two additional arrays to track the positions of the leftmost and rightmost candles relative to each position.
The prefix sum array, presum
, gets constructed such that presum[i]
stores the sum of plates encountered from the start of the string up to index i - 1
. This allows us to calculate the number of plates between any two candle positions quickly by subtracting the appropriate prefix sums.
However, before we can use this array, we need to know where the boundaries are ā the closest candles to the left and right of each plate. For that, we introduce two arrays: left
and right
. As we iterate through the string, we update left[i]
with the last seen candle position on the left of index i
and right[i]
with the upcoming candle position on the right of index i
. These arrays help us locate the nearest candles for any given plate quickly.
With these arrays ready, we can now process each query. We take the given query range [l, r]
and use the right
array to find the first candle to the right of l
and the left
array to find the last candle to the left of r
. If these exist and are properly positioned (the right of l
is less than the left of r
), we've identified the boundaries of the relevant candle-plate-candle sequence. Then we can use the differences of the prefix sums to find the number of plates between these two candles.
This approach allows us to process queries efficiently since we reduced the problem to constant-time look-ups and a single subtraction operation per query, after the initial setup of the prefix sum and left/right boundary arrays.
Learn more about Binary Search and Prefix Sum patterns.
Solution Approach
The solution approach breaks down into several key steps corresponding to the following algorithmic patterns and data structures:
Step 1: Prefix Sum Array
The first step is constructing the presum
array. It accumulates the count of plates ('*'
) as we iterate through the string s
. presum[i]
is computed as presum[i - 1] + (s[i - 1] == '*')
. This setup will later enable us to quickly calculate the number of plates between any two indices.
Step 2: Leftmost and Rightmost Candle Arrays
We initialize two arrays, left
and right
, to record the positions of the nearest candles on the left and right sides of each index in s
.
- As we scan the string from left to right, each
left[i]
is updated toi
ifs[i]
is a candle. If not, it carries over the position of the last encountered candle. - Conversely, scanning from right to left,
right[i]
is set toi
ifs[i]
is a candle. Otherwise, it retains the position of the next candle to the right.
The purpose of these arrays is to determine, for each plate, the positions of the closest candles that potentially enclose it in a valid sequence.
Step 3: Query Processing
For each query [l, r]
in queries
:
- We find the closest candle to the right of
l
usingright[l]
and the closest candle to the left ofr
usingleft[r]
. Let's refer to these positions asi
andj
, respectively. - We then check if
i
andj
form a valid boundary ā that is, ifi
is beforej
. If not, no plates can be counted for this query. - If they do form a valid boundary, the number of plates between these candles is the difference between the
presum
just after the left candle and just before the right candle:presum[j] - presum[i + 1]
. - This result is stored in the
ans
array at the position corresponding to the current query.
The final output is the ans
array, which contains the count of plates between candles for each query.
The algorithm leverages prefix sums, array scanning, and good use of boundary tracking to optimize the repeated calculations involved in answering each query. This results in an efficient solution that only requires a linear scan of the input string and the queries.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take an example to illustrate the solution approach:
Given a string s
= "||**|", and queries queries
= [[2, 5], [0, 9]]. We want to count the number of plates ('') that are located between candles ('|') for each query range.
Step 1: Prefix Sum Array
We create the presum
array as follows:
s
= "|*|**|"presum
= [0, 0, 0, 1, 2, 3, 3, 4, 5, 5]
Each element in presum
indicates the total number of plates to the left of it.
Step 2: Leftmost and Rightmost Candle Arrays
Next, we construct the left
and right
arrays:
left
= [-1, -1, 2, 2, 2, 2, 6, 6, 6, 6]right
= [2, 2, 2, 6, 6, 6, 6, 9, 9, 9]
The left
array is constructed by scanning from left to right and marking the latest position of a candle. Similarly, right
is constructed by scanning from right to left.
Step 3: Query Processing
Now we answer each query:
-
For the query
[2, 5]
, we check:- Nearest right candle from 2 (inclusive):
right[2]
= 2 - Nearest left candle from 5 (inclusive):
left[5]
= 2 - Since
right[2]
equalsleft[5]
, there are no valid boundaries within this substring, so the result for this query is 0.
- Nearest right candle from 2 (inclusive):
-
For the query
[0, 9]
, we check:- Nearest right candle from 0:
right[0]
= 2 - Nearest left candle from 9:
left[9]
= 6 - We have a valid boundary because 2 < 6.
- The number of plates is
presum[6] - presum[2 + 1]
which equals3 - 1 = 2
. There are 2 plates between the candles at positions 2 and 6.
- Nearest right candle from 0:
After processing both queries, our ans
array, which holds the resulting counts, is [0, 2].
This example completes the walk-through of the solution approach using an example string and a couple of queries. The algorithm efficiently computes the desired count using prefix sums, and nearest left/right candle tracking to avoid repeated calculations for each query.
Solution Implementation
1from typing import List
2
3class Solution:
4 def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
5 # Get the length of the string 's'
6 n = len(s)
7
8 # Initialize a prefix sum array that will count the number of plates ('*') up to index 'i'
9 prefix_sum = [0] * (n + 1)
10 for i, char in enumerate(s):
11 # Build the prefix sum array
12 prefix_sum[i + 1] = prefix_sum[i] + (char == '*')
13
14 # Initialize arrays to store the index of the closest candle to the left and right
15 closest_left_candle = [0] * n
16 closest_right_candle = [0] * n
17 left_candle_index = right_candle_index = -1
18 for i, char in enumerate(s):
19 # Update the index when a candle is found
20 if char == '|':
21 left_candle_index = i
22 closest_left_candle[i] = left_candle_index
23
24 # Populate the closest_right_candle array in reverse
25 for i in range(n - 1, -1, -1):
26 if s[i] == '|':
27 right_candle_index = i
28 closest_right_candle[i] = right_candle_index
29
30 # Initialize the answer array, one entry for each query
31 answer = [0] * len(queries)
32
33 # Process each query
34 for index, (left, right) in enumerate(queries):
35 # Find the closest right candle for the left index
36 # And the closest left candle for the right index
37 candle_to_the_right = closest_right_candle[left]
38 candle_to_the_left = closest_left_candle[right]
39
40 # If valid candle indexes are found and they do not overlap
41 if candle_to_the_right >= 0 and candle_to_the_left >= 0 and candle_to_the_right < candle_to_the_left:
42 # Calculate the number of plates between the candles
43 answer[index] = prefix_sum[candle_to_the_left] - prefix_sum[candle_to_the_right + 1]
44
45 # Return the result list containing the number of plates for each query
46 return answer
47
1class Solution {
2
3 // Method to calculate the number of plates between candles based on a set of queries
4 public int[] platesBetweenCandles(String s, int[][] queries) {
5 int length = s.length(); // Length of the string
6
7 // Array to hold the prefix sum of plates up to each position
8 int[] prefixSum = new int[length + 1];
9 // Calculate the prefix sum of plates
10 for (int i = 0; i < length; ++i) {
11 prefixSum[i + 1] = prefixSum[i] + (s.charAt(i) == '*' ? 1 : 0);
12 }
13
14 // Arrays to hold the index of the nearest left and right candles to each position
15 int[] nearestLeftCandle = new int[length];
16 int[] nearestRightCandle = new int[length];
17
18 // Calculate the nearest left candle positions
19 for (int i = 0, lastCandleIndex = -1; i < length; ++i) {
20 if (s.charAt(i) == '|') {
21 lastCandleIndex = i; // Update last seen candle
22 }
23 nearestLeftCandle[i] = lastCandleIndex;
24 }
25
26 // Calculate the nearest right candle positions
27 for (int i = length - 1, nextCandleIndex = -1; i >= 0; --i) {
28 if (s.charAt(i) == '|') {
29 nextCandleIndex = i; // Update next seen candle
30 }
31 nearestRightCandle[i] = nextCandleIndex;
32 }
33
34 // Array to hold the results of queries
35 int[] answer = new int[queries.length];
36
37 // Iterate over each query to determine the number of plates between candles
38 for (int k = 0; k < queries.length; ++k) {
39 // Find the nearest right candle index from the start of the current query
40 int startIndex = nearestRightCandle[queries[k][0]];
41 // Find the nearest left candle index from the end of the current query
42 int endIndex = nearestLeftCandle[queries[k][1]];
43
44 // If valid candle indices are found and the start index is before the end index
45 if (startIndex >= 0 && endIndex >= 0 && startIndex < endIndex) {
46 // Calculate the number of plates by subtracting the prefix sums
47 answer[k] = prefixSum[endIndex] - prefixSum[startIndex + 1];
48 }
49 }
50
51 return answer;
52 }
53}
54
1#include <vector>
2#include <string>
3
4using std::vector;
5using std::string;
6
7class Solution {
8public:
9 // Function to calculate the number of plates between candles
10 vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
11 int n = s.size();
12 // Create a prefix sum array to keep track of number of plates
13 vector<int> prefixSum(n + 1);
14 // Calculating the prefix sum of the plates
15 for (int i = 0; i < n; ++i) {
16 prefixSum[i + 1] = prefixSum[i] + (s[i] == '*');
17 }
18 // Arrays to store the nearest left and right candle positions
19 vector<int> nearestLeftCandle(n);
20 vector<int> nearestRightCandle(n);
21
22 // Find the nearest left candle for each position
23 for (int i = 0, lastCandleIndex = -1; i < n; ++i) {
24 if (s[i] == '|') lastCandleIndex = i;
25 nearestLeftCandle[i] = lastCandleIndex;
26 }
27 // Find the nearest right candle for each position
28 for (int i = n - 1, nextCandleIndex = -1; i >= 0; --i) {
29 if (s[i] == '|') nextCandleIndex = i;
30 nearestRightCandle[i] = nextCandleIndex;
31 }
32
33 // Answer vector to store the result for each query
34 vector<int> answer(queries.size());
35 // Process each query
36 for (int k = 0; k < queries.size(); ++k) {
37 // Find the nearest right candle from the start index of the query
38 int startCandleIndex = nearestRightCandle[queries[k][0]];
39 // Find the nearest left candle from the end index of the query
40 int endCandleIndex = nearestLeftCandle[queries[k][1]];
41 // If both candles are valid and the start candle is to the left of the end candle
42 if (startCandleIndex >= 0 && endCandleIndex >= 0 && startCandleIndex < endCandleIndex) {
43 // Calculate the number of plates between candles and store it in the answer
44 answer[k] = prefixSum[endCandleIndex] - prefixSum[startCandleIndex + 1];
45 }
46 }
47 return answer;
48 }
49};
50
1// Importing necessary libraries
2import { Vector, String } from "prelude-ts";
3
4// Function to calculate the number of plates between candles
5function platesBetweenCandles(s: string, queries: number[][]): number[] {
6 const n: number = s.length;
7 // Create a prefix sum array to keep track of the number of plates
8 const prefixSum: number[] = new Array(n + 1).fill(0);
9
10 // Calculating the prefix sum for the plates
11 for (let i = 0; i < n; ++i) {
12 prefixSum[i + 1] = prefixSum[i] + (s[i] === '*' ? 1 : 0);
13 }
14
15 // Arrays to store the nearest left and right candle positions
16 const nearestLeftCandle: number[] = new Array(n);
17 const nearestRightCandle: number[] = new Array(n);
18
19 // Find the nearest left candle for each position
20 let lastCandleIndex: number = -1;
21 for (let i = 0; i < n; ++i) {
22 if (s[i] === '|') lastCandleIndex = i;
23 nearestLeftCandle[i] = lastCandleIndex;
24 }
25
26 // Find the nearest right candle for each position
27 let nextCandleIndex: number = -1;
28 for (let i = n - 1; i >= 0; --i) {
29 if (s[i] === '|') nextCandleIndex = i;
30 nearestRightCandle[i] = nextCandleIndex;
31 }
32
33 // Answer array to store the result for each query
34 const answer: number[] = new Array(queries.length);
35
36 // Process each query
37 for (let k = 0; k < queries.length; ++k) {
38 // Find the nearest right candle from the start index of the query
39 const startCandleIndex: number = nearestRightCandle[queries[k][0]];
40 // Find the nearest left candle from the end index of the query
41 const endCandleIndex: number = nearestLeftCandle[queries[k][1]];
42
43 // If both candles are valid and the start candle is to the left of the end candle
44 if (startCandleIndex !== -1 && endCandleIndex !== -1 && startCandleIndex < endCandleIndex) {
45 // Calculate the number of plates between candles and store it in the answer
46 answer[k] = prefixSum[endCandleIndex] - prefixSum[startCandleIndex + 1];
47 }
48 // In case there is no valid segment of plates between candles, the result is 0
49 else {
50 answer[k] = 0;
51 }
52 }
53
54 return answer;
55}
56
Time and Space Complexity
The given Python code defines a method platesBetweenCandles
to calculate the number of plates between candles for a series of queries.
Time Complexity:
Let's break it down step by step:
- We first compute the prefix sum array
presum
, which takesO(n)
time, wheren
is the length of the strings
. - Then we create two arrays
left
andright
that store the index of the nearest left and right candle for each position in the string. Building these arrays takesO(n)
time each since we iterate over all elements from left to right and right to left, respectively. - Finally, we iterate over all the queries. For each query, it takes
O(1)
time to compute the answer using the prefix sums and theleft
andright
arrays. Since there areq
queries, this step takesO(q)
time in total.
Therefore, the overall time complexity of the code is O(n) + O(n) + O(q) = O(n + q)
.
Space Complexity:
- We use
O(n)
space for the prefix sum arraypresum
of sizen + 1
. - We also use
O(n)
space for each of theleft
andright
arrays. - Finally, the space for output
ans
isO(q)
whereq
is the number of queries.
Therefore, the total space used is O(n) + O(n) + O(n) + O(q) = O(n + q)
.
In conclusion, the time complexity of the code is O(n + q)
, and the space complexity is O(n + q)
, where n
is the length of the string and q
is the number of queries.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we