I'm familiarizing myself with Stack and while was able to come up with a logic that took me most of the way I have a problem with few problem cases.
console.log(greaterL([56, 23, 1, 5, 18, 17]))//[-1, -1, 5, 18, -1, -1]
====> actually returns -1, 5, 18, -1, -1, -1
console.log(greaterL([70, 60, 1, 4, 8, 12, 50, 23]))//[-1,-1, 4, 8, 12, 50, -1, -1]
====> actually returns -1, 4, 8,12, 50, -1, -1, -1
function greaterL(arr){
let stack = []
let result = []
for(let i = 0; i < arr.length-1; i++){
stack.push(arr[i])
let next = arr[i+1]
while(stack.length!==0 && stack[stack.length-1] < next){
stack.pop();
result.push(next);
}
}
result.push(-1)
while(stack.length){
let value = stack.pop()
if(arr[0]===value){
result.unshift(-1)
}else{
result.push(-1)
}
}
return result
}
I know I'm very close but I cannot come up with the solution satisfying all the cases, if someone could point me out in the right direction I would be most grateful
I would loop the array from the end, it looks more natural, since we analyze the rest of the array for each array item.
Thus we can simultaneously loop and collect the stack.
So we collect values in the stack unless we find a bigger value than in the stack. In that case we just reset the stack to this value and continue loop to the beginning.
I wouldn't call the stack a stack actually in this case, since there's no need to pop/shift elements from it.
console.log(...greaterL([56, 23, 1, 5, 1, 5, 1,18, 17]))//[-1, -1, 5, 18, -1, -1]
console.log(...greaterL([70, 60, 1, 4, 8, 12, 50, 23]))//[-1,-1, 4, 8, 12, 50, -1, -1]
function greaterL(arr){
let stack = [arr[arr.length - 1]];
const result = [-1];
for(let i = arr.length - 2; i >= 0; i--){
const item = arr[i];
const found = stack.find(max => max > item);
result.unshift(found ?? -1);
found === undefined ? stack = [item] : stack.unshift(item);
}
return result;
}Regarding your stack code there's a problem when you try to put -1 for array items which don't have a next max. You should actually collect indices for those items and insert -1 at the remembered indices.
But the whole idea of using a stack seems invalid. It assumes that consecutive items will be bigger than the previous ones. Once I add more data the algorithm fails. So seems my reversed loop is the only proper option from the two.
console.log(...greaterL([56, 23, 1, 5, 1, 5, 1,18, 17]))//[-1, -1, 5, 18, -1, -1]
console.log(...greaterL([70, 60, 1, 4, 8, 12, 50, 23]))//[-1,-1, 4, 8, 12, 50, -1, -1]
function greaterL(arr){
let stack = []
let result = []
for(let i = 0; i < arr.length-1; i++){
stack.push([arr[i], i])
let next = arr[i+1]
while(stack.length!==0 && stack[stack.length-1][0] < next){
stack.pop();
result.push(next);
}
}
result.push(-1);
stack.forEach(([_, idx]) => result.splice(idx, 0, -1));
return result
}