887. Super Egg Drop

At a Glance

• Topic: dp-2d
• Pattern: Dynamic Programming + binary search on answer — egg-drop / DP over moves
• Difficulty: Hard
• Companies: Google, Amazon, Adobe, MathWorks, Cisco
• Frequency: Medium
• LeetCode: 887

Problem (one-liner)

You have numberEggs identical eggs and numberFloors in a building (1..numberFloors). An egg breaks at or above critical floor F, survives below. Minimize worst-case number of drops in an adaptive strategy to determine F.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• Worst-case minimization — minimax / DP over strategies
• Constraint eggs × binary search on floors naively wrong — need optimal partition
• Reformulate: how tall can we distinguish with moves drops and eggs eggs?

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Classic DP drops[floor][egg] — O(k * n^2) — too slow for large n.
• DP over moves: maxFloors[moves][eggs] = tallest building solvable — recurrence 1 + broken + survived — inner loop O(1) per cell → O(k * log n) moves search — optimal.

Optimal Solution

Go

func superEggDrop(numberEggs int, numberFloors int) int {
	// maxFloors[moves][eggs] = max floors we can distinguish with this many moves and eggs
	maxFloors := make([][]int, numberFloors+1)
	for move := range maxFloors {
		maxFloors[move] = make([]int, numberEggs+1)
	}
	for moves := 1; moves <= numberFloors; moves++ {
		for eggs := 1; eggs <= numberEggs; eggs++ {
			// One drop: egg breaks -> fewer eggs below; survives -> same eggs above
			maxFloors[moves][eggs] = 1 + maxFloors[moves-1][eggs-1] + maxFloors[moves-1][eggs]
		}
		if maxFloors[moves][numberEggs] >= numberFloors {
			return moves
		}
	}
	return numberFloors
}

JavaScript

function superEggDrop(numberEggs, numberFloors) {
  const maxFloors = Array.from({ length: numberFloors + 1 }, () =>
    new Array(numberEggs + 1).fill(0)
  );
  for (let moves = 1; moves <= numberFloors; moves += 1) {
    for (let eggs = 1; eggs <= numberEggs; eggs += 1) {
      maxFloors[moves][eggs] =
        1 + maxFloors[moves - 1][eggs - 1] + maxFloors[moves - 1][eggs];
    }
    if (maxFloors[moves][numberEggs] >= numberFloors) {
      return moves;
    }
  }
  return numberFloors;
}

Walkthrough

Each drop either breaks (lose egg, recurse below) or not (same eggs, recurse above). Summable floors with moves-1 leftover yields recurrence.

Invariant: maxFloors[moves][eggs] counts distinguishable critical floors for some adaptive strategy.

Edge Cases

• numberFloors <= 1 — answer 1 or 0 per definition (typically n>=1, eggs>=1)
• numberEggs == 1 — must linear scan — equals numberFloors drops worst case

Pitfalls

• Confusing min moves for fixed strategy class with wrong recurrence order
• O(k * n^2) classic DP — times out on LeetCode hard constraints without moves reformulation

Similar Problems

• 312. Burst Balloons — minimax split intuition (Hard)
• 410. Split Array Largest Sum — binary search on worst segment (Hard)
• 174. Dungeon Game — survival / worst-path DP skin (Hard)

Variants

• Egg drop with cost per floor — weighted minimax
• Two eggs classic — closed form / optimized search
• Online / adversarial — competitive analysis twist

Mind-Map Tags

#egg-drop #minimax #dp-on-moves #reverse-state-count #binary-search-floor