Moderate Greedy Question 132 of 224

How do you find the starting gas station to complete a circular tour, or determine it is impossible?

DSA interview set · Speak this in 60–90 seconds · Faridabad & Delhi NCR

PICTURE THIS: DATABASE INDEX

Without indexScan every row

With indexJump to keys

CostWrites slower

Simple meaning

If total gas is less than total cost, no start works.

WHY — Greedy instead of guessing?

Why interviewers care about Greedy:

This is a process

question about Greedy.

Panels listen for order,

trade-offs, and what you would actually do on a DSA project - not buzzwords.

Stay structured

Name the idea, why it exists, then one short example.

Close cleanly

End with when you use it and one common pitfall.

STEPS — What happens step by step?

Before you speak the answer, walk the interviewer through these steps:

1
If total gas is
less than total cost, no start works.
2
Otherwise the unique start
is the index after the worst prefix tank dip (reset tank when it goes negative).
3
One O(n) pass and
O(1) space.
4
Give an example
Trying every start is O(n^2).
5
Common mistake
What juniors usually get wrong.
6
Close
When you pick this over the alternative.

EXAMPLE — See it in action

Here's a short line you can speak, broken into clear beats:

Say this line

“One O(n) pass and O(1) space.”

Break into beats

OneOnpassandO

Speaking order

2987408337471632900

Note: Adapt this scaffold to your own project — keep it under 60–90 seconds.

Key takeaway

If total gas is less than total cost, no start works. Otherwise the unique start is the index after the worst prefix tank dip (reset tank when it goes negative).