Skip to main content
Talentd

Minimum Time to Break Locks I - Solution & Explanation

MediumArrayDynamic ProgrammingBacktrackingBit Manipulation5 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 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.length
  • 1 <= n <= 8
  • 1 <= K <= 10
  • 1 <= strength[i] <= 106

Approach Overview

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

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Permutation BacktrackingO(n! * n)O(n)Understanding the brute-force ordering of locks or when n is extremely small
Bitmask Dynamic ProgrammingO(n · 2^n)O(2^n)Optimal approach for n ≤ 8; avoids recomputing repeated states

Video Solution

3376. Minimum Time to Break Locks I | Recursion with Bitmasks | Not Greedy | Math • Aryan Mittal • 2,305 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Minimum Time to Break Locks I easy or hard?
The problem is rated Medium because the core difficulty lies in recognizing that the order of locks matters and converting the brute-force permutation idea into a bitmask dynamic programming solution with O(n · 2^n) complexity.
Minimum Time to Break Locks I Python/Java solution
Most implementations use a DP array of size 2^n. For each mask, count the number of broken locks to determine the energy factor, compute the required time to break the next lock, and update the next mask. The same logic translates cleanly to Python, Java, C++, Go, and TypeScript.
How to solve Minimum Time to Break Locks I in O(n · 2^n)?
Use DP with a bitmask representing which locks are broken. For each mask, compute the energy factor X = 1 + broken * K. Try breaking every remaining lock, calculate the required minutes using ceil(strength[i] / X), and update the next mask with the minimum total time.
What is the best approach for Minimum Time to Break Locks I?
Bitmask dynamic programming is the most efficient approach. Each state represents the subset of locks already broken, and transitions try breaking any remaining lock. The energy factor X depends only on how many locks are broken, allowing the solution to run in O(n · 2^n) time.
Is Minimum Time to Break Locks I asked at Google/Amazon/Meta?
Problems involving bitmask dynamic programming and subset states appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact problem may appear in online assessments or practice sets, the technique tested here is widely used in real interview questions.
What data structure is used in Minimum Time to Break Locks I?
The main structure is a DP array indexed by a bitmask representing subsets of locks. Bit operations are used to check whether a lock is already broken and to generate new states efficiently.
What is the time complexity of Minimum Time to Break Locks I?
The optimal solution runs in O(n · 2^n) time with O(2^n) space using bitmask dynamic programming. A brute-force permutation approach would require O(n! * n) time, which becomes impractical as the number of locks grows.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays