# Greedy — Part 2: Interview Problems

Six problems where a local rule provably leads to the global optimum: Kadane, farthest reach, balance resets, last occurrences and smallest-first grouping.

## 1. Maximum Subarray (LeetCode 53)

**🟠 Medium.** Return the largest sum of a non-empty contiguous subarray.

```text
[-2,1,-3,4,-1,2,1,-5,4] → 6   ([4,-1,2,1])
```

**Approach.** Kadane's algorithm: the best subarray ending at i either extends the best one ending at i − 1 or starts fresh at i, whichever is larger. A negative running sum can only hurt what follows, so drop it.

**Complexity.** O(n) time, O(1) space.

```typescript
function maxSubArray(nums: number[]): number {
  let best = nums[0], cur = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    best = Math.max(best, cur);
  }
  return best;
}
```

```python
def max_sub_array(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best
```

## 2. Jump Game (LeetCode 55)

**🟠 Medium.** `nums[i]` is the maximum jump length from index i. Can you reach the last index from index 0?

```text
[2,3,1,1,4] → true · [3,2,1,0,4] → false
```

**Approach.** Scan left to right keeping the farthest reachable index. If you ever stand on an index beyond it, you're stuck.

**Complexity.** O(n) time, O(1) space.

```typescript
function canJump(nums: number[]): boolean {
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;
    reach = Math.max(reach, i + nums[i]);
  }
  return true;
}
```

```python
def can_jump(nums):
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + step)
    return True
```

## 3. Jump Game II (LeetCode 45)

**🟠 Medium.** Return the minimum number of jumps to reach the last index (always reachable).

```text
[2,3,1,1,4] → 2   (0 → 1 → 4)
```

**Approach.** BFS by levels without a queue: the current jump covers indices up to `end`; while scanning them, track the farthest index the **next** jump could reach. When you pass `end`, take a jump and set `end` to that farthest reach.

**Complexity.** O(n) time, O(1) space.

```typescript
function jump(nums: number[]): number {
  let jumps = 0, end = 0, farthest = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === end) { jumps++; end = farthest; }
  }
  return jumps;
}
```

```python
def jump(nums):
    jumps = end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == end:                   # current jump's range is exhausted
            jumps += 1
            end = farthest
    return jumps
```

## 4. Gas Station (LeetCode 134)

**🟠 Medium.** Stations on a circle have `gas[i]`; driving to the next costs `cost[i]`. Return the starting station for a full loop, or −1.

```text
gas = [1,2,3,4,5], cost = [3,4,5,1,2] → 3
```

**Approach.** If total gas < total cost, it's impossible. Otherwise scan once with a running tank; whenever the tank goes negative at station i, no station from the current start through i can work (they'd arrive with even less), so restart from i + 1.

**Complexity.** O(n) time, O(1) space.

```typescript
function canCompleteCircuit(gas: number[], cost: number[]): number {
  let total = 0, tank = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    total += gas[i] - cost[i];
    tank += gas[i] - cost[i];
    if (tank < 0) { start = i + 1; tank = 0; }
  }
  return total < 0 ? -1 : start;
}
```

```python
def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start, tank = i + 1, 0
    return start
```

## 5. Partition Labels (LeetCode 763)

**🟠 Medium.** Split `s` into as many parts as possible so each letter appears in at most one part. Return the part sizes.

```text
"ababcbacadefegdehijhklij" → [9,7,8]
```

**Approach.** Record the last index of every letter. Scan, extending the current part's end to the last occurrence of each letter seen; when the index reaches the end, close the part.

**Complexity.** O(n) time, O(26) space.

```typescript
function partitionLabels(s: string): number[] {
  const last = new Map<string, number>();
  for (let i = 0; i < s.length; i++) last.set(s[i], i);
  const sizes: number[] = [];
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last.get(s[i])!);
    if (i === end) { sizes.push(end - start + 1); start = i + 1; }
  }
  return sizes;
}
```

```python
def partition_labels(s):
    last = {c: i for i, c in enumerate(s)}
    sizes, start, end = [], 0, 0
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            sizes.append(end - start + 1)
            start = i + 1
    return sizes
```

## 6. Hand of Straights (LeetCode 846)

**🟠 Medium.** Can the cards be split into groups of `groupSize` consecutive values?

```text
[1,2,3,6,2,3,4,7,8], groupSize 3 → true   ([1,2,3],[2,3,4],[6,7,8])
```

**Approach.** The smallest remaining card must start a group (nothing smaller can cover it). Count cards, iterate values in sorted order, and for each value with remaining count c, consume c copies of the next `groupSize − 1` consecutive values; fail if any is short.

**Complexity.** O(n log n) time for sorting the distinct values.

```typescript
function isNStraightHand(hand: number[], groupSize: number): boolean {
  if (hand.length % groupSize) return false;
  const count = new Map<number, number>();
  for (const x of hand) count.set(x, (count.get(x) ?? 0) + 1);
  for (const x of [...count.keys()].sort((a, b) => a - b)) {
    const c = count.get(x)!;
    if (c === 0) continue;
    for (let v = x; v < x + groupSize; v++) {
      if ((count.get(v) ?? 0) < c) return false;
      count.set(v, count.get(v)! - c);
    }
  }
  return true;
}
```

```python
def is_n_straight_hand(hand, group_size):
    if len(hand) % group_size:
        return False
    count = {}
    for x in hand:
        count[x] = count.get(x, 0) + 1
    for x in sorted(count):
        c = count[x]
        if c == 0:
            continue
        for v in range(x, x + group_size):
            if count.get(v, 0) < c:
                return False
            count[v] -= c
    return True
```