🎒
Technical Interview Study Guide
  • 🍕Welcome!
  • 🍥Getting Started
    • Study Plan
    • Optimizing Revision
    • Summer 2024 Timeline
    • FAQs
  • 🥨Algorithms
    • Binary Search
    • Sorting
    • Recursion
    • Graph
    • Quick Select
    • Intervals
    • Binary
    • Geometry
    • Dynamic Programming
  • 🥞Data Structures
    • Arrays
      • Matrices
    • Strings
    • Linked Lists
      • Doubly Linked Lists
    • Hash Tables
    • Graphs
      • Trees
        • Binary Search Trees
        • Heaps
        • Tries
        • Segment Trees
    • Stacks
    • Queues
      • Double Ended Queues
    • Union-Find Disjoint Set (UFDS)
  • 🍡Problems Guide
    • Dynamic Programming Roadmap
      • Warmup
        • Climbing Stairs
        • Nth Tribonacci Number
        • Perfect Squares
      • Linear Sequence
        • Min Cost to Climb Stairs
        • Minimum Time to Make Rope Colorful
        • House Robber
        • Decode Ways
        • Minimum Cost for Tickets
        • Solving Questions with Brainpower
  • 🍣Other Technical Topics
    • General Problem Solving
    • Runtime Predictions
    • System Design
      • SQL
      • Accessing APIs
    • Operating Systems
  • 🍿Non-technical Topics
    • Behavioral Interviews
    • Resumes
Powered by GitBook
On this page
  • Runtime analysis
  • Corner cases
  • Take note…
  • Techniques
  • Monotonic stack
  • Mathematical equation parsing
  1. Data Structures

Stacks

Stack problems usually come in the form of monotonic stack problems

PreviousSegment TreesNextQueues

Last updated 1 year ago

Runtime analysis

  1. Top/peek: O(1)O(1)O(1)

  2. Push: O(1)O(1)O(1)

  3. Pop: O(1)O(1)O(1)

  4. Search: O(n)O(n)O(n)

  5. isEmpty: O(1)O(1)O(1)

Corner cases

  1. Empty stack

  2. Stack with one item

  3. Stack with two items

Take note…

  1. pop() is LIFO so if order of insertion matters, reverse the popped values

Techniques

Monotonic stack

Push elements while monotonically increasing/decreasing. Then, keep popping the elements once the reverse occurs until either empty or incoming element is eventually increasing/decreasing

  • The final stack can represent the overall values

Mathematical equation parsing

Stacks are useful for problems like evaluating equations as you can push numbers onto the stack and operations just need to pop the top two elements of the stack

🥞