[Solved] Output largest element on the right for each element in an Array

by


Here’s an example of how to do it. The idea is to iterate through your array, then look at every element after the one you’re currently looking at until you find one that is greater. The greater element (or -1 by default) is pushed into a second array for storage.

var Arr1 = [4, 6, 3, 9, 11, 5];
var Arr2 = [];
for (var i=0;i<Arr1.length;i++) {
    var biggerNumber = -1;
    for (var j=i+1;j<Arr1.length;j++) {
        if (Arr1[j]>Arr1[i]) {
            biggerNumber = Arr1[j];
            break;
        }
    }
    Arr2.push(biggerNumber);
}
//output: 
for(var i=0;i<Arr1.length;i++) {
    console.log(Arr1[i]+" -- "+Arr2[i]);
}

Updated answer: 

var Arr1 = [4, 6, 3, 9, 11, 5];
var stack=[];
Arr1.forEach(function(i){
    if (stack.length==0 || i<=stack[stack.length-1]) {
        stack.push(i);
    } else {
        while(stack.length>0 && i>stack[stack.length-1]) {
            console.log(i);
            stack.pop();
        }
        stack.push(i);
    }
});
stack.forEach(function(){console.log(-1);});

Why it’s better: The inner loop performs Arr1.length operations total, so it’s still running in O(n). How to implement that without nested loops I still have no idea.

6

solved Output largest element on the right for each element in an Array