Bird
Raised Fist0
Interview Prepgreedy-algorithmsmediumAmazonFacebookBloomberg

Gas Station (Circular)

Choose your preparation mode4 modes available
Try ItSolutionTrace

Start learning this pattern below

Jump into concepts and practice - no test required

or
Recommended
Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong
▶
Steps
setup

Calculate net gas at each station

Compute net gas array where each element is gas[i] - cost[i]. This shows how much gas is gained or lost at each station.

💡 Net gas array simplifies the problem by focusing on surplus or deficit at each station.
Line:net = [gas[i] - cost[i] for i in range(n)]
💡 Net gas array reveals which stations add or consume gas, critical for checking circuit feasibility.
📊
Gas Station (Circular) - Watch the Algorithm Execute, Step by Step
Watching each step reveals how the greedy approach efficiently checks feasibility without simulating the entire trip repeatedly.
Step 1/18
·Active fill★Answer cell
record
-2
0
-2
1
-2
2
3
3
3
4
compare
-2
0
-2
1
-2
2
3
3
3
4
Result: 0
record
0
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
0
10
record
i
0
0
-2
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
0
10
record
0
0
i
-2
1
-4
2
0
3
0
4
0
5
0
6
0
7
0
8
0
9
0
10
record
0
0
-2
1
i
-4
2
-6
3
0
4
0
5
0
6
0
7
0
8
0
9
0
10
record
0
0
-2
1
-4
2
i
-6
3
-3
4
0
5
0
6
0
7
0
8
0
9
0
10
record
0
0
-2
1
-4
2
-6
3
i
-3
4
0
5
0
6
0
7
0
8
0
9
0
10
record
0
0
-2
1
-4
2
-6
3
-3
4
i
0
5
-2
6
0
7
0
8
0
9
0
10
record
0
0
-2
1
-4
2
-6
3
-3
4
0
5
i
-2
6
-4
7
0
8
0
9
0
10
record
0
0
-2
1
-4
2
-6
3
-3
4
0
5
-2
6
i
-4
7
-6
8
0
9
0
10
record
0
0
-2
1
-4
2
-6
3
-3
4
0
5
-2
6
-4
7
i
-6
8
-3
9
0
10
record
0
0
-2
1
-4
2
-6
3
-3
4
0
5
-2
6
-4
7
-6
8
i
-3
9
0
10
compare
i
0
0
-2
1
-4
2
-6
3
-3
4
0
5
-2
6
-4
7
-6
8
-3
9
0
10
compare
0
0
i
-2
1
-4
2
-6
3
-3
4
0
5
-2
6
-4
7
-6
8
-3
9
0
10
compare
0
0
-2
1
i
-4
2
-6
3
-3
4
0
5
-2
6
-4
7
-6
8
-3
9
0
10
compare
0
0
-2
1
-4
2
i
-6
3
-3
4
0
5
-2
6
-4
7
-6
8
-3
9
0
10
Result: 3
record
0
0
-2
1
-4
2
start
-6
3
-3
4
0
5
-2
6
-4
7
-6
8
-3
9
0
10
Result: 3

Key Takeaways

✓ The net gas array transforms the problem into finding a non-negative sum subarray in a circular array.

This insight is hard to see from code alone because it abstracts the problem into a simpler numeric form.

✓ Prefix sums allow O(1) queries for sums over any window, enabling efficient feasibility checks.

Visualizing prefix sums clarifies why the algorithm avoids repeated summations.

✓ Checking each start index with prefix sums reveals exactly where the circuit can be completed.

Seeing each comparison step shows why some start points fail and one succeeds.

Practice

(1/5)
1. You have a list of children each with a greed factor and a list of cookies each with a size. You want to assign cookies to children so that each child gets at most one cookie and the cookie size is at least the child's greed factor. Which algorithmic approach guarantees the maximum number of content children?
easy
A. Greedy algorithm by sorting greed factors and cookie sizes, then assigning smallest sufficient cookie to each child
B. Dynamic Programming to try all possible assignments and pick the best
C. Brute force nested loops checking every cookie for every child without sorting
D. Divide and Conquer by splitting children and cookies and merging results

Solution

  1. Step 1: Understand problem constraints

    Each child can get at most one cookie, and the cookie must satisfy the child's greed factor.

  2. Step 2: Identify optimal approach

    Sorting both greed and cookie arrays allows a greedy assignment from smallest greed to smallest sufficient cookie, ensuring maximum matches.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Greedy sorting approach is classic for assignment problems [OK]
Hint: Sort both arrays and assign greedily [OK]
Common Mistakes:
  • Thinking brute force is needed for optimality
  • Assuming DP is required
  • Ignoring sorting leads to suboptimal matches
2. Consider the following Python code for forming the largest number from the list [3, 30, 34, 5]. What is the final returned string?
easy
A. 534330
B. 53430
C. 534303
D. 534330

Solution

  1. Step 1: Convert numbers to strings: ['3', '30', '34', '5']

    We compare pairs by concatenation: '5'+'34' vs '34'+'5' -> '534' > '345', so '5' before '34'. Similarly for others.

  2. Step 2: Sort using custom comparator to get order: ['5', '34', '3', '30']

    Concatenate to get '534330'. The check for leading zero is false since first is '5'.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Concatenation order matches expected largest number [OK]
Hint: Compare concatenations 'a+b' and 'b+a' to order strings [OK]
Common Mistakes:
  • Off-by-one in sorting
  • Ignoring leading zero case
  • Misordering '30' and '3'
3. Consider the following Python function that calculates the minimum number of platforms needed. Given the input arrivals = [900, 940, 950] and departures = [910, 1200, 1120], what is the value of max_platforms after processing the second train (index 1)?
easy
A. 3
B. 1
C. 2
D. 0

Solution

  1. Step 1: Sort trains by arrival time

    Sorted trains: [(900, 910), (940, 1200), (950, 1120)]

  2. Step 2: Process trains up to index 1

    After first train: heap=[910], max_platforms=1 Second train arrival=940, heap top=910 ≤ 940, pop 910 Push 1200, heap=[1200], max_platforms=max(1,1)=1 Since question asks after second train, max_platforms=1

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Heap size after second train is 1, max_platforms updated to 1 [OK]
Hint: Heap pops departures ≤ arrival before push [OK]
Common Mistakes:
  • Not popping from heap before push
  • Confusing max_platforms update timing
  • Off-by-one in iteration
4. What is the time complexity of the optimal max heap approach to reorganize a string of length n with k unique characters?
medium
A. O(n²) because each character insertion may require scanning the entire string
B. O(n log k) because each of the n characters is pushed and popped from a heap of size k
C. O(k log n) because the heap operations depend on the string length
D. O(n) because each character is processed once without extra overhead

Solution

  1. Step 1: Identify heap operations per character

    Each character is pushed and popped at most once per occurrence, total n operations.

  2. Step 2: Analyze heap size and operation cost

    Heap size is at most k (unique chars), each push/pop is O(log k), so total O(n log k).

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Heap operations dominate, not scanning entire string [OK]
Hint: Heap ops cost O(log k) per character [OK]
Common Mistakes:
  • Confusing n and k in complexity
  • Assuming linear time without heap cost
  • Mistaking quadratic due to nested loops
5. Suppose the problem is modified: instead of finding the largest monotone increasing digits number ≤ n, you want the largest monotone increasing digits number ≤ n that can reuse digits any number of times (digits can be repeated arbitrarily). Which approach correctly adapts the algorithm?
hard
A. Use the original greedy algorithm but allow digits after marker to be any digit less than or equal to the digit at marker-1
B. Sort the digits of n and build the largest monotone number by repeating the smallest digit as many times as needed
C. Use a backtracking approach to generate all monotone numbers with digits ≤ those in n, allowing reuse, and pick the largest ≤ n
D. Modify the greedy algorithm to decrement digits and set trailing digits to the digit at marker-1 instead of 9

Solution

  1. Step 1: Understand digit reuse changes problem nature

    Allowing reuse means digits can be repeated arbitrarily, so greedy digit decrement and trailing 9 assignment no longer guarantee largest monotone number ≤ n.

  2. Step 2: Backtracking enumerates all monotone numbers with digit reuse

    Backtracking can generate all monotone numbers with digits ≤ those in n, allowing reuse, then pick the largest ≤ n.

  3. Step 3: Other options fail to handle reuse or produce incorrect numbers

    Sorting digits or modifying trailing digits to marker-1 digit does not guarantee largest monotone number with reuse.

  4. Final Answer:

    Option C -> Option C

  5. Quick Check:

    Backtracking correctly handles reuse and monotonicity constraints [OK]
Hint: Digit reuse breaks greedy; backtracking needed for correctness [OK]
Common Mistakes:
  • Trying to adapt greedy without full enumeration
  • Assuming trailing digits can be set to 9 or marker digit
  • Ignoring exponential complexity of reuse