Skip to main content

Access largest element of the stack


Design a max stack that supports push, pop, top, peekMax and popMax.
  • push(x) -- Push element x onto stack.
  • pop() -- Remove the element on top of the stack and return it.
  • getMax() -- Retrieve the maximum element in the stack

Example:
MaxStack stack = new MaxStack();
stack.push(5);
stack.push(1);
stack.push(5);
stack.getMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5

Note:
  1. -1e7 <= x <= 1e7
  2. Number of operations won't exceed 10000.
  3. The last four operations won't be called when stack is empty.

Solution:
This problem can be solved with multiple approaches. This approach makes use of two stacks to get the largest element. we can however optimize the behavior to use doubly linked list and a treemap. 


Comments

Post a Comment

Popular posts from this blog

Java 8- Sorting a hashmap (by key and by value) using lambda expression and streams

Sometimes while working on business problems, it’s very common to come across use cases wherein a map needs to be sorted by either keys or by values. In this post, we will cover some of the examples to sort a map of primitives and custom objects.   In below approaches, we will not destroy existing map and will create a new map to ensure consistency of sorting 1. Sort HashMap by key  In order to sort a map by key, all we need to do is to use sorted method of stream interface and pass a default default/custom comparator to it. Moreover, to sort by keys, we need to use comparingByKey method of Entry interface of Map. 2. Sort HashMap by values  In order to sort a map by key, all we need to do is to use sorted method of stream interface and pass a default default/custom comparator to it. Moreover, to sort by keys, we need to use comparingByValue method of Entry interface of Map.
Post a Comment
Read more

Walls and gates- Find shortest distances between rooms and gates

Leetcode: Walls and Gates You are given a  m x n  2D grid initialized with these three possible values. -1  - A wall or an obstacle. 0  - A gate. INF  - Infinity means an empty room. We use the value  2 31  - 1 = 2147483647  to represent  INF  as you may assume that the distance to a gate is less than 2147483647 . Fill each empty room with the distance to its  nearest  gate. If it is impossible to reach a gate, it should be filled with  INF . For example, given the 2D grid: INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INF After running your function, the 2D grid should be: 3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4 Understand the problem: It is very classic backtracking problem. We can start from each gate (0 point), and searching for its neighbors. We can either use DFS or BFS solution. Below is a DFS solution-
Post a Comment
Read more

Design LRU Cache

Design and implement a data structure for  Least Recently Used (LRU) cache . It should support the following operations:  get  and  put . get(key)  - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value)  - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. Follow up: Could you do both operations in  O(1)  time complexity? Example: LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1);        // returns 1 cache.put(3, 3);      // evicts key 2 cache.get(2);        // returns -1 (not found) cache.put(4, 4);     // evicts key 1 cache.get(1);        //...
Post a Comment
Read more