We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Plates Between Candles

Number: 2165

Difficulty: Medium

Paid? No

Companies: Amazon, Adobe

Problem Description

Given a string s consisting of plates ('*') and candles ('|'), and a list of queries where each query specifies a substring by its start and end indices, determine for each query the number of plates positioned between the leftmost and rightmost candle within that substring. A plate is "between candles" if there is at least one candle to its left and one to its right in the substring.

Key Insights

  • Precompute a prefix sum array for the count of plates.
  • Use two auxiliary arrays:
    • One to track the nearest candle on the left of every index.
    • One to track the nearest candle on the right.
  • For a query, use the right-nearest candle from the left boundary as the effective start and the left-nearest candle from the right boundary as the effective end.
  • The answer for a query is the difference between the prefix sum at the effective end and effective start, if valid.

Space and Time Complexity

Time Complexity: O(n + q) where n is the length of s and q is the number of queries. Space Complexity: O(n)

Solution

We start by computing a prefix sum array that counts the number of plates up to each position. Then, we precompute two arrays: one that stores for each index the nearest candle seen from the left, and another for the nearest candle from the right. For each query, we locate the first candle at or after the left index (using the right-candle array) and the last candle at or before the right index (using the left-candle array). If these indices are valid and the first candle comes before the last, the number of plates is the difference in their respective prefix sums. Otherwise, the answer is 0.

Code Solutions

# Python solution for Plates Between Candles problem.

def platesBetweenCandles(s, queries):
    n = len(s)
    # Create prefix sum of plates
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + (1 if s[i - 1] == '*' else 0)

    # Array to store the nearest candle to the left for each index
    left_candle = [-1] * n
    prev = -1
    for i in range(n):
        if s[i] == '|':
            prev = i
        left_candle[i] = prev

    # Array to store the nearest candle to the right for each index
    right_candle = [-1] * n
    nxt = -1
    for i in range(n - 1, -1, -1):
        if s[i] == '|':
            nxt = i
        right_candle[i] = nxt

    result = []
    for left, right in queries:
        # Find the effective candles within the query boundaries.
        first = right_candle[left]
        last = left_candle[right]
        if first != -1 and last != -1 and first < last:
            result.append(prefix[last] - prefix[first])
        else:
            result.append(0)
    return result

# Example usage.
if __name__ == "__main__":
    s = "**|**|***|"
    queries = [[2, 5], [5, 9]]
    print(platesBetweenCandles(s, queries))  # Expected output: [2, 3]
← Back to All Questions