17. Greedy and Bit Manipulation

Greedy algorithms make the locally optimal choice at each step, hoping it leads to a globally optimal solution. When it works, greedy is simpler and faster than DP. Bit manipulation uses binary representation to solve problems with O(1) operations that would otherwise require loops or extra space.

When Greedy Works

Greedy works when the greedy choice property holds: making the best local choice at each step produces the best global result. You can't always prove this easily — but there are well-known problem families where greedy is guaranteed to work.

Greedy works for:

• Interval scheduling (activity selection)
• Huffman coding
• Fractional knapsack
• Minimum coins with canonical denominations (US coins)
• Dijkstra's algorithm (it's greedy!)
• MST algorithms (Kruskal's, Prim's)

Greedy fails for:

• 0/1 knapsack → need DP
• Coin change with arbitrary denominations → need DP
• Longest path in general graphs → NP-hard

NP-hard means no known algorithm solves it in polynomial time (O(n²), O(n³), etc.). NP stands for Nondeterministic Polynomial — a complexity class. NP-hard problems are at least as hard as the hardest problems in NP. In practice: don't look for an efficient algorithm, use approximations or restrict the input (e.g., longest path in a DAG is solvable in O(V+E) via topological sort).

Pattern: Interval Scheduling

Given intervals, find the maximum number of non-overlapping intervals. Greedy: always pick the interval that ends earliest.

LeetCode 435 - Non-overlapping Intervals

// Minimum intervals to remove so the rest don't overlap
func eraseOverlapIntervals(intervals [][]int) int {
    // Sort by end time — earliest end first
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })

    // Or with slices.SortFunc (Go 1.21+) — type-safe, compares values directly:
    // slices.SortFunc(intervals, func(a, b []int) int { return a[1] - b[1] })

    keep := 1
    end := intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] >= end { // no overlap — keep it
            keep++
            end = intervals[i][1]
        }
    }
    return len(intervals) - keep // total minus kept = removed
}

Why it works: picking the earliest-ending interval leaves the most room for future intervals. Any other choice can only do worse.

sort.Slice vs slices.SortFunc: sort.Slice compares by index (i, j), works in all Go versions. slices.SortFunc (Go 1.21+) compares by value (a, b) and returns int (<0, 0, >0) — type-safe and reads more naturally. Prefer slices.SortFunc in new code.

// sort.Slice — compare by index
sort.Slice(intervals, func(i, j int) bool {
    return intervals[i][0] < intervals[j][0]
})

// slices.SortFunc — compare by value (Go 1.21+)
slices.SortFunc(intervals, func(a, b []int) int {
    return a[0] - b[0]
})

Pattern: Merge Intervals

LeetCode 56 - Merge Intervals

Given a collection of intervals, merge all overlapping intervals into non-overlapping intervals.

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    merged := [][]int{intervals[0]}
    for i := 1; i < len(intervals); i++ {
        last := merged[len(merged)-1]
        if intervals[i][0] <= last[1] { // overlap
            if intervals[i][1] > last[1] {
                last[1] = intervals[i][1] // extend
            }
        } else {
            merged = append(merged, intervals[i])
        }
    }
    return merged
}

Sort by start, then greedily extend or start new intervals. O(n log n) for the sort.

Pattern: Jump Game

LeetCode 55 - Jump Game

Given an array where each element represents the maximum jump length from that position, determine if you can reach the last index.

func canJump(nums []int) bool {
    maxReach := 0
    for i := 0; i <= maxReach && i < len(nums); i++ {
        if i+nums[i] > maxReach {
            maxReach = i + nums[i]
        }
        if maxReach >= len(nums)-1 {
            return true
        }
    }
    return false
}

Greedy: track the farthest position you can reach. If you can reach beyond the end, return true.

Greedy vs DP — How to Decide

Ask: "If I make the locally best choice, can a later choice make it suboptimal?"

• No → greedy works. Example: interval scheduling — picking earliest end never hurts.
• Yes → need DP. Example: coin change with coins [1, 3, 4] and target 6. Greedy picks 4+1+1=3 coins. DP finds 3+3=2 coins.

When in doubt, try greedy first (it's simpler). If you find a counterexample, switch to DP.

Bit Manipulation

Computers store numbers in binary. Bit operations work on individual bits in O(1) — no loops needed.

Essential Operations

// AND — both bits must be 1
5 & 3   // 101 & 011 = 001 = 1

// OR — either bit is 1
5 | 3   // 101 | 011 = 111 = 7

// XOR — bits must differ
5 ^ 3   // 101 ^ 011 = 110 = 6

// NOT — flip all bits
^5      // ...11111010 (in Go, inverts all bits)

// Left shift — multiply by 2
5 << 1  // 101 << 1 = 1010 = 10

// Right shift — divide by 2
5 >> 1  // 101 >> 1 = 10 = 2

XOR Properties

XOR is the most useful bit operation for DSA:

a ^ a = 0     // anything XOR itself is 0
a ^ 0 = a     // anything XOR 0 is itself
a ^ b ^ a = b // XOR is self-inverse (order doesn't matter)

This gives you a powerful trick: XOR all elements, duplicates cancel out.

LeetCode 136 - Single Number

Given an array where every element appears twice except one, find the unique element.

// Find the single number (all others appear twice) — O(n) time, O(1) space
func singleNumber(nums []int) int {
    result := 0
    for _, n := range nums {
        result ^= n
    }
    return result
}

Without XOR, you'd need a hash map (O(n) space) or sorting (O(n log n) time).

Common Bit Tricks

// Check if n is a power of 2
func isPowerOfTwo(n int) bool {
    return n > 0 && n&(n-1) == 0
}

// Count set bits (number of 1s)
func countBits(n int) int {
    count := 0
    for n > 0 {
        count += n & 1
        n >>= 1
    }
    return count
}

// Get the ith bit
func getBit(n, i int) int {
    return (n >> i) & 1
}

// Set the ith bit
func setBit(n, i int) int {
    return n | (1 << i)
}

// Clear the ith bit
func clearBit(n, i int) int {
    return n & ^(1 << i)
}

Bitmask as Set

Use an integer as a set of flags. Bit i is 1 if element i is in the set. Gives O(1) add, remove, and membership — for sets up to 64 elements.

// Subset representation with bitmask
set := 0
set |= (1 << 3)  // add element 3
set |= (1 << 5)  // add element 5
set &^= (1 << 3) // remove element 3 (&^ is Go's bit-clear operator — clears the specified bit)

// Check membership
if set&(1<<5) != 0 {
    fmt.Println("5 is in the set")
}

// Iterate all subsets of {0, 1, ..., n-1}
for mask := 0; mask < (1 << n); mask++ {
    // mask represents one subset
}

This is used in bitmask DP — when the state is "which elements have been used."

When to Use Bit Manipulation

• Finding unique elements (XOR cancels duplicates)
• Power-of-2 checks
• Compact set representation (bitmask DP)
• Low-level optimization (multiply/divide by 2)
• Permission systems (read=4, write=2, execute=1)

Practice Problems

Key Takeaways

• Greedy makes the locally optimal choice — works when local optimality guarantees global optimality
• Interval problems (scheduling, merging) are the classic greedy family
• If greedy fails (counterexample exists), fall back to DP
• XOR is the key bit operation: a^a=0, a^0=a — finds unique elements in O(1) space
• Bitmasks represent sets as integers — O(1) operations for sets up to 64 elements
• Bit tricks: power-of-2 check (n&(n-1)==0), count bits, get/set/clear individual bits
• Greedy is O(n) or O(n log n). Bit operations are O(1). Both are faster than DP when applicable