Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
This is to find the next biggest element index for each given elements.
Very simple BT approach :
/* Brute force approach */
int* dailyTemperatures(int* tempr, int tsz, int* retsz){
int *res, jj;
bool match;
*retsz = tsz;
if (!tsz)
return NULL;
res = (int *)calloc(tsz, sizeof(int));
// TODO malloc check
for (int ii=0; ii< tsz; ii++){
match = 0;
for (jj=ii+1; jj <tsz; jj++){
if (tempr[ii] < tempr[jj]){ match =1;
break;}
}
if (match)
res[ii] = jj-ii;
}
return res;
}This BT approach is extra time complexity of O(n*n).
This time complexity reduced by using stack or traversal from back side. I learned these concepts and solutions and understood, but not my own.
Monotonic stack
Monotonic stack is the concept where the elements in stack are always in sorted order.
Problem is to find next biggest number. So if the next number is not bigger, add to stack, else set the ans index to 1.
We should pop these elements in cases where we find the next biggest element and the top element of stack is smaller than the biggest element.
Pop till this condition is met.
This monotonic stack is suggested approach when comparison of numbers are involved.
This stack helps to reduce traversals.
C solution using this monotonic stack concept :
struct stknode{
int val;
};struct stk{
struct stknode *stk_ar;
int curidx;
int stksz;// current stk allocated size
};#define STK_INIT_SIZE 100struct stk *stk_create(int size){
struct stk *stkp;
stkp = (struct stk *)calloc(1, sizeof(struct stk));
stkp->stk_ar = (struct stknode *)calloc(size, sizeof(struct stknode));
stkp->stksz = size;
return stkp;
}int stk_push(struct stk *s, int val){
if (s->curidx >= s->stksz){
s->stksz += STK_INIT_SIZE;
s->stk_ar = (struct stknode *)realloc(s->stk_ar, s->stksz*sizeof(struct stknode));
}
s->stk_ar[s->curidx].val = val;
s->curidx++;
return 0;
}int stk_pop(struct stk *s){
if (!s->curidx)
return -1;
s->curidx--;
return (s->stk_ar[s->curidx].val);
}int stk_empty(struct stk *s){
return (!(s->curidx));
}
int stk_top(struct stk *s){
if (s->curidx)
return(s->stk_ar[s->curidx-1].val);
return -1;
}
int* dailyTemperatures(int* tempr, int tsz, int* retsz){
int *res, jj;
bool match;
struct stk *monstk;
*retsz = tsz;
if (!tsz)
return NULL;
monstk = stk_create(STK_INIT_SIZE);
res = (int *)calloc(tsz, sizeof(int));
// TODO malloc check
for (int ii=0; ii<tsz-1; ii++){
if (tempr[ii] >= tempr[ii+1]) {
/* push to stack */
stk_push(monstk, ii); continue; }
/* else set to 1 and check if any stack elements */
res[ii] =1;
while (!stk_empty(monstk)){
jj = stk_top(monstk);
if (tempr[jj] < tempr[ii+1]){
jj = stk_pop(monstk);
res[jj] = ii+1-jj;
}else break;
}
}
return res;
}
This solution is faster compared to brute force, but memory it takes is more.
Another approach is traversal from back and use already found data wherever applicable.
No stack required and it also might reduce some traversals.
This is good concept.
Below is the solution with explanation:
/* here the problem is to check for the next warmest day
that is to check for the next biggest value.
when traversing from reverse,
this data can be utilised to check for the next bigger values of previous elements in array.
logic is :
allocate a result indices array and initialize to 0
initialise the max-val with the least value
traverse from n-1 to 0 elements :
if a[ii] is greater than max-val, assign it
else
-there is bigger value than current one
- check for next element,
if its next result index, and so on
ind =1
while (a[ii+ind]<=a[ii]) ind += res-ind[ii+ind]
end
eg.
23,34,45,21,19,22,46,13
max-val = 13 answer index for it will be 0.
next is 46,max-val= 46.answer index for it will be 0.
next is 22(index 5) , index , less than max-val
set the next index(ni) as 1 ,
check while the a[5+ni] <=a[5]
ni += ans[5+ni]
this addition of ni += ans[5+ni] will try to avoid linear traversal whereever possible.
Due to this logic (adding of ans[n+ni]), time complexity and space complexity is reduced.
*/
int* dailyTemperatures(int* tempr, int tsz, int* retsz){
int *res, jj, max_val =0;
*retsz = tsz;
if (!tsz)
return NULL;
res = (int *)calloc(tsz, sizeof(int));
for (int ii = tsz-1; ii>=0; ii--){
if (tempr[ii] >= max_val)
{ max_val = tempr[ii]; continue;}
jj= 1;
while (tempr[jj+ii]<=tempr[ii]) {
jj += res[jj+ii];
}
res[ii] = jj;
}
return res;
}Any other approaches if you know, please comment.
