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.

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

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.