Plates Between Candles - Practice Coding Problems

Plates Between Candles - Problem

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] = [lefti, righti] denotes the substring s[lefti...righti] (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 ith query.

Input & Output

Example 1 — Basic Case

$ Input: s = "**|**|***|", queries = [[2,5],[5,9]]

› Output: [2,3]

💡 Note: Query [2,5]: substring is "|**|", plates at indices 3,4 are between candles at 2,5. Query [5,9]: substring is "|***|", plates at indices 6,7,8 are between candles at 5,9.

Example 2 — No Candles

$ Input: s = "***", queries = [[0,2]]

› Output: [0]

💡 Note: Query [0,2]: substring is "***", no candles exist so no plates can be between candles.

Example 3 — Single Candle

$ Input: s = "|**|", queries = [[0,3]]

› Output: [2]

💡 Note: Query [0,3]: substring is "|**|", plates at indices 1,2 are between candles at 0,3.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

String of plates (*) and candles (|) with query ranges

Process

For each query, find plates between leftmost and rightmost candles

Output

Array of plate counts for each query

Key Takeaway

🎯 Key Insight: Only plates between the first and last candle in a range count as 'between candles'

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that only plates between the leftmost and rightmost candles in a query range can be "between candles". Best approach uses prefix sums with precomputation to answer queries in O(1) time after O(n) preprocessing. Time: O(n + q), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum with Precomputation	O(n + q)	O(n)	Precompute nearest candles and plate counts for O(1) query answering
Brute Force	O(q × n²)	O(1)	For each query, scan the substring to find plates with candles on both sides

Prefix Sum with Precomputation — Algorithm Steps

Precompute nearest left candle for each position
Precompute nearest right candle for each position
Build prefix sum array for plates
For each query, find boundary candles and calculate plate count

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute

Build nearest left/right candle arrays and plate prefix sums

Find Boundaries

For each query, find leftmost and rightmost candles in range

Count Plates

Use prefix sum to count plates between boundary candles

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(char* s, int** queries, int queriesSize, int* returnSize) {
    *returnSize = queriesSize;
    int* result = (int*)malloc(queriesSize * sizeof(int));
    int n = strlen(s);
    
    // Precompute nearest left candle for each position
    int* nearestLeft = (int*)malloc(n * sizeof(int));
    int lastCandle = -1;
    for (int i = 0; i < n; i++) {
        if (s[i] == '|') {
            lastCandle = i;
        }
        nearestLeft[i] = lastCandle;
    }
    
    // Precompute nearest right candle for each position
    int* nearestRight = (int*)malloc(n * sizeof(int));
    lastCandle = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '|') {
            lastCandle = i;
        }
        nearestRight[i] = lastCandle;
    }
    
    // Build prefix sum for plates
    int* platesPrefix = (int*)malloc((n + 1) * sizeof(int));
    platesPrefix[0] = 0;
    for (int i = 0; i < n; i++) {
        platesPrefix[i + 1] = platesPrefix[i] + (s[i] == '*' ? 1 : 0);
    }
    
    for (int q = 0; q < queriesSize; q++) {
        int left = queries[q][0], right = queries[q][1];
        
        // Find leftmost candle in range
        int leftmostCandle = nearestRight[left];
        if (leftmostCandle == -1 || leftmostCandle > right) {
            result[q] = 0;
            continue;
        }
        
        // Find rightmost candle in range
        int rightmostCandle = nearestLeft[right];
        if (rightmostCandle == -1 || rightmostCandle < left) {
            result[q] = 0;
            continue;
        }
        
        // Count plates between leftmost and rightmost candles
        if (leftmostCandle >= rightmostCandle) {
            result[q] = 0;
        } else {
            int platesCount = platesPrefix[rightmostCandle] - platesPrefix[leftmostCandle + 1];
            result[q] = platesCount;
        }
    }
    
    free(nearestLeft);
    free(nearestRight);
    free(platesPrefix);
    
    return result;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char line[1000000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Simple parsing for queries
    int** queries = NULL;
    int queriesSize = 0;
    
    // Count queries first
    for (int i = 0; line[i]; i++) {
        if (line[i] == '[' && i > 0) queriesSize++;
    }
    
    queries = (int**)malloc(queriesSize * sizeof(int*));
    for (int i = 0; i < queriesSize; i++) {
        queries[i] = (int*)malloc(2 * sizeof(int));
    }
    
    // Parse queries
    int idx = 0;
    char* token = strtok(line + 1, "[");
    while (token && idx < queriesSize) {
        sscanf(token, "%d,%d", &queries[idx][0], &queries[idx][1]);
        idx++;
        token = strtok(NULL, "[");
    }
    
    int returnSize;
    int* result = solution(s, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    for (int i = 0; i < queriesSize; i++) free(queries[i]);
    free(queries);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + q)

O(n) preprocessing to build arrays plus O(1) for each of q queries

✓ Linear Growth

Space Complexity

O(n)

Three arrays of size n for nearest candles and prefix sums

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum with Precomputation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler