Watch 3 video solutions for Minimum Time to Break Locks I, a medium level problem involving Array, Dynamic Programming, Backtracking. This walkthrough by Aryan Mittal has 2,230 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 a given value k.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], k = 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], k = 2
Output: 5
Explanation:
| Time | Energy | x | Action | Updated x |
|---|---|---|---|---|
| 0 | 0 | 1 | Nothing | 1 |
| 1 | 1 | 1 | Nothing | 1 |
| 2 | 2 | 1 | Break 1st Lock | 3 |
| 3 | 3 | 3 | Nothing | 3 |
| 4 | 6 | 3 | Break 2nd Lock | 5 |
| 5 | 5 | 5 | Break 3rd Lock | 7 |
The locks cannot be broken in less than 5 minutes; thus, the answer is 5.
Constraints:
n == strength.length1 <= n <= 81 <= K <= 101 <= strength[i] <= 106Problem Overview: You are given an array where each value represents the energy required to break a lock. Energy increases every minute based on a factor X. After breaking a lock, energy resets to 0 and X increases by K. The goal is to determine the minimum total time needed to break all locks.
Approach 1: Permutation Backtracking (O(n! * n) time, O(n) space)
The most direct strategy is to try every possible order of breaking locks. For each permutation, simulate the process: compute how many minutes are needed to accumulate enough energy to break the next lock using ceil(strength[i] / X). After breaking a lock, reset energy to 0 and increase X by K. Track the total time for that sequence and keep the minimum across all permutations. This approach is easy to reason about but becomes expensive because there are n! possible orders.
Approach 2: Bitmask Dynamic Programming (O(n · 2^n) time, O(2^n) space)
A more scalable solution models the problem using bitmask state compression. Each mask represents which locks have already been broken. The number of set bits tells you how many locks are completed, which determines the current energy factor X = 1 + broken * K. For every state, iterate through all locks not yet broken and calculate the time required to accumulate enough energy for that lock. Update the DP state for the new mask with the minimum total time. This eliminates repeated calculations across permutations.
The key insight is that energy always resets after breaking a lock, so the only state that matters is which locks are broken. The exact energy leftover never carries forward. This allows the problem to be solved cleanly with dynamic programming over subsets while exploring transitions similar to depth-first search.
Recommended for interviews: Bitmask DP is the expected solution. Starting with brute force permutations shows you understand the order-dependence of the problem. Converting that idea into a subset DP reduces the complexity from factorial to O(n · 2^n), which fits comfortably for n ≤ 8 and demonstrates strong problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Permutation Backtracking | O(n! * n) | O(n) | Understanding the brute-force ordering of locks or when n is extremely small |
| Bitmask Dynamic Programming | O(n · 2^n) | O(2^n) | Optimal approach for n ≤ 8; avoids recomputing repeated states |