Greedy Array Patterns: Gas Station, Candy, Arrows & Partition Labels

1. Introduction & Motivation

This lesson is a collection, not a single derivation. It covers four classic interview problems that all live in the "greedy over an array" family, but each one earns its greedy correctness in a genuinely different way. There is no single template that unifies them — that is exactly the point. A candidate who has only memorized "sort, then scan" for interval problems will be stuck the moment the array is circular (Gas Station), the constraint is bidirectional (Candy), the objects are ranges instead of points (Interval Stabbing), or the goal is to close a group as early as possible (Partition Labels).

What ties the four together is method, not formula: each problem has a small piece of local information (a running tank level, a neighbor comparison, an arrow position, a last-seen index) that is sufficient to make an irrevocable decision at each step without ever needing to reconsider it. Learning to find that piece of information — and to prove it is sufficient — is the actual transferable skill.

2. Prerequisites

This lesson assumes you can already read and modify a single-pass array scan, and that you are comfortable with the general shape of a greedy correctness argument (exchange argument, staying-ahead argument, or a direct contradiction proof). Two closely related greedy-on-arrays problems are not re-derived here because they are already covered in full elsewhere in this curriculum:

• Jump Game I & II — reachability and minimum jumps via a running "farthest reachable index," fully proved and implemented in DSA Part 16: Greedy Proofs & Scheduling § Jump Game.
• Merge Intervals (and the closely related Non-overlapping Intervals) — sort-by-start-time interval merging, fully proved and implemented in DSA Part 16: Greedy Proofs & Scheduling § Interval Scheduling.

If either of those feels unfamiliar, read that lesson's sections first — this one builds on the same "sort, then make one linear pass" instinct without repeating the setup.

3. A Concrete Example

Section 4 explains exactly why "reset to the next index the instant the tank goes negative" is safe, rather than merely a convenient heuristic.

4. Gas Station (Circular Tour Feasibility)

LeetCode 134. Given gas[] and cost[] for n stations arranged in a circle, return the starting station index from which a car with an initially empty tank can complete the entire circuit exactly once, or −1 if no such station exists. It is guaranteed that if a solution exists, it is unique.

Plain-English steps:

1. If total gas is less than total cost, no starting station works — return −1 immediately.
2. Otherwise, a valid start exists. Initialize candidate = 0 and tank = 0.
3. Scan i from 0 to n−1. Add gas[i] − cost[i] to tank.
4. If tank drops below 0, the run starting at candidate has failed at i. Set candidate = i + 1 and reset tank = 0.
5. After the scan, candidate is the answer.

Why skipping past the failure point is valid

The key fact to prove is: if the tank goes negative while attempting a start at index $s$, no index in $[s, j]$ can be a valid start, where $j$ is the index where the tank first went negative. This licenses jumping the candidate all the way to $j+1$ instead of retrying every index between $s$ and $j$ individually — turning an $O(n^2)$ brute force into a single $O(n)$ pass.

Define the prefix sum $P(s, i) = \sum_{k=s}^{i} \big(gas[k] - cost[k]\big)$, the tank level after starting at $s$ and driving through station $i$. Suppose starting at $s$ fails first at $j$, meaning $P(s, i) \geq 0$ for every $i$ with $s \leq i \lt j$, but $P(s, j) \lt 0$. Now consider any candidate start $s'$ with $s \lt s' \leq j$. Because the run from $s$ to $s'-1$ never went negative, $P(s, s'-1) \geq 0$. Splitting the sum,

$$P(s, j) = P(s, s'-1) + P(s', j)$$

so $P(s', j) = P(s, j) - P(s, s'-1) \leq P(s, j) \lt 0$. Starting at $s'$ also runs the tank negative by the time it reaches $j$ — it fails too, and possibly earlier. So none of $s+1, s+2, \ldots, j$ can be the answer, which is exactly why the algorithm is allowed to advance the candidate directly to $j+1$ and reset the tank, without re-examining the skipped indices.

The remaining question is why some start must succeed at all when $\sum gas \geq \sum cost$. Suppose the single forward scan from index 0 (with resets) ends with final candidate $c$. By construction, every index from 0 up to $c-1$ was ruled out by the argument above, each ruling-out consuming exactly one contiguous failed run. Because $\sum_{i=0}^{n-1}(gas[i]-cost[i]) = \sum gas - \sum cost \geq 0$, the total of all these consumed negative segments plus the final segment starting at $c$ must sum to something non-negative overall; since every prior segment was strictly negative (that is why it failed), the final segment from $c$ to the end of the array — wrapping around to close the circuit — cannot itself be negative at any prefix, or the same argument would have advanced the candidate again. This is the standard "total surplus forces a working start to exist" argument, and it is why the algorithm needs only one linear pass with the total-sum precheck, never a second pass to confirm the candidate.

def can_complete_circuit(gas, cost):
    """
    LeetCode 134: Gas Station
    Return the starting index that completes the circuit, or -1.
    Time: O(n), Space: O(1)
    """
    if len(gas) != len(cost):
        raise ValueError("gas and cost must have the same length")
    if sum(gas) < sum(cost):
        return -1  # total surplus is negative: no start can work

    tank = 0
    candidate = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            # No station in [candidate, i] can be a valid start either.
            candidate = i + 1
            tank = 0
    return candidate

# Examples
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print("Start station:", can_complete_circuit(gas, cost))  # Start station: 3

gas2 = [2, 3, 4]
cost2 = [3, 4, 3]
print("Start station:", can_complete_circuit(gas2, cost2))  # Start station: -1

#include <iostream>
#include <vector>
#include <numeric>
#include <stdexcept>

int canCompleteCircuit(const std::vector<int>& gas, const std::vector<int>& cost) {
    if (gas.size() != cost.size()) {
        throw std::invalid_argument("gas and cost must have the same length");
    }
    long totalGas = std::accumulate(gas.begin(), gas.end(), 0L);
    long totalCost = std::accumulate(cost.begin(), cost.end(), 0L);
    if (totalGas < totalCost) {
        return -1;  // total surplus is negative: no start can work
    }

    long tank = 0;
    int candidate = 0;
    for (std::size_t i = 0; i < gas.size(); ++i) {
        tank += gas[i] - cost[i];
        if (tank < 0) {
            // No station in [candidate, i] can be a valid start either.
            candidate = static_cast<int>(i) + 1;
            tank = 0;
        }
    }
    return candidate;
}

int main() {
    std::vector<int> gas{1, 2, 3, 4, 5};
    std::vector<int> cost{3, 4, 5, 1, 2};
    std::cout << "Start station: " << canCompleteCircuit(gas, cost) << '\n';  // 3

    std::vector<int> gas2{2, 3, 4};
    std::vector<int> cost2{3, 4, 3};
    std::cout << "Start station: " << canCompleteCircuit(gas2, cost2) << '\n';  // -1
}

import java.util.Arrays;

public class GasStation {
    static int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas.length != cost.length) {
            throw new IllegalArgumentException("gas and cost must have the same length");
        }
        long totalGas = Arrays.stream(gas).asLongStream().sum();
        long totalCost = Arrays.stream(cost).asLongStream().sum();
        if (totalGas < totalCost) {
            return -1;  // total surplus is negative: no start can work
        }

        long tank = 0;
        int candidate = 0;
        for (int i = 0; i < gas.length; i++) {
            tank += gas[i] - cost[i];
            if (tank < 0) {
                // No station in [candidate, i] can be a valid start either.
                candidate = i + 1;
                tank = 0;
            }
        }
        return candidate;
    }

    public static void main(String[] args) {
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};
        System.out.println("Start station: " + canCompleteCircuit(gas, cost)); // 3

        int[] gas2 = {2, 3, 4};
        int[] cost2 = {3, 4, 3};
        System.out.println("Start station: " + canCompleteCircuit(gas2, cost2)); // -1
    }
}

flowchart TD
    A["Precheck: total gas < total cost?"] -->|Yes| Z["Return -1: no start is possible"]
    A -->|No| B["candidate = 0, tank = 0, i = 0"]
    B --> C["tank += gas[i] - cost[i]"]
    C --> D{"tank < 0 ?"}
    D -->|Yes| E["No start in [candidate, i] can work either"]
    E --> F["candidate = i + 1, tank = 0"]
    F --> G["i = i + 1"]
    D -->|No| G
    G --> H{"i < n ?"}
    H -->|Yes| C
    H -->|No| I["Return candidate as the answer"]
                

The diagram shows the same rule traced in Section 3: the moment the tank dips below zero, every station from the current candidate through the failing index is eliminated in one step, and the search resumes immediately after the failure.

5. Candy / Distribute Candies

LeetCode 135. There are $n$ children standing in a line, each with a rating. Every child must receive at least 1 candy, and any child with a higher rating than an adjacent neighbor must receive strictly more candies than that neighbor. Find the minimum total number of candies needed.

Plain-English steps:

1. Give every child 1 candy to start: candies[i] = 1 for all $i$.
2. Left-to-right pass: for each $i$ from 1 to $n-1$, if ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1. After this pass, every child's count already respects its left neighbor.
3. Right-to-left pass: for each $i$ from $n-2$ down to 0, if ratings[i] > ratings[i+1], set candies[i] = max(candies[i], candies[i+1] + 1). The max is essential: it must not discard a larger value already earned from the left-to-right pass.
4. Sum candies[] for the answer.

Why does the second pass never break the first pass's guarantee? The right-to-left pass only ever increases candies[i] (via max), and it only touches candies[i] when ratings[i] > ratings[i+1] — a fact about the right neighbor that the left-to-right pass never examined. Raising candies[i] can only help it stay strictly greater than candies[i-1] when required (never hurt, since the left-to-right relationship was `>` and increasing candies[i] preserves any existing `>`), so both directional constraints hold simultaneously at the end.

For ratings = [1, 2, 3, 2, 1], the left-to-right pass alone gives [1, 2, 3, 1, 1] — correct on the left side, but child 3 (rating 2) has only 1 candy despite outranking child 4 (rating 1, also 1 candy), a tie that violates the rule. The right-to-left pass fixes exactly that, raising child 3 to 2 candies. Final distribution: [1, 2, 3, 2, 1], total 9 candies.

def candy(ratings):
    """
    LeetCode 135: Candy
    Minimum total candies satisfying both-neighbor constraints.
    Time: O(n), Space: O(n)
    """
    n = len(ratings)
    if n == 0:
        return 0
    candies = [1] * n

    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1

    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)

    return sum(candies)

# Examples
print("Total candies:", candy([1, 2, 3, 2, 1]))  # Total candies: 9
print("Total candies:", candy([1, 0, 2]))        # Total candies: 5

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

int candy(const std::vector<int>& ratings) {
    int n = static_cast<int>(ratings.size());
    if (n == 0) return 0;
    std::vector<int> candies(n, 1);

    for (int i = 1; i < n; ++i) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }
    for (int i = n - 2; i >= 0; --i) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = std::max(candies[i], candies[i + 1] + 1);
        }
    }
    return std::accumulate(candies.begin(), candies.end(), 0);
}

int main() {
    std::vector<int> ratings{1, 2, 3, 2, 1};
    std::cout << "Total candies: " << candy(ratings) << '\n';  // 9

    std::vector<int> ratings2{1, 0, 2};
    std::cout << "Total candies: " << candy(ratings2) << '\n';  // 5
}

import java.util.Arrays;

public class Candy {
    static int candy(int[] ratings) {
        int n = ratings.length;
        if (n == 0) return 0;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);

        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }
        return Arrays.stream(candies).sum();
    }

    public static void main(String[] args) {
        int[] ratings = {1, 2, 3, 2, 1};
        System.out.println("Total candies: " + candy(ratings)); // 9

        int[] ratings2 = {1, 0, 2};
        System.out.println("Total candies: " + candy(ratings2)); // 5
    }
}

6. Interval Stabbing (Minimum Arrows to Burst Balloons)

Each balloon is a horizontal interval [start, end] (its diameter along the x-axis). An arrow shot straight up at some x-coordinate bursts every balloon whose interval contains that coordinate. Given all the balloon intervals, find the minimum number of arrows needed so every balloon is pierced by at least one arrow.

This is the same greedy pattern family as interval covering / non-overlapping intervals: sort by one coordinate, then make a single greedy pass. Concretely: sort the balloons by their end coordinate. Shoot the first arrow at the end of the first (unpierced) balloon. That single arrow pierces every other balloon whose start is at or before that arrow position — skip all of them. The first balloon whose start is strictly past the current arrow needs a new arrow, shot at its end. Repeat. The shared exchange-argument reasoning for why sorting by the coordinate you extend greedily is safe is developed in full for the interval-covering variant in Interval Scheduling: Minimum Meeting Rooms & Point Covering § Interval Covering; this section focuses on applying that pattern to the balloon-arrow framing rather than re-deriving the proof.

Trace on balloons [[10,16],[2,8],[1,6],[7,12]], sorted by end: [1,6], [2,8], [7,12], [10,16].

• Arrow at 6 (end of [1,6]): pierces [1,6] and also [2,8], since 2 ≤ 6 ≤ 8. Both skipped. Arrows so far: 1.
• Next unpierced balloon is [7,12], whose start (7) is past the current arrow (6): fire a new arrow at 12. It also pierces [10,16], since 10 ≤ 12 ≤ 16. Arrows so far: 2.
• All balloons pierced. Answer: 2.

def find_min_arrow_shots(points):
    """
    LeetCode 452: Minimum Number of Arrows to Burst Balloons
    NOT LeetCode 312 (Burst Balloons, interval DP) -- see disambiguation above.
    Time: O(n log n) for the sort, O(n) for the scan. Space: O(1) extra.
    """
    if not points:
        return 0

    points = sorted(points, key=lambda p: p[1])
    arrows = 1
    arrow_position = points[0][1]

    for start, end in points[1:]:
        if start > arrow_position:
            # This balloon is not pierced by the current arrow; shoot a new one.
            arrows += 1
            arrow_position = end
        # else: start <= arrow_position <= end, already pierced -- skip.

    return arrows

# Examples
balloons = [[10, 16], [2, 8], [1, 6], [7, 12]]
print("Minimum arrows:", find_min_arrow_shots(balloons))  # Minimum arrows: 2

balloons2 = [[1, 2], [3, 4], [5, 6], [7, 8]]
print("Minimum arrows:", find_min_arrow_shots(balloons2))  # Minimum arrows: 4

#include <iostream>
#include <vector>
#include <algorithm>

int findMinArrowShots(std::vector<std::vector<int>> points) {
    if (points.empty()) return 0;

    std::sort(points.begin(), points.end(),
              [](const std::vector<int>& a, const std::vector<int>& b) {
                  return a[1] < b[1];
              });

    int arrows = 1;
    long arrowPosition = points[0][1];

    for (std::size_t i = 1; i < points.size(); ++i) {
        long start = points[i][0];
        long end = points[i][1];
        if (start > arrowPosition) {
            ++arrows;
            arrowPosition = end;
        }
    }
    return arrows;
}

int main() {
    std::vector<std::vector<int>> balloons{{10, 16}, {2, 8}, {1, 6}, {7, 12}};
    std::cout << "Minimum arrows: " << findMinArrowShots(balloons) << '\n';  // 2

    std::vector<std::vector<int>> balloons2{{1, 2}, {3, 4}, {5, 6}, {7, 8}};
    std::cout << "Minimum arrows: " << findMinArrowShots(balloons2) << '\n';  // 4
}

import java.util.Arrays;

public class MinArrowShots {
    static int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;

        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

        int arrows = 1;
        long arrowPosition = points[0][1];

        for (int i = 1; i < points.length; i++) {
            long start = points[i][0];
            long end = points[i][1];
            if (start > arrowPosition) {
                arrows++;
                arrowPosition = end;
            }
        }
        return arrows;
    }

    public static void main(String[] args) {
        int[][] balloons = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
        System.out.println("Minimum arrows: " + findMinArrowShots(balloons)); // 2

        int[][] balloons2 = {{1, 2}, {3, 4}, {5, 6}, {7, 8}};
        System.out.println("Minimum arrows: " + findMinArrowShots(balloons2)); // 4
    }
}

7. Partition Labels

LeetCode 763. Given a string, split it into as many partitions as possible such that each letter appears in at most one partition. Return the length of each partition, in order.

Plain-English steps:

1. Build a map from each character to the index of its last occurrence in the string.
2. Initialize start = 0 and end = 0 for the current partition.
3. Scan index i from 0 to the end of the string. Set end = max(end, last[s[i]]) — the current partition must stretch at least that far, because the current character cannot appear again in a later partition.
4. If i == end, every character seen so far in this partition has had its last occurrence accounted for, so no future character can force this partition to grow further. Record the partition length end - start + 1, then set start = i + 1 to begin a new partition.

Trace on s = "aabbbacccd". Last occurrences: a→5, b→4, c→8, d→9.

Result: partition lengths [6, 3, 1] — "aabbba", "ccc", "d". The 'a' at index 5 is what forces the first partition to swallow the 'b's in between: without the second 'a', the partitions would have split earlier.

def partition_labels(s):
    """
    LeetCode 763: Partition Labels
    Time: O(n), Space: O(1) extra (at most 26 lowercase letters)
    """
    last_occurrence = {char: i for i, char in enumerate(s)}

    result = []
    start = 0
    end = 0
    for i, char in enumerate(s):
        end = max(end, last_occurrence[char])
        if i == end:
            result.append(end - start + 1)
            start = i + 1

    return result

# Examples
print("Partitions:", partition_labels("aabbbacccd"))  # Partitions: [6, 3, 1]
print("Partitions:", partition_labels("abcabcdeed"))  # Partitions: [6, 4]

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::vector<int> partitionLabels(const std::string& s) {
    int lastOccurrence[26] = {0};
    for (int i = 0; i < static_cast<int>(s.size()); ++i) {
        lastOccurrence[s[i] - 'a'] = i;
    }

    std::vector<int> result;
    int start = 0, end = 0;
    for (int i = 0; i < static_cast<int>(s.size()); ++i) {
        end = std::max(end, lastOccurrence[s[i] - 'a']);
        if (i == end) {
            result.push_back(end - start + 1);
            start = i + 1;
        }
    }
    return result;
}

int main() {
    for (int len : partitionLabels("aabbbacccd")) {
        std::cout << len << ' ';  // 6 3 1
    }
    std::cout << '\n';
}

import java.util.ArrayList;
import java.util.List;

public class PartitionLabels {
    static List<Integer> partitionLabels(String s) {
        int[] lastOccurrence = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastOccurrence[s.charAt(i) - 'a'] = i;
        }

        List<Integer> result = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, lastOccurrence[s.charAt(i) - 'a']);
            if (i == end) {
                result.add(end - start + 1);
                start = i + 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println("Partitions: " + partitionLabels("aabbbacccd")); // [6, 3, 1]
    }
}

8. Complexity Comparison Table

9. Applications & Alternatives

10. Exercises

Easy

1. Run Partition Labels by hand on s = "ecbacbced" and list the resulting partition lengths.

Medium

1. Given gas = [4, 3, 1, 2, 7, 4] and cost = [1, 2, 7, 3, 2, 5], find the starting station using the Gas Station algorithm, and verify by hand-tracing the tank level that it never goes negative from that start.

Hard

1. Suppose Candy adds a rule that no child may receive more than maxCandies candies (a fixed cap). Explain, without writing code, why the simple two-pass greedy can no longer guarantee a valid assignment always exists, and describe at a design level what would need to change (e.g., what makes a rating sequence infeasible under the cap, and whether the answer is still uniquely determined by local neighbor comparisons alone).

Review rhythm: tomorrow, reconstruct all four core insights from memory without looking at the code. Next week, re-implement Gas Station and Partition Labels from scratch and re-derive the Candy two-pass argument out loud. Several weeks later, when you meet a new problem, ask whether it is really the Jump Game / Merge Intervals pattern from Part 16, or one of these four — the fastest way to fail an interview on this family is misidentifying which of the five is in front of you.

11. Summary Cheat Sheet

• Gas Station: total gas ≥ total cost guarantees a start exists; track a running tank, reset the candidate to the next index whenever the tank goes negative.
• Candy: two passes — left-to-right for the left-neighbor rule, right-to-left with max for the right-neighbor rule — never undoing each other.
• Interval Stabbing (Minimum Arrows, LC 452): sort by interval end, greedily place an arrow at the first unpierced balloon's end, skip everything it also pierces. Not the same problem as DP Burst Balloons (LC 312).
• Partition Labels: track each character's last occurrence; a partition closes exactly when the scan index catches up to the running max of last-occurrence indices.
• All four run in $O(n)$ or $O(n \log n)$ time with little to no extra space beyond the output — the hard part is finding the right local invariant, not the code.