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 to i if s[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 to i if s[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 using right[l] and the closest candle to the left of r using left[r]. Let's refer to these positions as i and j, respectively.
  • We then check if i and j form a valid boundary ā€” that is, if i is before j. 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 Evaluator

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

  1. 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] equals left[5], there are no valid boundaries within this substring, so the result for this query is 0.
  2. 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 equals 3 - 1 = 2. There are 2 plates between the candles at positions 2 and 6.

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:

  1. We first compute the prefix sum array presum, which takes O(n) time, where n is the length of the string s.
  2. Then we create two arrays left and right that store the index of the nearest left and right candle for each position in the string. Building these arrays takes O(n) time each since we iterate over all elements from left to right and right to left, respectively.
  3. Finally, we iterate over all the queries. For each query, it takes O(1) time to compute the answer using the prefix sums and the left and right arrays. Since there are q queries, this step takes O(q) time in total.

Therefore, the overall time complexity of the code is O(n) + O(n) + O(q) = O(n + q).

Space Complexity:

  1. We use O(n) space for the prefix sum array presum of size n + 1.
  2. We also use O(n) space for each of the left and right arrays.
  3. Finally, the space for output ans is O(q) where q 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings