insert, delete, max in O(1)

by

This is a classical interview question, and is usually presented like this:

Devise a stack-like data structure that does push, pop and min (or max) operations in O(1) time. There are no space constraints.

The answer is, you use two stacks: the main stack, and a min (or max) stack.

So for example, after pushing 1,2,3,4,5 onto the stack, your stacks would look like this:

MAIN   MIN
+---+  +---+
| 5 |  | 1 |
| 4 |  | 1 |
| 3 |  | 1 |
| 2 |  | 1 |
| 1 |  | 1 |
+---+  +---+

However, if you were to push 5,4,3,2,1, the stacks would look like this:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 2 |  | 2 |
| 3 |  | 3 |
| 4 |  | 4 |
| 5 |  | 5 |
+---+  +---+

For 5,2,4,3,1 you would have:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 3 |  | 2 |
| 4 |  | 2 |
| 2 |  | 2 |
| 5 |  | 5 |
+---+  +---+

and so on.

You can also save some space by pushing to the min stack only when the minimum element changes, iff the items are known to be distinct.

More Related Contents:

  1. How to create the most compact mapping n → isprime(n) up to a limit N?
  2. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  3. Hash table runtime complexity (insert, search and delete)
  4. Data structures for loaded dice?
  5. Find kth smallest element in a binary search tree in Optimum way
  6. How to implement a queue using two stacks?
  7. How do you validate a binary search tree?
  8. design a stack such that getMinimum( ) should be O(1)
  9. Computing set intersection in linear time?
  10. Best algorithm to test if a linked list has a cycle
  11. How to delete in a heap data structure?
  12. Array remove duplicate elements
  13. What is the difference between tree depth and height?
  14. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  15. What is the fastest way to find the closest point to a given point?
  16. O(klogk) time algorithm to find kth smallest element from a binary heap
  17. In Order Successor in Binary Search Tree
  18. Skip List vs. Binary Search Tree
  19. Algorithm for autocomplete?
  20. Hashing a Tree Structure
  21. graph – Dijkstra for The Single-Source Longest Path
  22. What is the advantage to using Bloom filters?
  23. Why does Dijkstra’s algorithm use decrease-key?
  24. Search a sorted 2D matrix [duplicate]
  25. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  26. Why use binary search if there’s ternary search?
  27. Why are hash table expansions usually done by doubling the size?
  28. What are probabilistic data structures?
  29. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  30. Given a set of intervals, find the interval which has the maximum number of intersections

Leave a Comment