Egg Dropping: Min Outside, Max Inside

Scrambled String needed an extra dimension because a substring couldn't be pinned down by position alone, it also needed a length. Egg Dropping needs something different again: the partition point k isn't a place in a string this time, it's an actual floor of a building, and for the first time in this series, the combining step has to account for the fact that you don't get to see the outcome of your own choice before committing to it.

The Problem

You have E eggs and a building with F floors. There's some unknown threshold floor: eggs dropped from it or below survive, eggs dropped above it break. You want to find that threshold using as few drops as possible, but you have to plan for the worst case, since you don't know in advance which floor the threshold actually is.

Floor:   1  2  3  4  5  6  7  8  9  10
         ok ok ok ok ok break break break break break

Here the threshold is floor 5. The egg survives dropped from there, and breaks from floor 6 onward. If you tested floors one at a time starting from the bottom, you could end up needing all the way up to F drops in the worst case, since the threshold could turn out to be the very last floor you try. The goal is a strategy that guarantees finding the threshold using as few worst-case attempts as possible.

Picking a Floor to Test

Say you drop an egg from floor k. There are exactly two outcomes, and each one tells you something different about where the threshold has to be.

          10
           9
           8
           7
           6
          --------------
           5   <- drop here
          --------------
           4
           3
           2
           1

The egg breaks. The threshold has to be below k. Every floor at k and above is now known to break, so the search space shrinks to floors 1 through k-1. You've also used up one of your eggs, since it just broke, so you're left with E-1 eggs and k-1 floors still to search.

subproblem: solve(E - 1, k - 1)

The egg survives. The threshold has to be at k or above. Floors below k are ruled out, and the search space becomes k+1 through F, a span of F-k floors. Since the egg survived, you still have all E eggs, just fewer floors left to check.

subproblem: solve(E, F - k)

                     Drop at k
                         |
              +----------+----------+
              |                     |
            Break                No Break
              |                     |
        E - 1 eggs                E eggs
        k - 1 floors             F - k floors
              |                     |
       solve(E-1, k-1)         solve(E, F-k)

Here's the part that's genuinely new compared to every problem earlier in this series. You don't get to choose which of these two outcomes happens. The egg either breaks or it doesn't, and you have no control over that, and no way to know in advance. So whatever strategy you commit to has to be judged by its worst possible outcome, not its best one. That means the two branches get combined with max, not the min or the sum seen in earlier chapters:

1 + max(solve(E - 1, k - 1), solve(E, F - k))

The +1 accounts for the drop you just made, which counts as one attempt regardless of which way it goes.

Why This Still Looks Like MCM

The core move is identical to every problem in this series so far: try every possible partition point, solve two subproblems, combine them. What's different is the shape of the combination.

for k in range(1, F + 1):

Every earlier problem in this family picked the best partition using a min over k. Egg Dropping does that too, but with a twist: at each individual k, you first have to brace for the worse of the two outcomes with max, and only after that do you compare across different values of k with min, looking for whichever floor gives the smallest worst-case guarantee.

                   MIN (choose the best floor)
                    |
       +------------+------------+
       k=1         k=2          k=3 ...
        |            |             |
      MAX          MAX           MAX  (brace for the worse outcome)
     /    \        /    \        /    \
 break  survive  break  survive break  survive

That min-outside, max-inside structure is the actual signature of this problem, and it's worth naming explicitly, because it's the piece that's genuinely new. Every earlier problem in this series only ever needed one of the two: MCM and Palindrome Partitioning only needed min, Boolean Parenthesization only needed sums, Scrambled String only needed a boolean or. This is the first one that needs both a min and a max at once, nested inside each other, because you're optimizing a strategy against an adversary you can't predict.

dp(E, F) = min over 1 <= k <= F of { 1 + max(dp(E - 1, k - 1), dp(E, F - k)) }

The Base Cases

Three conditions end the recursion.

No floors left (F == 0): nothing to test, zero attempts needed.

One floor left (F == 1): there's nothing to narrow down, one drop settles it, so it's one attempt either way.

Down to one egg (E == 1): this one is worth sitting with, because it's the case where the whole partitioning strategy stops being available to you. With only one egg left, you can no longer afford the risk of testing high up and having it break, since a single break with no eggs left in reserve means you can't continue testing at all. The only safe strategy left is testing floors one at a time from the bottom, which means the worst case is F attempts, testing every floor in sequence until you find the one that breaks.

if F == 0 or F == 1:
    return F

if E == 1:
    return F

The Recursive Solution

class Solution:

    def solve(self, E, F):

        if F == 0 or F == 1:
            return F

        if E == 1:
            return F

        ans = float('inf')

        for k in range(1, F + 1):

            break_case = self.solve(E - 1, k - 1)
            no_break_case = self.solve(E, F - k)

            attempts = 1 + max(break_case, no_break_case)

            ans = min(ans, attempts)

        return ans

    def eggDrop(self, E, F):
        return self.solve(E, F)

A Small Example: E = 2, F = 3

Try dropping at floor k = 2.

If it breaks: one egg left, one floor left below (floor 1) to check. solve(1, 1) = 1 attempt.

If it survives: two eggs still available, one floor left above (floor 3) to check. solve(2, 1) = 1 attempt.

attempts at k = 2 = 1 + max(1, 1) = 2

With 2 eggs and 3 floors, dropping first at floor 2 guarantees finding the threshold in at most 2 attempts, regardless of which way that first drop goes.

Two Ways to Represent the Same State

Just like Scrambled String had a dictionary version and an index-based version describing the same subproblem, Egg Dropping has an equivalent choice, whether to model floors as an explicit range (i, j) or as a simple count F.

Explicit interval: solve(E, i, j), tracking the actual floor boundaries. A partition at k splits the break case into i through k-1 and the survive case into k+1 through j.

min over i <= k <= j of { 1 + max(solve(E - 1, i, k - 1), solve(E, k + 1, j)) }

Relative span: solve(E, F), tracking only how many untested floors remain, not their absolute labels.

The reason the simpler version works here, and it's a genuinely useful thing to notice, is that this problem doesn't care which specific floors remain, only how many. Floors 4 through 10 behave identically to floors 1 through 7 as far as the strategy is concerned, since nothing about the problem references a floor's absolute position, only the count of floors still left to search. That's different from something like Palindrome Partitioning, where the actual characters at each position mattered, not just how many characters were left. Because Egg Dropping's subproblems only ever depend on a count, the 2D state (E, F) is already complete, with no need for the extra index bookkeeping that Scrambled String's length dimension required.

Memoization: A 2D Table

Since only two things change between subproblems, the number of eggs and the number of remaining floors, an (E+1) x (F+1) table covers the entire state space.

        F ->
E |    0  1  2  3  4  5 ...
      ---------------------
  1  |
  2  |
  3  |
  4  |

class Solution:

    def solve(self, E, F, T):

        if F == 0 or F == 1:
            return F

        if E == 1:
            return F

        if T[E][F] != -1:
            return T[E][F]

        ans = float('inf')

        for k in range(1, F + 1):

            break_case = self.solve(E - 1, k - 1, T)
            no_break_case = self.solve(E, F - k, T)

            attempts = 1 + max(break_case, no_break_case)

            ans = min(ans, attempts)

        T[E][F] = ans

        return T[E][F]

    def eggDrop(self, E, F):

        T = [[-1] * (F + 1) for _ in range(E + 1)]

        return self.solve(E, F, T)

This is the same memoization pattern from every earlier chapter, check before computing, store after, just keyed on (E, F) instead of (i, j).

The Interval DP Family, Side by Side

Every row in this table shares the same skeleton, boundaries, a loop over k, two subproblems, a combining rule. What's actually been changing chapter to chapter is entirely in the last two or three columns: what the subproblems represent, how they combine, and how many dimensions the state needs to carry. Egg Dropping's real contribution to this table isn't a new kind of partitioning, it's the first appearance of max inside the combination step, sitting underneath the min that every other row in this table already had.

Quick Revision

Egg Dropping
     |
Choose a floor k
     |
     +-----------------------+
     |                       |
   BREAK                  SURVIVE
     |                       |
 E - 1 eggs              E eggs
 k - 1 floors            F - k floors
     |                       |
     +----------+------------+
                |
        max(break, survive)
                |
          + 1 attempt
                |
      try every possible k
                |
             minimum

Base cases:
  F == 0 or F == 1  -> return F
  E == 1            -> return F (must test bottom-up)

Recurrence:
  dp(E, F) = min over k of { 1 + max(dp(E-1, k-1), dp(E, F-k)) }

"min outside, max inside" is the signature of this problem, and more broadly, of interval DP problems where you're minimizing a worst-case guarantee rather than a straightforward cost. The min picks the best strategy available to you. The max accounts for the fact that once you've picked, the outcome isn't yours to control.

What You Now Understand

Egg Dropping keeps the exact partitioning skeleton this whole series has been building on, but it's the first problem where the two subproblems on either side of the split aren't both under your control. One of them happens to you, not because you chose it. That's why max shows up nested inside the min here for the first time: the outer min is you picking the best strategy, and the inner max is bracing for whichever of the two outcomes turns out worse, since you don't get to decide which one you get.