Find The Next Bigger Number
Stacks
JavaScript
Problem:
Given an array of numbers, find the next bigger number to the right of a specified number. That is, for each number in the array, determine the next larger number that appears to its right. If no such number exists, return -1. You can assume that the array contains unique numbers.
Example:
Input Array: [5, 9, 3, 21, 18]
Input Number: 5
Output: 9
9 is the next larger number after 5.
Input Number: 9
Output: 21
In the same array, after 9, we have 3, which is not larger than 9. Therefore, we move to the next element, 21, which is larger than 9, and 21 is returned.
Input Number: 21
Output: -1
After 21, there are no numbers larger than 21 in the array.
Algorithm:
To solve this, we need to traverse the array from the end and push each element onto the stack until we encounter the reference number. Once the reference number is found, we begin popping elements from the stack and checking if each popped number is greater than the reference number.
Steps:
- Loop through the array from the end and push each element onto the stack until the reference number is encountered.
- Once the reference number is found, pop elements from the stack and compare each with the reference number.
- If a popped number is greater than the reference number, that number is the answer.
- If the stack becomes empty and no greater number is found, return -1.
Solution & Visualize:
The animation/visualization below illustrates the algorithm. Feel free to experiment with different input values.
Result
Code
Input:
Enter the array elements followed by a comma
This is the custom help text for this input
Output:
solution.js
stack.js
stack-displayer.js
animator-module.js
function stackSolution(args) {console.log(args);
let array = args[0];
let referenceNumber = args[1];
const stack = new Stack(
array,
{
name: 'Stack',
description: 'This stack holds the input array elements.'
}
);
const tempStack = new Stack(
[],
{
name: 'Temp Stack',
description: 'Temporary stack to get the compare the numbers.'
}
);
animatorModule.displayComment(
'Pop from the input stack until the reference number('+ referenceNumber +') is found.',
1000
);
let nextBiggerNumber = -1;
while (! stack.isEmpty()) {
if (stack.top() == referenceNumber) {
animatorModule.displayComment(
'The reference number('+ referenceNumber +') is found.',
1000
);
break;
}
tempStack.push(stack.pop());
}
animatorModule.displayComment(
'Now pop from the second stack and check if the popped number is bigger than reference number.',
1000
);
let topElement = '';
while (! tempStack.isEmpty()) {
topElement = tempStack.pop();
if (topElement > referenceNumber) {
animatorModule.displayComment(
'Next bigger number is found: ' + topElement,
1000
);
nextBiggerNumber = topElement;
break;
}
}
if (nextBiggerNumber == -1) {
animatorModule.displayComment(
'There is no next bigger number.',
1000
);
}
animatorModule.displayOutput(nextBiggerNumber);
return nextBiggerNumber;
}
class Stack {
metaData = {
'name': 'Stack',
'description': '',
'animation_duration': 1500,
}
constructor(initialData, metaData) {
this.initialData = [...initialData];
this.metaData = Object.assign({}, this.metaData, metaData);
this.stackDisplayer = new StackDisplayer(initialData, this.metaData);
this.stackId = this.stackDisplayer.display();
}
getStackData() {
return this.initialData;
}
push(value) {
this.initialData.push(value);
// Perform the animation
animatorModule.performPushAnimation(this.stackId, value);
}
pop() {
if (this.initialData.length == 0) return;
const value = this.initialData.pop();
// Perform the animation
animatorModule.performPopAnimation(this.stackId, value);
return value;
}
top() {
if (this.initialData.length == 0) return;
const value = this.initialData[this.initialData.length - 1];
return value;
}
isEmpty() {
return this.initialData.length === 0;
}
}
class StackDisplayer {
constructor(initialData, metaData) {
this.initialData = initialData;
this.metaData = metaData;
}
display() {
// Display stack on the screen
const stackTemplate = document.getElementById('stack-template');
const clone = stackTemplate.content.cloneNode(true);
const stackCount = document.getElementsByClassName('stack-wrapper').length + 1;
// Add an unique ID to the clone
const stackWrapperId = 'stack-' + stackCount;
const stackWrapper = clone.querySelector('.stack-wrapper');
stackWrapper.id = stackWrapperId;
// Add initial stack items
const stackElement = clone.querySelector('.stack');
while(this.initialData.length) {
stackElement.insertAdjacentHTML(
'beforeend',
'<div class="stack-item">'+ this.initialData.pop() +'</div>'
)
}
clone.querySelector('.stack-description h4')
.textContent = this.metaData.name;
clone.querySelector('.stack-description p')
.textContent = this.metaData.description;
document.getElementById('stack-visualizer')
.appendChild(clone);
return stackWrapperId;
}
}
class AnimationList {
animations = [];
length() {
return this.animations.length;
}
push(animation) {
this.animations.push(animation);
}
shift() {
return this.animations.shift();
}
}
let animatorModule = (function() {
let animations = new AnimationList();
let animationsRunning = false;
let animationSpeed = 1200;
function getMoveDownAnimation(animation) {
let topElement = animation.stackElement.children[0];
let distance = animation.stackElement.offsetHeight;
if (topElement) {
distance = topElement.getBoundingClientRect().y
- animation.pushElement.getBoundingClientRect().y
- animation.pushElement.getBoundingClientRect().height
- 2; // Margin bottom
}
let moveDownAnimation = [
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
(0.2 * distance) + 'px',
(0.37 * distance) + 'px',
(0.55 * distance) + 'px',
(0.7 * distance) + 'px',
(0.87 * distance) + 'px',
distance + 'px',
distance + 'px'
];
return moveDownAnimation;
}
function getMoveUpAnimation(animation) {
let topElement = animation.stackElement.children[0];
let distance = topElement.getBoundingClientRect().y
- animation.pushElement.getBoundingClientRect().y;
let moveUpAnimation = [
(distance - 0.95 * distance) + 'px',
(distance - 0.87 * distance) + 'px',
(distance - 0.7 * distance) + 'px',
(distance - 0.55 * distance) + 'px',
(distance - 0.37 * distance) + 'px',
(distance - 0.2 * distance) + 'px',
distance + 'px',
distance + 'px',
distance + 'px',
distance + 'px',
distance + 'px',
distance + 'px',
distance + 'px'
];
return moveUpAnimation;
}
function pushAnimate(animation) {
animation.pushElement.textContent = animation.value;
let pushAnimationKeyFrames = {
// 25% - Show element
opacity: ['0', '0.3', '0.7', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'],
left: ['0', '0', '0', '0', '7px', '20px', '35px', '60px', '75px', '90px', '100px', '100px', '100px', '100px', '100px', '100px', '100px', '100px', '100px'],
top: getMoveDownAnimation(animation),
offset: [0, 0.08, 0.16, 0.25, 0.25, 0.31, 0.37, 0.43, 0.5, 0.56, 0.62, 0.68, 0.73, 0.78, 0.83, 0.88, 0.93, 0.98, 1]
};
let duplicateElement = animation.pushElement.cloneNode(true);
duplicateElement.classList.remove('hidden');
// TODO: Increase the height of the stack before pushing
let pushAnimation = animation.pushElement.animate(pushAnimationKeyFrames, animationSpeed);
return new Promise((resolve) => {
return pushAnimation.finished.then(() => {
animation.stackElement.prepend(duplicateElement);
resolve(`Push Animation completed!`);
});
})
}
function popAnimate(animation) {
let popAnimationKeyFrames = {
bottom: getMoveUpAnimation(animation),
left: ['0', '0', '0', '0', '0', '0', '7px', '20px', '35px', '60px', '75px', '90px', '100px'],
offset: [0, 0.07, 0.15, 0.22, 0.3, 0.37, 0.45, 0.52, 0.6, 0.67, 0.75, 0.82, 0.9, 1]
};
let topElement = animation.stackElement.children[0];
let popAnimation = topElement.animate(popAnimationKeyFrames, animationSpeed);
// The animation is not smooth
// So remove the item before animation is completed
setTimeout(() => {
topElement.remove();
animation.popElement.textContent = topElement.textContent;
}, animationSpeed - 200);
return new Promise((resolve) => {
return popAnimation.finished.then(() => {
// topElement.remove();
// animation.popElement.textContent = topElement.textContent;
resolve(`Pop Animation completed!`);
});
})
}
function displayCommentAnimate(animation) {
return new Promise((resolve) => {
document.getElementsByClassName('sv-comment')[0]
.innerHTML = animation.value;
setTimeout(() => {
resolve('Comment displayed!');
}, animation.timeout);
})
}
function displayOutputAnimate(animation) {
return new Promise((resolve) => {
let outputELement = document.getElementById('final-output');
outputELement.innerHTML = animation.value;
resolve('Output displayed!');
})
}
function runSingleAnimation(animation) {
switch (animation.type) {
case 'push':
return pushAnimate(animation);
break;
case 'pop':
return popAnimate(animation);
break;
case 'display-comment':
return displayCommentAnimate(animation);
break;
case 'display-output':
return displayOutputAnimate(animation);
break;
}
}
function runAnimations() {
if (animationsRunning) return;
animationsRunning = true;
// Perform the animations one after the other
let animation = animations.shift();
runSingleAnimation(animation)
.then(() => {
animationsRunning = false;
if (animations.length()) {
runAnimations();
}
});
}
function getStackElements(stackId) {
let stackWrapper = document.getElementById(stackId);
return {
stackElement: stackWrapper.getElementsByClassName('stack')[0],
pushElement: stackWrapper.getElementsByClassName('push-element')[0],
popElement: stackWrapper.getElementsByClassName('pop-element')[0]
}
}
let performPushAnimation = function (stackId, value) {
let animationObject = Object.assign(
{type: 'push', value: value},
getStackElements(stackId)
);
animations.push(animationObject);
runAnimations();
}
let performPopAnimation = function (stackId, value) {
let animationObject = Object.assign(
{type: 'pop', value: value},
getStackElements(stackId)
);
animations.push(animationObject);
runAnimations();
}
/**
* Set the animation duration.
*
* @param flot speed Duration in seconds (1, 2.5...)
*/
let setAnimationSpeed = function (speed) {
animationSpeed = speed * 1000;
}
let displayComment = function (comment, timeout = 0) {
let animationObject = {
type: 'display-comment',
value: comment,
timeout: timeout
};
animations.push(animationObject);
runAnimations();
}
let displayOutput = function (output) {
let animationObject = {
type: 'display-output',
value: output
};
animations.push(animationObject);
runAnimations();
}
let clearAnimations = function () {
animations = new AnimationList();
animationsRunning = false;
}
return {
performPushAnimation: performPushAnimation,
performPopAnimation: performPopAnimation,
setAnimationSpeed: setAnimationSpeed,
displayComment: displayComment,
displayOutput: displayOutput,
clearAnimations: clearAnimations
}
})();