Leetcode 2055: Plates Between Candles
You are tasked with processing a string of plates (’*’) and candles (’|’) arranged on a table. For a set of queries, you must determine the number of plates that are enclosed by candles within specified substrings of the string.
Problem
Approach
Steps
Complexity
Input: The input consists of a string `s` containing only '*' and '|' characters and a list of queries, where each query specifies a substring using two indices.
Example: Input: s = "|*|*|**|", queries = [[1, 5], [3, 7]]
Constraints:
• 3 <= s.length <= 10^5
• s consists of '*' and '|' characters.
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= lefti <= righti < s.length
Output: For each query, return the number of plates between candles in the specified substring.
Example: Output: [1, 2]
Constraints:
• The result is an integer array where each element corresponds to a query.
Goal: Determine the number of plates between candles for each query by preprocessing the input for efficient computation.
Steps:
• Preprocess the string to identify the nearest candles to the left and right of each index.
• Compute the cumulative count of plates encountered up to each index.
• For each query, use the preprocessed data to calculate the number of plates enclosed by candles.
Goal: Ensure the solution adheres to the input size and computational efficiency requirements.
Steps:
• The solution must handle up to 10^5 queries efficiently.
• String processing should be optimized for O(n) complexity.
Assumptions:
• Each substring query will always be within the bounds of the string.
• A valid candle must enclose plates on both sides within a query range.
• Input: s = "|**|**|*", queries = [[2, 7], [0, 8]]
• Explanation: For query [2, 7], the substring is "**|**|", and the number of plates between candles is 2. For query [0, 8], the substring is "|**|**|*", and the number of plates between candles is 4.
Approach: Preprocess the string for efficient query resolution using arrays to store nearest candles and cumulative plate counts.
Observations:
• Plates must be enclosed by candles to be counted.
• Processing the string for every query would be computationally expensive.
• Use prefix sums and nearest candle positions for efficient computation.
Steps:
• Traverse the string to compute the nearest left and right candles for each index.
• Calculate a cumulative count of plates as a prefix sum array.
• For each query, determine the bounds of the substring using nearest candle indices.
• Compute the number of plates between the candles using the prefix sum array.
Empty Inputs:
• An empty string or query list should return an empty result.
Large Inputs:
• Handle strings with maximum length and maximum number of queries efficiently.
Special Values:
• All plates or all candles should result in zero plates between candles for any query.
Constraints:
• Ensure indices in queries are within bounds.
vector<int> platesBetweenCandles(string s, vector<vector<int>>& q) {
int n = s.length();
vector<int> left(n, 0), right(n, 0), count(n, 0), ans(q.size(), 0);
int node = -1;
int cnt = 0;
for(int i = 0; i < n; i++) {
if(s[i] == '|') {
node = i;
cnt++;
}
left[i] = node;
count[i] = cnt;
}
node = -1;
for(int i = n - 1; i >= 0; i--) {
if(s[i] == '|'){
node = i;
}
right[i] = node;
}
int idx = 0;
for(vector<int> qr : q) {
int r = left[qr[1]];
int l = right[qr[0]];
// int c = count[r] - count[l] + 1;
if (r == -1 || l == -1 || r - l <= 1) {
ans[idx] = 0;
} else {
int c = count[r] - count[l] +1;
ans[idx] = r - l + 1 - c;
}
idx++;
}
return ans;
}
1 : Main Function Declaration
vector<int> platesBetweenCandles(string s, vector<vector<int>>& q) {
Declare the main function 'platesBetweenCandles' that takes a string 's' representing plates and candles, and a vector 'q' representing queries. It returns a vector of integers indicating the number of plates between candles for each query.
2 : Variable Declaration
int n = s.length();
Declare a variable 'n' to store the length of the input string 's'.
3 : Variable Declaration
vector<int> left(n, 0), right(n, 0), count(n, 0), ans(q.size(), 0);
Declare vectors 'left', 'right', 'count', and 'ans' to store the leftmost candle position, rightmost candle position, the count of plates up to each position, and the answers for each query.
4 : Variable Initialization
int node = -1;
Initialize 'node' to -1, which will be used to track the position of candles during the processing.
5 : Variable Initialization
int cnt = 0;
Initialize 'cnt' to 0, which will be used to count the number of plates encountered so far.
6 : For Loop
for(int i = 0; i < n; i++) {
Start a loop to process the input string 's' from left to right.
7 : If Statement
if(s[i] == '|') {
Check if the current character is a candle ('|').
8 : Variable Update
node = i;
Update the 'node' to the current position, as it now represents a candle.
9 : Counter Update
cnt++;
Increment the 'cnt' variable as a candle is found.
10 : Vector Update
left[i] = node;
Store the position of the last encountered candle in the 'left' vector.
11 : Vector Update
count[i] = cnt;
Store the cumulative count of plates encountered so far in the 'count' vector.
12 : Variable Update
node = -1;
Reset the 'node' variable to -1 in preparation for the second pass of the string.
13 : For Loop
for(int i = n - 1; i >= 0; i--) {
Start a loop to process the input string 's' from right to left.
14 : If Statement
if(s[i] == '|'){
Check if the current character is a candle ('|').
15 : Variable Update
node = i;
Update the 'node' to the current position as it represents a candle.
16 : Vector Update
right[i] = node;
Store the position of the last encountered candle in the 'right' vector.
17 : Variable Declaration
int idx = 0;
Declare an index 'idx' to track the current query in the queries list.
18 : For Loop
for(vector<int> qr : q) {
Start a loop to process each query in the 'q' vector.
19 : Query Calculation
int r = left[qr[1]];
Get the position of the leftmost candle on the right side of the query range.
20 : Query Calculation
int l = right[qr[0]];
Get the position of the rightmost candle on the left side of the query range.
21 : If Condition
if (r == -1 || l == -1 || r - l <= 1) {
Check if the range is invalid (either no candles found or the range is too small).
22 : Answer Update
ans[idx] = 0;
Set the answer for the query to 0 if the range is invalid.
23 : Else Block
} else {
If the range is valid, proceed to calculate the number of plates.
24 : Answer Calculation
int c = count[r] - count[l] +1;
ans[idx] = r - l + 1 - c;
Calculate the number of plates between candles by subtracting the count of plates in the range from the total number of positions in the range.
25 : Return Statement
return ans;
Return the vector containing the answers for all the queries.
Best Case: O(n + q)
Average Case: O(n + q)
Worst Case: O(n + q)
Description: Preprocessing takes O(n), and each query is resolved in O(1) for a total of O(n + q).
Best Case: O(n)
Worst Case: O(n)
Description: Additional arrays for nearest candles and cumulative plate counts require O(n) space.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus