Greedy

1. Jump Game Medium

Problem

You stand on index 0 of an array. Each value nums[i] is the longest jump allowed from index i. Shorter jumps are also allowed. Return whether you can reach the last index.

Approach

• Do not choose a jump. Track reach, the farthest index that any route can land on so far.
• Walk left to right. If the current index is beyond reach, no route gets here, so the answer is false.
• Otherwise extend reach to i + nums[i] if that is farther.
• Why it is safe: every index up to reach is reachable, because you can always jump short. So one number sums up all routes.

Solution

public static class JumpGame
{
    /// <summary>Whether the last index is reachable from index 0.</summary>
    /// <param name="nums">Non-negative jump lengths. nums[i] is the longest jump from i.</param>
    /// <returns>True if some sequence of jumps lands on the last index.</returns>
    /// <example><c>JumpGame.CanJump([2, 3, 1, 1, 4])</c> returns true.
    /// <c>JumpGame.CanJump([3, 2, 1, 0, 4])</c> returns false.</example>
    public static bool CanJump(int[] nums)
    {
        // reach: the farthest index any route found so far can land on.
        // 0: we start on index 0, so it is reachable for free.
        int reach = 0;

        // i is the index we stand on. 0: start where we stand.
        // Invariant: every index 0..reach is reachable using nums[0..i-1].
        for (int i = 0; i < nums.Length; i++)
        {
            // i beyond reach: no earlier index can hop this far. i is a wall.
            if (i > reach)
            {
                return false;
            }

            // From i we can land anywhere up to i + nums[i]. Keep the farther reach.
            reach = Math.Max(reach, i + nums[i]);
        }

        // We never hit a wall, so the last index, nums.Length - 1, was reached.
        return true;
    }
}

Walkthrough

nums = [3, 2, 1, 0, 4]:

• i = 0, jump 3: reach becomes 3.
• i = 1, jump 2: 1 + 2 = 3, reach stays 3.
• i = 2, jump 1: 2 + 1 = 3, reach stays 3.
• i = 3, jump 0: reach stays 3. Every route ends here.
• i = 4: 4 > 3, a wall. Return false.

Reading the figure. Each blue arc is the longest jump from its index, ending at i + nums[i]. All three arcs land on index 3, the amber cell with jump 0. The green bar is reach. Index 4, in red, sits past the bar, so the loop returns false there.

The follow-up: fewest jumps

public static class JumpGameII
{
    /// <summary>Jump Game II: fewest jumps to reach the last index.</summary>
    /// <param name="nums">Non-negative jump lengths. The last index is reachable.</param>
    /// <returns>The minimum number of jumps.</returns>
    /// <example><c>JumpGameII.MinJumps([2, 3, 1, 1, 4])</c> returns 2.</example>
    public static int MinJumps(int[] nums)
    {
        int jumps = 0;          // 0: no jumps taken yet
        int windowEnd = 0;      // 0: with zero jumps we can only be on index 0
        int farthest = 0;       // 0: farthest index reachable with one more jump

        // Stop before the last index: nums.Length - 1. Standing on it needs no jump.
        // Invariant: indexes up to windowEnd are reachable in `jumps` jumps.
        for (int i = 0; i < nums.Length - 1; i++)
        {
            farthest = Math.Max(farthest, i + nums[i]);  // best landing from this window

            // i == windowEnd: this window is used up. Take one more jump.
            if (i == windowEnd)
            {
                jumps += 1;              // 1: one jump moves us to the next window
                windowEnd = farthest;    // the next window ends at the best landing
            }
        }

        return jumps;
    }
}

This is BFS by levels without a queue. Each window is one level. Say that link out loud.

Edge cases to raise

• One element: already on the last index. Returns true.
• A 0 at index 0 with more elements: stuck at once. The loop returns false at i = 1.
• A 0 in the middle is only a problem if nothing jumps over it.
• Overflow: i + nums[i] wraps negative if a jump is near int.MaxValue. Then reach stops growing and the answer is wrong. Add in long or stop early.
• Early exit: you can return true as soon as reach >= nums.Length - 1. Same big-O, faster in practice.

2. Gas Station Medium

Problem

n stations sit on a circle. Station i gives gas[i] fuel, and driving to station i + 1 costs cost[i]. You start with an empty tank. Return the start index that lets you drive one full loop, or -1. The answer is unique if it exists.

Approach

• Fact 1. If total gas is less than total cost, no start works. Return -1.
• Fact 2. Start at start and suppose the tank goes negative after station i. Then no station from start to i can be the answer. Each one is reached with a tank of at least zero, so starting there with zero is no better.
• So on failure, jump the candidate to i + 1 and reset the tank. One pass.
• Fact 1 guarantees the last candidate standing works for the wrap-around part too.

Solution

public static class GasStation
{
    /// <summary>Start station for one full loop, or -1 if none exists.</summary>
    /// <param name="gas">Fuel gained at each station.</param>
    /// <param name="cost">Fuel spent driving from station i to station i + 1.</param>
    /// <returns>The unique valid start index, or -1.</returns>
    /// <example><c>GasStation.CanCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])</c>
    /// returns 3.</example>
    public static int CanCompleteCircuit(int[] gas, int[] cost)
    {
        // Each station needs a matching cost. A length mismatch is a caller bug.
        if (gas.Length != cost.Length)
        {
            throw new ArgumentException("gas and cost must have the same length");
        }

        // Sum in long: int Sum() throws OverflowException on large inputs.
        // Less fuel than distance overall: no start can work. -1 means "none".
        if (gas.Sum(g => (long)g) < cost.Sum(c => (long)c))
        {
            return -1;
        }

        int start = 0;     // 0: the first candidate is station 0
        long tank = 0;     // 0: we arrive at the candidate with an empty tank

        // i is the station we leave from. 0: begin at the first candidate.
        // Invariant: tank is the fuel left after driving from start through i - 1,
        // and it never dropped below 0 on the way.
        for (int i = 0; i < gas.Length; i++)
        {
            tank += gas[i] - cost[i];   // fill up at i, then pay the drive to i + 1

            // Below 0: start cannot reach i + 1. Nor can any station between
            // start and i, since each was reached with tank >= 0 and still failed.
            if (tank < 0)
            {
                start = i + 1;          // + 1: the next station is the first fresh hope
                tank = 0;               // 0: restart with an empty tank
            }
        }

        // Total fuel covers total cost, so the last surviving start completes the loop.
        return start;
    }
}

Walkthrough

gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]. Net per station is [-2, -2, -2, 3, 3]. Totals are 15 and 15, so an answer exists.

• i = 0: tank -2. Fail. Start moves to 1.
• i = 1: tank -2. Fail. Start moves to 2.
• i = 2: tank -2. Fail. Start moves to 3.
• i = 3: tank 3.
• i = 4: tank 6. Loop ends. Return 3.

Reading the figure. Each column is one station. Red bars are a tank that went below zero. Each red bar resets the tank and moves start one past the failure. Green bars are a tank that stayed at zero or above. The green station cell is the answer, the last start that never failed.

Edge cases to raise

• One station: works if gas[0] >= cost[0], and the code returns 0.
• Totals exactly equal: an answer still exists. That is why the check is <, not <=.
• The brute force tries every start, O(n²). Mention it first, then the skip that makes it linear.
• The two Sum calls are a second pass. You can fold them into the loop as a running total if asked.
• Big inputs: Enumerable.Sum on int runs in a checked context and throws OverflowException. So the code sums as long.
• Different array lengths: the code throws ArgumentException instead of reading past the end.

3. Partition Labels Medium

Problem

Split a string into as many parts as possible so that each letter appears in at most one part. Return the sizes of the parts, in order.

Approach

• First pass: record the last index of every letter.
• Second pass: the current part must stretch to the last index of every letter in it. Keep end as the farthest such index.
• When i reaches end, every letter in the part is finished. Cut right there.
• Why cutting early is safe: any valid split must cut at or after end. Cutting at end leaves the most room for later parts, so it can only add parts.

Solution

public static class PartitionLabels
{
    /// <summary>Sizes of the most parts where no letter spans two parts.</summary>
    /// <param name="s">The string to split. Lowercase letters a to z.</param>
    /// <returns>Part sizes, left to right. They sum to s.Length.</returns>
    /// <example><c>PartitionLabels.Sizes("ababcbacadefegdehijhklij")</c>
    /// returns [9, 7, 8].</example>
    public static List<int> Sizes(string s)
    {
        // last[c - 'a']: the final index of letter c. A part holding c must reach it.
        // 26: one slot per lowercase letter. An array beats a Dictionary here.
        var last = new int[26];

        // Later indexes overwrite earlier ones, so each slot ends with the last index.
        for (int i = 0; i < s.Length; i++)   // 0: scan from the first letter
        {
            last[s[i] - 'a'] = i;            // - 'a': map 'a'..'z' to 0..25
        }

        var sizes = new List<int>();
        int start = 0;    // 0: the first part begins at index 0
        int end = 0;      // 0: so far the part only has to reach index 0

        // i is the index we read. 0: start at the first letter.
        // Invariant: end is the farthest last-index of any letter in s[start..i].
        for (int i = 0; i < s.Length; i++)
        {
            end = Math.Max(end, last[s[i] - 'a']);   // this letter may push the cut later

            // i == end: every letter in this part is finished. Cut here.
            if (i == end)
            {
                sizes.Add(end - start + 1);   // + 1: both ends are inclusive
                start = i + 1;                // + 1: the next part starts after i
            }
        }

        return sizes;
    }
}

Walkthrough

s = "ababcbacadefegdehijhklij":

• Index 0, a: last a is at 8, so end = 8.
• Indexes 1 to 7: b ends at 5, c at 7. Neither passes 8.
• Index 8: i == end. Cut. Size 8 - 0 + 1 = 9.
• Index 9, d: ends at 14. Then e at 15 pushes end to 15. Cut at 15, size 7.
• Index 16, h: ends at 19. Then i (last at 22) and j (last at 23) push end to 23. Cut at 23, size 8.

Reading the figure. Each cell is one letter, with its index below. Amber cells are last copies that set or push end. The label above each part shows how end grew. A red line is a cut, made the moment i == end. The green numbers are the answer.

Edge cases to raise

• Empty string: returns [].
• All letters distinct: every part has size 1.
• First letter equals last letter: one part, the whole string.
• Space is O(1) for lowercase letters only. Say O(k) for an alphabet of size k. For any characters, swap the int[26] for a Dictionary<char, int>.

4. Task Scheduler Medium

Problem

A CPU runs tasks given as letters. Each slot runs one task or stays idle. Two runs of the same task need at least n slots between them. Return the fewest slots needed to run every task. Order is free.

Approach

• The most frequent task decides the shape. Say A appears top times. Lay it out in top rows, one A per row.
• Each row except the last is n + 1 slots wide: the A plus n cooling slots.
• The last row holds every task tied for top. That gives (top - 1) * (n + 1) + ties.
• Other tasks fill the cooling gaps. If there are more tasks than gaps, the rows just get wider and nothing idles. Then the answer is tasks.Length.
• So the answer is the larger of those two numbers.

Solution

public static class TaskScheduler
{
    /// <summary>Fewest CPU slots to run all tasks with cooldown n between repeats.</summary>
    /// <param name="tasks">Task labels, uppercase 'A' to 'Z'. Repeats are allowed.</param>
    /// <param name="n">Minimum number of slots between two runs of the same task.</param>
    /// <returns>The minimum total slots, idle slots included.</returns>
    /// <example><c>TaskScheduler.LeastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 2)</c>
    /// returns 8.</example>
    public static int LeastInterval(char[] tasks, int n)
    {
        // No tasks: no slots. 0 also keeps Max() below off an empty count.
        if (tasks.Length == 0)
        {
            return 0;
        }

        // counts[c - 'A']: how often task c appears. 26: one slot per letter.
        var counts = new int[26];
        foreach (char task in tasks)
        {
            counts[task - 'A']++;        // - 'A': map 'A'..'Z' to 0..25
        }

        // top: how many times the most common task must run.
        int top = counts.Max();
        // ties: how many tasks share that top count. They all sit in the last row.
        int ties = counts.Count(count => count == top);

        // top - 1: full rows. The last row needs no cooldown after it.
        // n + 1: each full row is the task plus n cooling slots.
        int frame = (top - 1) * (n + 1) + ties;

        // Too many tasks to fit the gaps: rows widen, no idle, answer = task count.
        return Math.Max(frame, tasks.Length);
    }
}

Walkthrough

tasks = A A A B B B, n = 2:

• top = 3 (A and B each appear 3 times). ties = 2.
• Full rows: top - 1 = 2, each n + 1 = 3 wide. That is 6 slots.
• Last row: A B, 2 slots. Frame is 8.
• Schedule: A B idle | A B idle | A B. 6 tasks fit, so Math.Max(8, 6) = 8.
• With n = 0 the frame is 2 * 1 + 2 = 4, below 6. No cooldown means no idle, so the answer is 6.

Reading the figure. Each row starts with A and is n + 1 slots wide. So n slots always sit between two runs of A. Dashed cells are idle slots that nothing could fill. The green last row holds the tied tasks. The bottom strip is the same schedule read left to right.

public static class TaskSchedulerSim
{
    /// <summary>Task Scheduler by simulation: run the task with the most runs left.</summary>
    /// <param name="tasks">Task labels, uppercase 'A' to 'Z'.</param>
    /// <param name="n">Minimum number of slots between two runs of the same task.</param>
    /// <returns>The minimum total slots, idle slots included.</returns>
    /// <example><c>TaskSchedulerSim.LeastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 2)</c>
    /// returns 8.</example>
    public static int LeastInterval(char[] tasks, int n)
    {
        // 26: one count per letter. - 'A' maps 'A'..'Z' to 0..25.
        var counts = new int[26];
        foreach (char task in tasks)
        {
            counts[task - 'A']++;
        }

        // PriorityQueue is a min-heap. Priority -count puts the biggest count first.
        var ready = new PriorityQueue<int, int>();
        foreach (int count in counts)
        {
            if (count > 0)                    // 0: letters that never appear stay out
            {
                ready.Enqueue(count, -count);
            }
        }

        // cooling: tasks waiting out their cooldown, oldest first. Queue is FIFO.
        var cooling = new Queue<(int Left, int ReadyAt)>();
        int time = 0;                         // 0: no slot used yet

        // Each pass is one slot.
        // Invariant: every task is either in ready, in cooling, or finished.
        while (ready.Count > 0 || cooling.Count > 0)
        {
            time += 1;                        // 1: this pass fills one slot

            // Run the task with the most runs left. No task ready means an idle slot.
            if (ready.TryDequeue(out int left, out _) && left - 1 > 0)
            {
                // - 1: one run done. + n: it may run again n slots from now.
                cooling.Enqueue((left - 1, time + n));
            }

            // The oldest cooling task finished its wait. Put it back in the heap.
            if (cooling.Count > 0 && cooling.Peek().ReadyAt == time)
            {
                var (back, _) = cooling.Dequeue();
                ready.Enqueue(back, -back);
            }
        }

        return time;
    }
}

Edge cases to raise

• n = 0: the answer is always tasks.Length, and Math.Max handles it.
• One task type repeated k times: (k - 1) * (n + 1) + 1.
• Many distinct tasks: the gaps overflow and the answer is tasks.Length. Many candidates miss this case.
• Empty array: returns 0 from the guard. Without it, top is 0 and all 26 empty slots tie, so the frame is wrong.
• Labels outside 'A'..'Z': task - 'A' falls outside the array and throws IndexOutOfRangeException. Use a Dictionary<char, int> for open alphabets.