beingsde
Sign In
Back to all DSA patterns
Greedy•Pattern: Greedy•Medium

Gas station — can you complete the circuit?

Problem Intuition & Objective

Find the starting station for a circular route if possible.

Time ComplexityO(n)
Optimal
Space ComplexityO(1)
Memory Bounds
Optimal Algorithmic Approach

Single-pass greedy: reset starting point when tank runs out.

Core Invariants & Edge Cases

  • If total gas < total cost, no solution
  • Track current tank; if it goes negative, reset and try next station as start
  • The last candidate start after full scan is the answer
Previous ProblemNon-overlapping intervals — minimum removalNext Problem Meeting rooms II — minimum rooms needed

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.