MediumNo. 1884
Egg Drop With 2 Eggs and N Floors — LeetCode 1884 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Math, Dynamic Programming
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given two identical eggs and you have access to a building with n floors labeled from 1 to n. You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.
Example
- Input
- n = 2
- Output
- 2
- Explanation
- We can drop the first egg from floor 1 and the second egg from floor 2.
Python solution
class Solution:
def twoEggDrop(self, n: int) -> int:
f = [0] + [inf] * n
for i in range(1, n + 1):
for j in range(1, i + 1):
f[i] = min(f[i], 1 + max(j - 1, f[i - j]))
return f[n]Complexity
- Time
- O(n2)
- Space · auxiliary
- O(n)
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1884. Egg Drop With 2 Eggs and N Floors is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0062 | Unique Paths | Medium |
| 0070 | Climbing Stairs | Easy |
| 0096 | Unique Binary Search Trees | Medium |
| 0233 | Number of Digit One | Hard |
| 0241 | Different Ways to Add Parentheses | Medium |
| 0279 | Perfect Squares | Medium |
Frequently asked questions
- How hard is LeetCode 1884. Egg Drop With 2 Eggs and N Floors?
LeetCode 1884. Egg Drop With 2 Eggs and N Floors is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1884. Egg Drop With 2 Eggs and N Floors?
The Python solution on this page runs in O(n2).
- What is the space complexity of LeetCode 1884. Egg Drop With 2 Eggs and N Floors?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1884. Egg Drop With 2 Eggs and N Floors cover?
LeetCode 1884. Egg Drop With 2 Eggs and N Floors is tagged Math and Dynamic Programming on LeetCode.