DEV Community

Cover image for Road to Genius: superior #55
Ilya Nevolin
Ilya Nevolin

Posted on

1

Road to Genius: superior #55

Each day I solve several coding challenges and puzzles from Codr's ranked mode. The goal is to reach genius rank, along the way I explain how I solve them. You do not need any programming background to get started, and you will learn a ton of new and interesting things as you go.

function MinStack() {
    this.stack = []
    this.MS = []
};

MinStack.prototype.push = function(x) {
    this.stack.push(x)
    if (this.MS.length == 0 || x <= this.MS[this.MS.length - 1]) {
        this.MS.push(x)
    }
};

MinStack.prototype.pop = function() {
    const x = this.stack.pop()
    if (x !== void 0 && x === this.MS[this.MS.length - 1]) {
        this.MS.pop()
    }
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1]
};

MinStack.prototype.min = function() {
    return this.MS[this.MS.length - 1]
};

var obj = new MinStack()
obj.push(20)
obj.push(15)
obj.push(16)
obj.push(3)
obj.push(18)

let A = obj.top() + obj.min();

// A = ? (number)
Enter fullscreen mode Exit fullscreen mode

In today's challenge we are looking at some kind of special "stack" class called MinStack.

The last few lines of code is what we have to analyze: first the code pushes a bunch of numbers to this stack, finally it's asking for the answer:

obj = MinStack()
obj.push(...)
A = obj.top() + obj.min()
// A = ?
Enter fullscreen mode Exit fullscreen mode

The constructor of MinStack creates two empty arrays MS and stack, so that's all there is to it. The push function adds the argument to the stack array, and if the number satisfies the if-condition it's also added to MS. This particular condition checks if MS is empty, or that the latest element in MS is greater than or equal to the number. In a nutshell this adds the number to MS if it's smaller than the latest number inside (or if it's empty of course). Hence the name MinStack, it's keeping track of the smallest numbers in the stack structure.

Here's some pseudo-code that to help us solve the challenge:

stack = []
MS    = []

push(20)
stack = [20]
MS    = [20]

push(15)
stack = [20, 15]
MS    = [20, 15]

push(16)
stack = [20, 15, 16]
MS    = [20, 15]

push(3)
stack = [20, 15, 16, 3]
MS    = [20, 15, 3]

push(18)
stack = [20, 15, 16, 3, 18]
MS    = [20, 15, 3]


A = top() + min()
A = 18    + 3
a = 21
Enter fullscreen mode Exit fullscreen mode

coding challenge answer

By solving these challenges you train yourself to be a better programmer. You'll learn newer and better ways of analyzing, debugging and improving code. As a result you'll be more productive and valuable in business. Get started and become a certified Codr today at https://nevolin.be/codr/

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more