Skip to main content

Monk and prisoner of azkaban (application of stack data structure)

As mysterious it may sound, this is a problem in Hacker-earth practice problems under data structure criteria. The problem statement is as below:
The problem is given an array A having N integers, for each i(1≤i≤N), find x+y, where x is the largest number less than i such that A[x]>A[i] and y is the smallest number greater than i such that A[y]>A[i]. If there is no x<i such that A[x]>A[i], then take x=−1. Similarly, if there is no y>i such that A[y]>A[i], then take y=−1.
Input Format:
First line consists of a single integer denoting N.
Second line consists of N space separated integers denoting the array A.
Output Format:
Print N space separated integers, denoting x+y for each i(1≤i≤N)
Constraints:
1≤N≤10⁶
1≤A[i]≤10¹⁸
This problem was set by vaibhab jamini and was tested by prateek garg. It also appeared on a hacker-earth challenge named codemonk with some other data structure related problems.
Discussion:
So first of all, in someone’s mind, a very easy algorithm will pop up which is that parse through the array and for each array element, find the x and y and then we are done. Finding the x and y in this way is a easy way. But as soon as you write this, you understand that, this algorithm is O(n²) order algorithm and therefore it will give you a time limit when the constraint is as high as 10⁶.
This happens too. On writing the following C code, I have got 3 cases solved and other inputs provide a “time limit exceeded” notice. This means that you need a better algorithm.
Here, I mention my naive method for referral.
#include <stdio.h>
int main()
{ int N;int i; int j;
 scanf(“%d”,&N);
 long long *A=(long long *)calloc(N+2,sizeof(long long));
 long long *B=(long long *)calloc(N+2,sizeof(long long));
 for(i=0;i<N;i++)
 {
 scanf(“%lld”,&A[i]);
 }
 for(i=0;i<N;i++)
 {
 int x=-1; int y=-1;
 for(j=i-1;j>-1;j — )
 {
 if(A[j]>A[i])
 {
 x=j+1;
 break;
 }
 }
 for(j=i+1;j<N;j++)
 {
 if(A[j]>A[i])
 {
 y=j+1;
 break;
 }
 }
 B[i]=x
 B[i+1]=i;
 B[i+2]=y;
 printf(“%d “,B[i]);
 }

}
Now, I start to search for a better algorithm. Now as it seems, it is a variation problem of a so called “stock span problem” in which one is given an array of par day stock price and is supposed to find the number of days for which the stock price was less than that day’s price. This question is solved using a stack implementation. Statement of the stock span problem can be found here. Also, if you want to know what a stack is or want to take a casual look at a sample code, please look here
First one takes i. Then one finds the index h(i) which denotes the maximum index less than i such that A[h(i)]>A[i]. Then one saves the i,h(i),h(h(i)).. in a stack. Now, when one goes from i to i+1, then,
if A[i+1]<A[i], then x=i; else A[i+1]>A[i], so the stack can directly provide the next best solution for this as the previous element greater than A[i] is the previous element in the stack. So, we basically do the following:
(a)we create the stock from right i=0. We save h(0).
(b) In each step, i, we compare the top of the stack and A[i]. We pop until top>A[i]. Then we push i. If the stack becomes empty, then we push i as the first node and the required x for i becomes -1.
This algorithm clearly gives a better solution. The code of this is not added to the post to just leave a little work for the readers. Also, better algorithms can be thought for the same problem.
So, this was my take of the problem,comment to let me know what you think of the problem.

Comments

Popular posts from this blog

Mastering SQL for Data Science: Top SQL Interview Questions by Experience Level

Introduction: SQL (Structured Query Language) is a cornerstone of data manipulation and querying in data science. SQL technical rounds are designed to assess a candidate’s ability to work with databases, retrieve, and manipulate data efficiently. This guide provides a comprehensive list of SQL interview questions segmented by experience level—beginner, intermediate, and experienced. For each level, you'll find key questions designed to evaluate the candidate’s proficiency in SQL and their ability to solve data-related problems. The difficulty increases as the experience level rises, and the final section will guide you on how to prepare effectively for these rounds. Beginner (0-2 Years of Experience) At this stage, candidates are expected to know the basics of SQL, common commands, and elementary data manipulation. What is SQL? Explain its importance in data science. Hint: Think about querying, relational databases, and data manipulation. What is the difference between WHERE ...

Spacy errors and their solutions

 Introduction: There are a bunch of errors in spacy, which never makes sense until you get to the depth of it. In this post, we will analyze the attribute error E046 and why it occurs. (1) AttributeError: [E046] Can't retrieve unregistered extension attribute 'tag_name'. Did you forget to call the set_extension method? Let's first understand what the error means on superficial level. There is a tag_name extension in your code. i.e. from a doc object, probably you are calling doc._.tag_name. But spacy suggests to you that probably you forgot to call the set_extension method. So what to do from here? The problem in hand is that your extension is not created where it should have been created. Now in general this means that your pipeline is incorrect at some level.  So how should you solve it? Look into the pipeline of your spacy language object. Chances are that the pipeline component which creates the extension is not included in the pipeline. To check the pipe eleme...

20 Must-Know Math Puzzles for Data Science Interviews: Test Your Problem-Solving Skills

Introduction:   When preparing for a data science interview, brushing up on your coding and statistical knowledge is crucial—but math puzzles also play a significant role. Many interviewers use puzzles to assess how candidates approach complex problems, test their logical reasoning, and gauge their problem-solving efficiency. These puzzles are often designed to test not only your knowledge of math but also your ability to think critically and creatively. Here, we've compiled 20 challenging yet exciting math puzzles to help you prepare for data science interviews. We’ll walk you through each puzzle, followed by an explanation of the solution. 1. The Missing Dollar Puzzle Puzzle: Three friends check into a hotel room that costs $30. They each contribute $10. Later, the hotel realizes there was an error and the room actually costs $25. The hotel gives $5 back to the bellboy to return to the friends, but the bellboy, being dishonest, pockets $2 and gives $1 back to each friend. No...