07 — Greedy, Intervals, Bit Manipulation, Math#

# Jump Game: can you reach the last index?
def can_jump(nums):
    reach = 0
    for i, x in enumerate(nums):
        if i > reach: return False       # a gap we can't cross
        reach = max(reach, i + x)
    return True
# O(n) — track the furthest reachable index
 
# Jump Game II: minimum jumps to reach the end
def jump(nums):
    jumps = curr_end = furthest = 0
    for i in range(len(nums) - 1):
        furthest = max(furthest, i + nums[i])
        if i == curr_end:                # exhausted the current jump's range
            jumps += 1
            curr_end = furthest
    return jumps
# This is BFS by levels, expressed without a queue.
 
# Gas Station: find the start index enabling a full circuit
def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost): return -1   # a solution must exist if total >= 0
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:                     # can't reach i+1 from `start`
            start = i + 1                # ...nor from anything between them
            tank = 0
    return start

# Hand of Straights / Divide Array in Sets of K Consecutive
from collections import Counter
import heapq
def is_n_straight_hand(hand, group_size):
    if len(hand) % group_size: return False
    count = Counter(hand)
    for x in sorted(count):               # always start from the smallest
        c = count[x]
        if c > 0:
            for k in range(x, x + group_size):
                if count[k] < c: return False
                count[k] -= c
    return True

# Merge Intervals
def merge(intervals):
    intervals.sort(key=lambda x: x[0])            # by start
    out = []
    for start, end in intervals:
        if out and start <= out[-1][1]:           # overlaps the last merged
            out[-1][1] = max(out[-1][1], end)     # extend it
        else:
            out.append([start, end])
    return out
# O(n log n)
 
# Insert Interval — input is already sorted and non-overlapping
def insert(intervals, new):
    out = []
    i, n = 0, len(intervals)
    while i < n and intervals[i][1] < new[0]:     # entirely before new
        out.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= new[1]:    # overlapping — absorb
        new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]
        i += 1
    out.append(new)
    out.extend(intervals[i:])                     # entirely after
    return out
# O(n), no sort needed
 
# Non-overlapping Intervals: minimum removals to eliminate all overlaps
def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])            # by END — interval scheduling
    count = 0
    prev_end = float('-inf')
    for start, end in intervals:
        if start >= prev_end:
            prev_end = end                        # keep it
        else:
            count += 1                            # drop it (it ends later)
    return count

# Meeting Rooms II — minimum rooms required
def min_meeting_rooms(intervals):
    starts = sorted(i[0] for i in intervals)
    ends   = sorted(i[1] for i in intervals)
    rooms = best = 0
    s = e = 0
    while s < len(starts):
        if starts[s] < ends[e]:
            rooms += 1                  # a meeting begins before one ends
            best = max(best, rooms)
            s += 1
        else:
            rooms -= 1                  # a meeting ended, free a room
            e += 1
    return best
# O(n log n)

# Number of 1 Bits — Brian Kernighan's algorithm
def hamming_weight(n):
    count = 0
    while n:
        n &= n - 1          # remove one set bit per iteration
        count += 1
    return count
# O(number of set bits), not O(32)
 
# Counting Bits: popcount for every number 0..n, in O(n)
def count_bits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)     # same as i//2, plus the last bit
    return dp
# DP + bits — a nice combination they like

# Rotate Image 90° clockwise, in place
def rotate(matrix):
    matrix.reverse()                             # 1. flip vertically
    for i in range(len(matrix)):                 # 2. transpose
        for j in range(i + 1, len(matrix)):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Reverse-then-transpose = rotate clockwise.
# Transpose-then-reverse-each-row = also clockwise. Know one, derive the other.
 
# Spiral Matrix — shrink four boundaries
def spiral_order(matrix):
    out = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1): out.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1): out.append(matrix[r][right])
        right -= 1
        if top <= bottom:                        # guard: single row remaining
            for c in range(right, left - 1, -1): out.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:                        # guard: single column
            for r in range(bottom, top - 1, -1): out.append(matrix[r][left])
            left += 1
    return out

# Set Matrix Zeroes in O(1) space — use row 0 and column 0 as marker storage
def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_col_zero = any(matrix[r][0] == 0 for r in range(rows))
    for r in range(rows):
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = matrix[0][c] = 0       # mark in the margins
    for r in range(rows - 1, -1, -1):                 # fill BACKWARD so the
        for c in range(cols - 1, 0, -1):              # markers survive
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0
        if first_col_zero:
            matrix[r][0] = 0