Stacks Binary Trees

Stock Span Problem

Stacks
JavaScript

Problem:

Given a series of daily price quotes for a stock over N days, calculate the span of the stock’s price for each day. The span S(i) of the stock’s price on a given day i is defined as the maximum number of consecutive days before day i, including day i itself, for which the price of the stock on the current day is greater than or equal to the price on the previous days.

Example:

Input Array (Stock price): [150, 120, 140, 160, 140, 145, 150]

Output (Stock Span): [1, 1, 2, 4, 1, 2, 3]

For the first value, 150, there are no previous values, so the stock span is 1. For the value 120, the previous value is 150, which is greater than 120, so the stock span is 1. However, for 140, the previous value 120 is smaller, and the stock span extends to 2, as 140 is greater than 120. Similarly, for 150 at the end of the array, there are 3 values (including the current value itself) that are less than or equal to 150, so the stock span is 3.

Algorithm:

To solve this, we need two stacks. We will loop through the price array and push each item onto Stack 1. For each item pushed onto Stack 1, we will check if the previous values are less than or equal to the current value being pushed. To achieve this, we can use a second stack (Stack 2). After finding the stock span for each value, we can restore Stack 1 by transferring the elements from Stack 2 back to it.

Steps:

  1. Loop through the price array and push each price onto Stack 1.
  2. For each price pushed onto Stack 1, compare it with the previous values in Stack 1.
  3. To find the stock span, pop values from Stack 1 and push them onto Stack 2 until you find a value that is greater than the current price. The number of popped elements gives the stock span for that day.
  4. Once Stack 1 is empty, push all the elements from Stack 2 back into Stack 1 and continue processing the next price in the array.

Solution & Visualize:

The animation/visualization below demonstrates how the algorithm to reverse a string works. Feel free to experiment by changing the input strings.

Result
Code

Input:

Enter the array elements followed by a comma

Output:

   
solution.js
stack.js
stack-displayer.js
animator-module.js
function stackSolution(args) {
    let array = args[0];

    const stack1 = new Stack(
        [],
        {
            name: 'Stack 1',
            description: 'Stack 1.'
        }
    );

    const stack2 = new Stack(
        [],
        {
            name: 'Stack 2',
            description: 'Stack 2'
        }
    );

    let popOpsCount = 0;
    let currentValue = null;
    let stockSpan = [];
    let currentStockSpan = 1;
    while (array.length) {
        animatorModule.displayComment(
            'Loop through the array and compare the previous values in stack. <br>'
            + highlightArray([...array], 0)
            + '<br> Stock Span: ' + currentStockSpan,
            500
        );

        currentValue = array[0];
        currentStockSpan = 1;

        while (! stack1.isEmpty()) {
            if (stack1.top() > currentValue) {
                break;
            }

            animatorModule.displayComment(
                'If the top element of Stack 1 is smaller then push it Stack 2. <br>'
                + highlightArray([...array], 0)
                + '<br> Stock Span: ' + currentStockSpan,
                500
            );

            stack2.push(stack1.pop());
            popOpsCount++;
            currentStockSpan++;
        }

        while (popOpsCount > 0) {
            if (stack1.isEmpty()) {
                animatorModule.displayComment(
                    'Stack 1 is empty. Now push the elements back to Stack 1 <br>'
                    + highlightArray([...array], 0)
                    + '<br> Stock Span: ' + currentStockSpan,
                    500
                );
            } else {
                animatorModule.displayComment(
                    'We hit the larger value. Now push the elements back to Stack 1 <br>'
                    + highlightArray([...array], 0)
                    + '<br> Stock Span: ' + currentStockSpan,
                    500
                );
            }

            stack1.push(stack2.pop());
            popOpsCount--;
        }

        array.shift();
        stack1.push(currentValue);
        stockSpan.push(currentStockSpan);
        animatorModule.displayOutput([...stockSpan]);
    }

    animatorModule.displayOutput(stockSpan);
    animatorModule.displayComment('');
    return stockSpan;
}
                                        
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
    }
})();