Skip to main content

Data structure problem 3: Implement a Stack With Minimum

 


Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.

void push(int val) pushes the element val onto the stack.

void pop() removes the element on the top of the stack.

int top() gets the top element of the stack.

int getMin() retrieves the minimum element in the stack.

Input

["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output

[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Solution:


 var MinStack = function({
this.elements = [];
};

/**

 @param {number} x
 @return {void}
 */
MinStack.prototype.push = function(x) {
  this.elements.push({
    value: x,
    min: this.elements.length === 0 ? x : Math.min(x, this.getMin()),
  });
};
/**

 @return {void}
 */
MinStack.prototype.pop = function() {
  this.elements.pop();
};
/**

 @return {number}
 */
MinStack.prototype.top = function() {
  return this.elements[this.elements.length - 1].value;
};
/**

 @return {number}
 */
MinStack.prototype.getMin = function() {
  return this.elements[this.elements.length - 1].min;
};




Explanation: In this approch whenever we are pushing something in stack we are maintaing value and min value element and that does the work .

Comments

Popular posts from this blog

Node JS:Understanding bin in package.json.

Well as a Node Js developer we know package.json as dependency file where we keep a note of all dependencies of our project. Here we will be looking at what is bin in package.json? To understand this we first need to understand command line application and it's purpose. CLI applications are mostly used to automate things such as deployments of application,running tests,building reports and the list goes on and on. So lets start with creating our first CLI application. First, let’s make sure you have the tools required. To complete this tutorial, you will need the following: 1)A recent version of Node.js downloaded and installed 2)A good text editor, such as Visual Studio Code Next, open your computer’s command prompt (Windows) or terminal (macOS/Linux). Change the current directory to the folder where you save your documents or projects. Enter the following commands to create a new project folder and initialize the project. mkdir hello-cli cd hello-cli npm init Nex

Node.js: Extract text from image using Tesseract.

In this article, we will see how to extract text from images using Tesseract . So let's start with this use-case, Suppose you have 300 screenshot images in your mobile which has an email attribute that you need for some reason like growing your network or for email marketing. To get an email from all these images manually into CSV or excel will take a lot of time. So now we will check how to automate this thing. First, you need to install Tesseract OCR( An optical character recognition engine ) pre-built binary package for a particular OS. I have tested it for Windows 10. For Windows 10, you can install  it from here. For other OS you make check  this link. So once you install Tesseract from windows setup, you also need to set path variable probably, 'C:\Program Files\Tesseract-OCR' to access it from any location. Then you need to install textract library from npm. To read the path of these 300 images we can select all images and can rename it to som

Node.js: create an excel file with multiple tabs.

This article is a sample code to generate an excel file with multiple tabs using  excel4node  module. Install: npm i excel4node Let's see the sample code, var excel = require( 'excel4node' ); // Create a new instance of a Workbook class var workbook = new excel.Workbook(); // Add Worksheets to the workbook var worksheet = workbook.addWorksheet( 'Buy order types' ); var worksheet1 = workbook.addWorksheet( 'Sell order types' ); // Style for headers var style = workbook.createStyle({ font : { color : '#EA3A14' , size : 18 }, numberFormat : '$#,##0.00; ($#,##0.00); -' }); var styleForData = workbook.createStyle({ font : { color : '#47180E' , size : 12 }, alignment : { wrapText : true , horizontal : 'center' , }, numberFormat : '$#,##0.00; ($#,##0.00); -' }); let buyOrderTypes = [ {name : "buy" ,id : "1" ,comment : "Normal