Skip to main content
Talentd

Minimum Time to Break Locks II - Solution & Explanation

HardPremiumFree on FleetCodeArrayDepth-First SearchGraph8 min readAsked at: Ivp
Practice this problem

Problem Statement

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:

  • The initial energy of the sword is 0.
  • The initial factor X by which the energy of the sword increases is 1.
  • Every minute, the energy of the sword increases by the current factor X.
  • To break the ith lock, the energy of the sword must reach at least strength[i].
  • After breaking a lock, the energy of the sword resets to 0, and the factor 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.length
  • 1 <= n <= 80
  • 1 <= strength[i] <= 106
  • n == strength.length

Approach Overview

Problem 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.

Solution

Code

PythonJava

Python

Java

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 PathO(n · 2^n)O(2^n)When modeling the problem explicitly as transitions between bitmask states

Frequently Asked Questions

Is Minimum Time to Break Locks II easy or hard?
Minimum Time to Break Locks II is classified as Hard. The difficulty comes from recognizing that the lock-breaking order affects future costs and that brute force permutations are too slow. Converting the problem into subset DP with memoized DFS is the key insight.
Minimum Time to Break Locks II Python/Java solution
Implement a recursive DFS function that accepts the current bitmask of broken locks. Use a memo array indexed by mask to cache results. For each unbroken lock, compute the time using ceil(strength[i] / power), update the mask, and recurse. The same logic works in Python, Java, C++, and Go with bit operations and memoization.
How to solve Minimum Time to Break Locks II in O(n · 2^n)?
Represent the set of broken locks as a bitmask. For each mask, compute the current power using the number of bits set. Try breaking each remaining lock, calculate the time cost using ceil(strength[i] / power), and recursively solve the next state. Cache results for each mask so every subset is evaluated only once.
What is the best approach for Minimum Time to Break Locks II?
The most efficient approach is DFS with memoization using a bitmask to represent which locks are already broken. Each state computes the minimum time to finish the remaining locks while deriving the current sword power from the number of broken locks. This reduces repeated work and runs in O(n · 2^n) time with O(2^n) space.
Is Minimum Time to Break Locks II asked at Google/Amazon/Meta?
Problems involving subset DP, permutation optimization, and state graph traversal frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests similar skills: modeling states, pruning repeated work, and optimizing exponential search with memoization.
What data structure is used in Minimum Time to Break Locks II?
The core structure is a bitmask representing which locks are already broken. A memoization map or array stores results for each mask. DFS or graph traversal is used to explore transitions between states while computing the minimum cost.
What is the time complexity of Minimum Time to Break Locks II?
A naive permutation search takes O(n!) time because every order of locks must be evaluated. With bitmask dynamic programming and memoization, the complexity improves to O(n · 2^n) since each subset of locks is processed once and transitions try up to n remaining locks.

Ready to solve this problem?

Practice Minimum Time to Break Locks II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays