Cracking the Safe solution and explanation
Google
9 more videos on this problem
花花酱 LeetCode 753. Cracking the Safe - 刷题找工作 EP144Hua Hua · 17:42 · 9K views
Leetcode 753. Cracking the SafeElite Code · 27:44 · 5K views
Leetcode 0753. Cracking the SafeFearless Learner · 13:11 · 1K views
Interview, Swift, Graph, leetcode, 753. Cracking the Safe (Google , DFS, Graph, Eulerian Circuit)Soonin Coding Challenge · 31:55 · 1K views
【每日一题】753. Cracking the Safe, 1/16/2020Huifeng Guan · 24:41 · 1K views
LeetCode 753: Cracking the SafeRoel Van de Paar · 2:19 · 493 views
753 cracking the safeJimmy Wang · 1:38 · 401 views
Cracking the Safe (LeetCode) # Euclidean circuitDaiki - Road to $400K - · 48:25 · 240 views
LeetCode Hard 753 Cracking the Saferobzingcod · 28:33 · 215 views
No Sound Leetcode 753: Cracking the SafeExtremeProgrammer · 2:02 · 91 views
The problem
There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1].
The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit.
- For example, the correct password is
"345"and you enter in"012345":- After typing
0, the most recent3digits is"0", which is incorrect. - After typing
1, the most recent3digits is"01", which is incorrect. - After typing
2, the most recent3digits is"012", which is incorrect. - After typing
3, the most recent3digits is"123", which is incorrect. - After typing
4, the most recent3digits is"234", which is incorrect. - After typing
5, the most recent3digits is"345", which is correct and the safe unlocks.
- After typing
Return any string of minimum length that will unlock the safe at some point of entering it.
Example 1:
Input: n = 1, k = 2 Output: "10" Explanation: The password is a single digit, so enter each digit. "01" would also unlock the safe.
Example 2:
Input: n = 2, k = 2 Output: "01100" Explanation: For each possible password: - "00" is typed in starting from the 4th digit. - "01" is typed in starting from the 1st digit. - "10" is typed in starting from the 3rd digit. - "11" is typed in starting from the 2nd digit. Thus "01100" will unlock the safe. "10011", and "11001" would also unlock the safe.
Constraints:
1 <= n <= 41 <= k <= 101 <= kn <= 4096
Approach overview
Problem Overview: You need to generate the shortest possible string that guarantees opening a safe with an unknown password of length n, where each digit ranges from 0 to k-1. The string must contain every possible combination of length n exactly once as a substring. This is fundamentally a sequence generation problem that maps directly to graph traversal.
Approach 1: Backtracking with Visited Combinations (Time: O(k^n * n), Space: O(k^n))
This approach builds the sequence incrementally using Depth-First Search. Start with a prefix of n zeros, then repeatedly append digits from 0 to k-1. Each time you append a digit, form the last n-length substring and mark it as visited. If that combination hasn’t appeared before, continue the DFS. When all k^n combinations are visited, the constructed string is valid. Backtracking removes the last digit if a branch cannot cover all combinations. This method is conceptually simple and mirrors typical DFS permutation generation, but it becomes expensive as n grows because each recursive step checks and tracks visited states.
Approach 2: De Bruijn Sequence using Hierholzer's Algorithm (Time: O(k^n), Space: O(k^n))
The optimal solution models the problem as an graph. Each node represents a string of length n-1. Each directed edge represents appending a digit (forming a length n combination). Since every combination must appear exactly once, the task becomes finding an Eulerian circuit that visits every edge exactly once. Hierholzer’s algorithm performs a DFS traversal that consumes edges as they are visited. When traversing from node u, append digits 0..k-1, mark edges as used, and recursively explore the next node formed by the last n-1 characters. The resulting traversal naturally constructs a De Bruijn sequence. After DFS finishes, append the initial n-1 prefix to complete the cycle.
The key insight is that each edge corresponds to a unique password combination, so covering all edges exactly once ensures every possible password appears in the sequence. Instead of brute-forcing combinations, the algorithm systematically walks the graph structure that represents them.
Recommended for interviews: Interviewers usually expect the De Bruijn sequence solution with Hierholzer’s algorithm. It shows you recognize the transformation from substring coverage to Eulerian traversal. Explaining the backtracking version first demonstrates understanding of the search space, but implementing the graph-based approach proves stronger algorithmic maturity.
Approach 1: De Bruijn Sequence Using Hierholzer's Algorithm
The problem can be transformed into finding a De Bruijn sequence for n-length and k-digit passwords. A De Bruijn sequence of order n over an alphabet of size k is a cyclic sequence in which every possible subsequence of length n appears as a sequence of consecutive characters exactly once. Hierholzer's algorithm can be used to find an Eulerian path/circuit, which forms the basis for constructing the desired De Bruijn sequence.
def crackSafe(n, k):
seen = set()
result = []
def dfs(node):
for x in map(str, range(k)):
nei = node + x
if nei not in seen:
seen.add(nei)
dfs(nei[1:])
result.append(x)
start_node = '0' * (n - 1)
dfs(start_node)
return ''.join(result) + start_nodefunction crackSafe(n, k) {
const seen = new Set();
const result = [];
function dfs(node) {
for (let x = 0; x < k; x++) {
const neighbor = node + x;
if (!seen.has(neighbor)) {
seen.add(neighbor);
dfs(neighbor.slice(1));
result.push(x);
}
}
}
const startNode = '0'.repeat(n - 1);
dfs(startNode);
return result.join('') + startNode;
}The code uses Depth First Search (DFS) to traverse all possible paths in our De Bruijn graph representation. Each node is a sequence and we attempt to append each possible digit (0 to k-1). If a sequence has not been seen, it is marked as visited. We recursively call DFS on the new node formed by appending the digit. Once a dead-end is reached, digits are added back to the result, which forms a De Bruijn sequence after appending the start node.
Time Complexity: O(k^n).
Space Complexity: O(k^n) for the resulting sequence and visited nodes.
Approach 2: Backtracking Approach
We can solve this problem using a backtracking approach by manually exploring each possible combination of digits and backtracking when a potential solution is found. Unlike the Eulerian path strategy, this approach builds sequences on-the-fly, exploring each digit combination and ensuring that all unique combinations appear in the sequence.
import java.util.HashSet;
public class CrackSafeJava {
public static void main(String[] args) {
int n = 2, k = 2;
System.out.println(crackSafe(n, k));
}
public static String crackSafe(int n, int k) {
StringBuilder result = new StringBuilder();
HashSet<String> seen = new HashSet<>();
String start = "0".repeat(n - 1);
dfs(start, k, seen, result, n);
return result.toString() + start;
}
private static void dfs(String node, int k, HashSet<String> seen, StringBuilder result, int n) {
for (int x = 0; x < k; x++) {
String nei = node + x;
if (!seen.contains(nei)) {
seen.add(nei);
dfs(nei.substring(1), k, seen, result, n);
result.append(x);
}
}
}
}#include <iostream>
#include <unordered_set>
#include <string>
#include <vector>
using namespace std;
void dfs(string current, int k, unordered_set<string>& seen, string& result, int n) {
for (char c = '0'; c < '0' + k; ++c) {
string next = current + c;
if (seen.find(next) == seen.end()) {
seen.insert(next);
dfs(next.substr(1), k, seen, result, n);
result += c;
}
}
}
string crackSafe(int n, int k) {
string result;
unordered_set<string> seen;
string start(n - 1, '0');
dfs(start, k, seen, result, n);
return result + start;
}
int main() {
int n = 2, k = 2;
cout << crackSafe(n, k) << endl;
return 0;
}This Java solution involves recursive backtracking similar to earlier approaches, visiting nodes that have not been yet included in the sequence. Each node tracks extensions of the current sequence to k-based digits. The solution becomes valid when backtrack completes, yielding a concatenated sequence from DFS.
Time Complexity: O(k^n).
Space Complexity: O(k^n).
Approach 3: Eulerian Circuit
We can construct a directed graph based on the description in the problem: each point is considered as a length n-1 k-string, and each edge carries a character from 0 to k-1. If there is a directed edge e from point u to point v, and the character carried by e is c, then the last k-1 characters of u+c form the string v. At this point, the edge u+c represents a password of length n.
In this directed graph, there are k^{n-1} points, each point has k outgoing edges and k incoming edges. Therefore, this directed graph has an Eulerian circuit, and the path traversed by the Eulerian circuit is the answer to the problem.
The time complexity is O(k^n), and the space complexity is O(k^n).
function crackSafe(n: number, k: number): string {
function dfs(u: number): void {
for (let x = 0; x < k; x++) {
const e = u * 10 + x;
if (!vis.has(e)) {
vis.add(e);
const v = e % mod;
dfs(v);
ans.push(x.toString());
}
}
}
const mod = Math.pow(10, n - 1);
const vis = new Set<number>();
const ans: string[] = [];
dfs(0);
ans.push('0'.repeat(n - 1));
return ans.join('');
}func crackSafe(n int, k int) string {
mod := int(math.Pow(10, float64(n-1)))
vis := map[int]bool{}
ans := &strings.Builder{}
var dfs func(int)
dfs = func(u int) {
for x := 0; x < k; x++ {
e := u*10 + x
if !vis[e] {
vis[e] = true
v := e % mod
dfs(v)
ans.WriteByte(byte('0' + x))
}
}
}
dfs(0)
ans.WriteString(strings.Repeat("0", n-1))
return ans.String()
}Complexity comparison
| Approach | Complexity |
|---|---|
| De Bruijn Sequence Using Hierholzer's Algorithm | Time Complexity: O(k^n). |
| Backtracking Approach | Time Complexity: O(k^n). |
| Eulerian Circuit | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Visited Set | O(k^n * n) | O(k^n) | Good for understanding the search space and demonstrating DFS logic in interviews |
| De Bruijn Sequence (Hierholzer's Algorithm) | O(k^n) | O(k^n) | Optimal solution when modeling the problem as a graph with Eulerian circuit traversal |
Frequently asked questions
Is Cracking the Safe easy or hard?
Cracking the Safe is classified as a Hard problem on LeetCode. The difficulty comes from recognizing that the task maps to generating a De Bruijn sequence and solving it using an Eulerian circuit in a directed graph rather than brute-force combination generation.
Cracking the Safe Python/Java solution
Most implementations build the De Bruijn sequence using DFS and a visited set of edges. Python and JavaScript solutions typically implement Hierholzer's algorithm recursively, while C++ and Java versions often demonstrate the backtracking approach or an iterative DFS over graph edges.
How to solve Cracking the Safe in O(k^n)?
Model each (n-1)-length string as a node in a graph and each length-n combination as a directed edge. Run a DFS using Hierholzer's algorithm to find an Eulerian circuit that visits every edge exactly once. Append digits during traversal to construct a De Bruijn sequence that contains all combinations.
What is the best approach for Cracking the Safe?
The optimal approach uses a De Bruijn sequence constructed via Hierholzer's algorithm on a directed graph. Nodes represent (n-1)-length strings and edges represent possible password combinations. Finding an Eulerian circuit ensures every combination appears exactly once. This runs in O(k^n) time and is the standard interview solution.
Is Cracking the Safe asked at Google/Amazon/Meta?
Cracking the Safe appears in hard-level interview preparation lists and has been reported in interviews at companies like Google and Amazon. The problem tests graph modeling, Eulerian circuits, and advanced DFS traversal techniques, which are common topics in senior algorithm interviews.
What data structure is used in Cracking the Safe?
The optimal solution uses a graph representation where nodes are (n-1)-digit strings and edges represent transitions formed by appending digits. A DFS traversal with a visited-edge set or adjacency tracking is used to implement Hierholzer's algorithm for finding an Eulerian circuit.
What is the time complexity of Cracking the Safe?
The optimal graph-based solution runs in O(k^n) time because it visits each possible password combination exactly once. There are k^n edges in the De Bruijn graph, and Hierholzer's algorithm processes each edge once. Space complexity is also O(k^n) to store visited edges or combinations.