1.
Question
2.
Solution
3.
Key takeaways
Last Updated: Mar 27, 2024

# Plates Between Candles

GAZAL ARORA
0 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

## Question

There is a long table with plates and candles placed in a line on the top of it. You're given a 0-indexed string s that only contains the letters'*' and '|,' with a '*' representing a plate and a '|' representing a candle.

In addition, you are given a 0-indexed 2D integer array queries, where queries[i] = [lefti, righti] signifies the substring s[lefti...righti] (inclusive).

You have to count the number of plates between candles in each substring for each query. If the given substring contains at least one candle to its left and one to its right, the plate is considered between candles.

Alert Ninjas:  Donâ€™t stop now! Enroll in the Competitive Programming course today and start coding. Learn the art of writing time and space-efficient code and compete in code competitions worldwide.

Input:   A string s, a vector of strings of queries.

Example 1

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

Output: [2,3]

Explanation:

-There are two plates between candles in queries[0].

-There are three plates between candles in queries[1].

Example 2

Input: s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11]]

Output: [9,0,0,0]

Explanation:

- There are nine plates between candles in queries[0].

- There are no plates between candles in the remaining queries.

## Solution

Observation:

This problem requires us to find a sum between a range that should immediately hint prefix sum. This will result in the constant time calculation of a query.

Idea:

The idea is to find the closest candles at the boundary that get us in the range for each query. This means we need to find the nearest left candle of the leftmost index and the nearest right candle of the rightmost index. And return the number of plates between these leftmost and rightmost candles.

We maintained three arrays prev, next, and preSum:

• prev[i] will store the nearest left candle.
• next[i] will store the nearest right candle.
• preSum[i] will store the number of plates up to index i.

C++

Time Complexity: O(N+Q)

Space Complexity: O(N)

Also check out - Substr C++ and  Rabin Karp Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Key takeaways

Here we solved a medium leveled programming question using Dynamic Programming. Join this Master Class on DP by Coding Ninjas and become a Ninja coder.

We solved it in O(N) space complexity. Can you further reduce the space complexity?

Start coding today, practice more Data Structures and Algorithms problems.