Bob is stuck in a dungeon and must break n locks, each requiring some amount of energy to break. The required energy for each lock is stored in an array called strength where strength[i] indicates the energy needed to break the ith lock.
To break a lock, Bob uses a sword with the following characteristics:
X by which the energy of the sword increases is 1.X.ith lock, the energy of the sword must reach at least strength[i].X increases by 1.Your task is to determine the minimum time in minutes required for Bob to break all n locks and escape the dungeon.
Return the minimum time required for Bob to break all n locks.
Example 1:
Input: strength = [3,4,1]
Output: 4
Explanation:
| Time | Energy | X | Action | Updated X |
|---|---|---|---|---|
| 0 | 0 | 1 | Nothing | 1 |
| 1 | 1 | 1 | Break 3rd Lock | 2 |
| 2 | 2 | 2 | Nothing | 2 |
| 3 | 4 | 2 | Break 2nd Lock | 3 |
| 4 | 3 | 3 | Break 1st Lock | 3 |
The locks cannot be broken in less than 4 minutes; thus, the answer is 4.
Example 2:
Input: strength = [2,5,4]
Output: 6
Explanation:
| Time | Energy | X | Action | Updated X |
|---|---|---|---|---|
| 0 | 0 | 1 | Nothing | 1 |
| 1 | 1 | 1 | Nothing | 1 |
| 2 | 2 | 1 | Break 1st Lock | 2 |
| 3 | 2 | 2 | Nothing | 2 |
| 4 | 4 | 2 | Break 3rd Lock | 3 |
| 5 | 3 | 3 | Nothing | 3 |
| 6 | 6 | 3 | Break 2nd Lock | 4 |
The locks cannot be broken in less than 6 minutes; thus, the answer is 6.
Constraints:
n == strength.length1 <= n <= 801 <= strength[i] <= 106n == strength.lengthProblem Overview: You are given an array strength where each value represents the effort required to break a lock. Your sword starts with power 1. Breaking a lock takes ceil(strength[i] / power) time. After each lock is broken, the sword power increases by k. The challenge is choosing the order of locks so the total time is minimized.
Approach 1: Brute Force Permutation with DFS (O(n!))
The direct idea is to try every possible order of breaking locks. Use depth-first search to generate permutations of the indices. At each step compute the time required using ceil(strength[i] / currentPower), then increase power by k after breaking the lock. Track the minimum total time across all permutations. This approach is straightforward but becomes expensive because the number of orders grows factorially. It works only for very small n.
Approach 2: Bitmask DFS with Memoization (O(n · 2^n))
Instead of recomputing the same states, treat the problem as a state graph. A state is defined by a bitmask representing which locks are already broken. The number of broken locks determines the current sword power: power = 1 + brokenCount * k. From each state, iterate through all remaining locks and try breaking one next. Recursively compute the cost and cache results for each mask. This transforms the search into a dynamic programming problem over subsets, similar to traveling through nodes in a small graph. Memoization avoids recomputation and reduces the complexity to O(n · 2^n) time with O(2^n) space.
Approach 3: Graph Shortest Path Interpretation (O(n · 2^n))
You can also model each bitmask as a node in a state graph. Edges represent breaking an unbroken lock and moving to a new mask. The edge weight equals the time required with the current power. Running DFS with caching or Dijkstra-style traversal finds the minimum total time to reach the mask where all locks are broken. This framing helps when reasoning about transitions and pruning repeated states. The underlying mechanics still rely on subset DP and efficient traversal of the state space.
Recommended for interviews: The bitmask DFS with memoization approach is the expected solution. Starting with brute force shows you understand the ordering dependency, but recognizing overlapping states and converting the search into subset DP demonstrates strong problem-solving skills. Interviewers usually want to see the transition from permutation exploration to memoized state search using techniques common in array ordering and subset graph traversal.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS (Permutations) | O(n!) | O(n) | Useful for understanding the ordering dependency or when n is very small |
| DFS + Memoization (Bitmask DP) | O(n · 2^n) | O(2^n) | Best general solution when n ≤ 10–15 and states repeat frequently |
| State Graph Shortest Path | O(n · 2^n) | O(2^n) | When modeling the problem explicitly as transitions between bitmask states |
Practice Minimum Time to Break Locks II with our built-in code editor and test cases.
Practice on FleetCode