Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Question
2.
Solution
3.
Key takeaways
Last Updated: Mar 27, 2024

Plates Between Candles

Author 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.

Output: Return an answer array where answer[i] is the answer to the ith query.

 

Example 1

ex-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.

 

 


 

 

Recommended: Please try to solve it yourself first before moving on to the solution.

 

 


 

 

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++

 

vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        
        int q = queries.size();
        int l = s.length();
        
        vector<int> ans;
        vector<int> prev(l);
        vector<int> next(l);
        vector<int> preSum(l);
        
        int p=-1, nxt = -1;
        
        // calculating prev candle up to this index.
        for(int i = 0; i < l ; i++){
            
            if(s[i] == '|'){
                p = i;
            }
            prev[i] = p;
        }
        //Calculating next candle from this index.
        
          for(int i = l-1 ;i >= 0 ; i--){
              
            if(s[i] == '|'){
                nxt = i;
            }
            next[i] = nxt;
        }
        
        int c=0;
        
        // calculating the number of stars between these indices.
        for(int i = 0; i < l ; i++){
            
            if(s[i] == '*'){
                c++;
            }
            preSum[i] = c;
        }
        
        // calculating ans.
        for(int k = 0 ; k < q ; k++){
            
            int i = queries[k][0];
            int j = queries[k][1];
            
            int right  = prev[j];// position of left candle.
            int left   = next[i];// position of right candle.
            //cout<<right<<left;
            
            if(left == -1 || right == -1 || left > right){
                ans.push_back(0);
            }
            else{
                ans.push_back(preSum[right] - preSum[left]);
            }
        }
        return ans;
    }

 

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. 

Recommended Readings:


Happy Coding!

 

Previous article
Find a Fixed Point (Value equal to Index) in a Given Array
Next article
Ceiling in a sorted array
Live masterclass