Plates Between Candles

Medium

Asked by:

53 views

Topics:

ArraysStringsTwo Pointers

There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters '*' and '|' only, where a '*' represents a plate and a '|' represents a candle.

You are also given a 0-indexed 2D integer array queries where queries[i] = [left_i, right_i] denotes the substring s[left_i...right_i] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.

For example, s = "||**||**|*", and a query [3, 8] denotes the substring "*||**|". The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.

Return an integer array answer where answer[i] is the answer to the i^th query.

Example 1:

Input: s = "**|**|***|", queries = [[2,5],[5,9]]
Output: [2,3]
Explanation:
- queries[0] has two plates between candles.
- queries[1] has three plates between candles.

Example 2:

Input: s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
Output: [9,0,0,0,0]
Explanation:
- queries[0] has nine plates between candles.
- The other queries have zero plates between candles.

Constraints:

3 <= s.length <= 10⁵
s consists of '*' and '|' characters.
1 <= queries.length <= 10⁵
queries[i].length == 2
0 <= left_i <= right_i < s.length

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the string `s` and the number of queries in the `queries` array? Are there any constraints on the values within the `queries`?
Can the string `s` be empty or contain characters other than '*' and '|'?
If a query range doesn't contain any candles, or contains no plates between any candles, what should the result be?
Are the query ranges in the `queries` array guaranteed to be valid (i.e., start index less than or equal to end index and within the bounds of the string length)?
If multiple candles are adjacent, how do we determine the 'nearest' candle for counting the plates in between?

Brute Force Solution

Approach

The brute force method is like counting everything one-by-one to get the answer. For this problem, we examine every possible section between two points and check if it fits our needs.

Here's how the algorithm would work step-by-step:

For each query, examine every possible segment within the given range.
For each segment, count the number of plates between the two candles that define the segment.
Save the count of plates for each segment.
After checking every segment, return the saved count of plates for that particular query.

Code Implementation

def platesBetweenCandlesBruteForce(stringInput, queries):
    results = []
    for query in queries:
        start = query[0]
        end = query[1]
        queryResult = 0

        # Iterate through all possible segments within the query range
        for segmentStart in range(start, end + 1):
            for segmentEnd in range(segmentStart, end + 1):

                # Find the leftmost candle in the segment
                leftCandle = -1
                for index in range(segmentStart, segmentEnd + 1):
                    if stringInput[index] == '|':
                        leftCandle = index
                        break

                # Find the rightmost candle in the segment
                rightCandle = -1
                for index in range(segmentEnd, segmentStart - 1, -1):
                    if stringInput[index] == '|':
                        rightCandle = index
                        break

                # Check if two candles were found in this segment
                if leftCandle != -1 and rightCandle != -1 and leftCandle < rightCandle:

                    # Count the plates between the candles
                    plateCount = 0
                    for index in range(leftCandle + 1, rightCandle):
                        if stringInput[index] == '*':
                            plateCount += 1

                    # Add the plates between candles to running total
                    queryResult += plateCount

        results.append(queryResult)

    return results

Big(O) Analysis

Time Complexity

O(n*m*q) – The brute force solution iterates through each query. For each query, it examines every possible segment within the range defined by the query. Assume the size of the string s is n, and m is the maximum range size in the queries array. This can require examining m * m possible segments. For each segment, the algorithm counts the number of plates, which takes O(n) time in worst case. Since there can be q queries the final time complexity is O(q*m*m*n). However we can consider that worst case m is n and thus the complexity can also be interpreted as O(q*n^3). Given the original prompt mentions checking of every possible segment between two points, then we can assume that we need to iterate over the array to check for plates. Given the constraint that for each segment, we count the number of plates, we get the time complexity of O(n*m*q).

Space Complexity

O(1) – The brute force method, as described, examines segments within each query range and counts plates. It saves the count of plates for each segment within the range of the query. The algorithm does not appear to use any auxiliary data structures that scale with the input string length (N) or the number of queries. Only constant space is used for storing variables like counters and the segment's plate count. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The problem asks us to count the number of items between candles in specific sections of a row. The efficient solution avoids recounting items by precalculating helpful information to quickly answer each count request.

Here's how the algorithm would work step-by-step:

First, scan the entire row once to find the location of every candle. Keep this information handy.
Next, for every position in the row, calculate and store the position of the nearest candle to the left. Similarly, calculate and store the position of the nearest candle to the right.
Now, when we get a request to count items between candles in a given section, use the pre-calculated candle positions.
Find the nearest candle to the right of the start of the section and the nearest candle to the left of the end of the section.
If the candle on the right of the start appears before the candle to the left of the end, we can calculate the number of items between those candles using the information stored in the beginning.
If the candles do not appear in the correct order, that section doesn't contain any items between valid candles, so the answer for this section is zero.

Code Implementation

def plates_between_candles(s, queries):
    number_of_positions = len(s)
    candle_positions = []

    for i in range(number_of_positions):
        if s[i] == '|':
            candle_positions.append(i)

    nearest_left = [0] * number_of_positions
    nearest_right = [0] * number_of_positions

    left_candle_position = -1
    for i in range(number_of_positions):
        if s[i] == '|':
            left_candle_position = i
        nearest_left[i] = left_candle_position

    right_candle_position = -1
    for i in range(number_of_positions - 1, -1, -1):
        if s[i] == '|':
            right_candle_position = i
        nearest_right[i] = right_candle_position

    result = []
    for start, end in queries:
        # Find the bounding candles for the range
        left_bounding_candle = nearest_right[start]
        right_bounding_candle = nearest_left[end]

        # Ensure the candles are in the correct order
        if left_bounding_candle == -1 or right_bounding_candle == -1 or left_bounding_candle >= right_bounding_candle:
            result.append(0)
        else:
            # Count the plates between the bounding candles.
            count = 0
            for i in range(left_bounding_candle + 1, right_bounding_candle):
                if s[i] == '*':
                    count += 1
            result.append(count)

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm first scans the row of size n to find all candle positions, which takes O(n) time. Then, it calculates the nearest candle to the left and right for each position in the row, also taking O(n) time. For each query, it finds the nearest candles and calculates the number of items between them, which takes constant time, O(1). Since there can be multiple queries, say q queries, these operations take O(q) time. Therefore, the overall time complexity is O(n) + O(n) + O(q) which simplifies to O(n+q). If the number of queries, q, is less than or equal to n, then the time complexity is O(n). If the number of queries is greater than n, the time complexity becomes O(q).

Space Complexity

O(N) – The solution uses auxiliary space to store the indices of all candles in the row, the nearest candle to the left for each position, and the nearest candle to the right for each position. This results in three arrays, each of size N, where N is the length of the input row. Therefore, the auxiliary space required is proportional to the input size N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty string s or empty queries array	Return an empty list if either input is empty as no calculations can be performed.
String s contains no candles ('\|')	Return a list of zeros with the same length as queries, as there are no candles to calculate plates between.
String s contains only plates ('*')	Return a list of zeros with the same length as queries, as there are no candles to bound the plates.
A query range contains no candles	The number of plates in this case is zero, so return 0 for this specific query.
Large input string (close to maximum allowed size) and large number of queries	Precompute the nearest left and right candle positions to avoid repeated scans within the queries and ensure time complexity is efficient.
Queries with overlapping or identical ranges	Each query is independent so overlapping or identical ranges do not change the algorithm's logic, simply the same computation being repeated multiple times.
String starts or ends with many plates	Precompute the left and right nearest candles to handle these leading/trailing plates and include them when the query range intersects the valid candle range.
Integer overflow when calculating the number of plates between candles in very long strings	Use a data type that can accommodate the largest possible number of plates, such as long or long long.

Empty string s or empty queries array

How to Handle:

Return an empty list if either input is empty as no calculations can be performed.

String s contains no candles ('|')

How to Handle:

Return a list of zeros with the same length as queries, as there are no candles to calculate plates between.

String s contains only plates ('*')

How to Handle:

Return a list of zeros with the same length as queries, as there are no candles to bound the plates.

A query range contains no candles

How to Handle:

The number of plates in this case is zero, so return 0 for this specific query.

Large input string (close to maximum allowed size) and large number of queries

How to Handle:

Precompute the nearest left and right candle positions to avoid repeated scans within the queries and ensure time complexity is efficient.

Queries with overlapping or identical ranges

How to Handle:

Each query is independent so overlapping or identical ranges do not change the algorithm's logic, simply the same computation being repeated multiple times.

String starts or ends with many plates

How to Handle:

Precompute the left and right nearest candles to handle these leading/trailing plates and include them when the query range intersects the valid candle range.

Integer overflow when calculating the number of plates between candles in very long strings

How to Handle:

Use a data type that can accommodate the largest possible number of plates, such as long or long long.