Facebook Pixel

773. Sliding Puzzle

HardBreadth-First SearchMemoizationArrayDynamic ProgrammingBacktrackingMatrix
Leetcode Link

Problem Description

You have a 2x3 game board with tiles numbered 1 through 5 and one empty space (represented as 0). The tiles can slide into the empty space if they are directly adjacent to it (up, down, left, or right - no diagonal moves).

The goal is to rearrange the tiles to reach the target configuration:

[[1, 2, 3],
 [4, 5, 0]]

In this target state, the numbers 1-5 are arranged in order from left to right, top to bottom, with the empty space (0) in the bottom-right corner.

A move consists of sliding one tile that is adjacent to the empty space into that empty position (equivalently, swapping the 0 with an adjacent number).

Given an initial board configuration, you need to find the minimum number of moves required to reach the target state. If it's impossible to reach the target state from the given configuration, return -1.

For example, if the initial board is:

[[1, 2, 3],
 [4, 0, 5]]

You can slide the 5 into the empty space (where 0 is) to get the target configuration in just 1 move.

The solution uses BFS (Breadth-First Search) to explore all possible board states level by level, ensuring the shortest path is found. The board states are converted to strings for efficient storage and comparison in the visited set.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: The sliding puzzle can be represented as a graph where each board state is a node, and edges connect states that can be reached through a single tile move.

Is it a tree?

  • No: The state space is not a tree because multiple paths can lead to the same board configuration (you can often reach the same state through different sequences of moves).

Is the problem related to directed acyclic graphs?

  • No: The state graph can have cycles (you can return to a previous state by reversing moves).

Is the problem related to shortest paths?

  • Yes: We need to find the minimum number of moves to reach the target state, which is essentially finding the shortest path from the initial state to the goal state.

Is the graph Weighted?

  • No: Each move has the same cost (1 move), so this is an unweighted graph where all edges have equal weight.

BFS

  • Yes: For unweighted shortest path problems, BFS is the optimal choice.

Conclusion: The flowchart suggests using BFS (Breadth-First Search) for finding the minimum number of moves in the sliding puzzle. BFS explores states level by level, guaranteeing that when we first reach the target state, we've found it via the shortest possible path (minimum number of moves).

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is to think of this puzzle as a graph traversal problem. Each possible board configuration is a node in our graph, and moving a tile creates an edge between two configurations. Since we want the minimum number of moves, we're looking for the shortest path from our starting configuration to the target configuration [[1,2,3],[4,5,0]].

Why BFS? When all moves have equal cost (each move counts as 1), BFS naturally finds the shortest path because it explores all configurations reachable in 1 move, then all configurations reachable in 2 moves, and so on. The first time we encounter our target, we've found it using the minimum number of moves.

To implement this, we need to:

  1. Represent board states efficiently: Converting the 2D board to a string like "123450" makes it easy to store in a set and check for duplicates
  2. Track visited states: We use a set to avoid revisiting the same configuration, preventing infinite loops
  3. Generate all possible next states: From any configuration, we find where the empty space (0) is, then try swapping it with each adjacent tile (up, down, left, right)
  4. Level-by-level exploration: Using a queue, we process all states at distance k before moving to states at distance k+1

The solution converts between board representation and string representation (gets() and setb()) for efficient state management. The function f() generates all valid next states by finding the empty space and swapping it with adjacent tiles. If we exhaust all possible states without finding the target, the puzzle is unsolvable, so we return -1.

Learn more about Breadth-First Search, Memoization, Dynamic Programming and Backtracking patterns.

Solution Approach

The implementation uses BFS with string representation of board states. Let's walk through the key components:

1. State Representation

  • Convert the 2D board to a string for efficient storage and comparison
  • gets(): Flattens the 2D board into a string by concatenating rows (e.g., [[1,2,3],[4,0,5]] becomes "123405")
  • setb(s): Reconstructs the 2D board from a string representation

2. Generating Next States (f() function)

  • Find the position (i, j) of the empty space (0) in the current board
  • Try moving the empty space in 4 directions: [[0, -1], [0, 1], [1, 0], [-1, 0]] (left, right, down, up)
  • For each valid adjacent position (x, y):
    • Swap the empty space with the adjacent tile
    • Convert to string and add to results
    • Swap back to restore original state (backtrack)

3. BFS Implementation

start = gets()  # Initial board state as string
end = "123450"  # Target state
vis = {start}   # Visited states set
q = deque([start])  # BFS queue
ans = 0  # Move counter

4. Level-by-Level Traversal

  • Process all states at current distance before incrementing ans
  • For each state in the current level:
    • Convert string back to board using setb(x)
    • Generate all possible next states using f()
    • If target state found, return current move count
    • Add unvisited states to queue and visited set

5. Early Termination

  • Check if initial state equals target (return 0)
  • Return -1 if queue empties without finding target (unsolvable)

The algorithm guarantees finding the minimum moves because BFS explores states in order of distance from the start. Time complexity is O(n!) where n is the number of tiles (6 in this case), as there are at most 6! possible board configurations. Space complexity is also O(n!) for storing visited states.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a simple example where the initial board is:

[[1, 2, 3],
 [4, 0, 5]]

And we want to reach the target:

[[1, 2, 3],
 [4, 5, 0]]

Step 1: Initialize BFS

  • Convert initial board to string: "123405"
  • Target string: "123450"
  • Initialize queue with ["123405"] and visited set with {"123405"}
  • Set move counter ans = 0

Step 2: Process Level 0 (Initial State)

  • Queue size = 1, so we process 1 state at this level
  • Pop "123405" from queue
  • Convert back to board: [[1,2,3],[4,0,5]]
  • Find empty space (0) at position (1, 1)

Step 3: Generate Next States From position (1, 1), the empty space can move:

  • Up (1-1, 1) = (0, 1): Swap with 2
    • New board: [[1,0,3],[4,2,5]] → String: "103425"
  • Down (1+1, 1) = (2, 1): Invalid (out of bounds)
  • Left (1, 1-1) = (1, 0): Swap with 4
    • New board: [[1,2,3],[0,4,5]] → String: "123045"
  • Right (1, 1+1) = (1, 2): Swap with 5
    • New board: [[1,2,3],[4,5,0]] → String: "123450" ✓ Target found!

Step 4: Check for Target

  • When generating the right move, we get "123450" which equals our target
  • Since we're still processing level 0, we increment ans to 1
  • Return ans = 1

The minimum number of moves is 1 (sliding the 5 left into the empty space).

Alternative Example - Multiple Moves: If the initial board was:

[[4, 1, 2],
 [5, 0, 3]]

String: "412503"

The BFS would explore:

  • Level 0: Initial state "412503"
  • Level 1: States reachable in 1 move from initial
    • Move 0 up: "402513"
    • Move 0 left: "412053"
    • Move 0 right: "412530"
  • Level 2: States reachable in 2 moves (from unvisited Level 1 states)
  • Continue until target "123450" is found or all states exhausted

Each level represents states reachable with exactly that many moves, ensuring we find the minimum path when we first encounter the target.

Solution Implementation

1class Solution:
2    def slidingPuzzle(self, board: List[List[int]]) -> int:
3        """
4        Solve the sliding puzzle problem using BFS.
5        Goal: Transform the board to [[1,2,3],[4,5,0]]
6        Returns minimum number of moves, or -1 if impossible.
7        """
8      
9        def board_to_string() -> str:
10            """Convert 2D board to string representation for hashing."""
11            result = []
12            for row in range(2):
13                for col in range(3):
14                    result.append(str(board[row][col]))
15            return ''.join(result)
16      
17        def string_to_board(state: str) -> None:
18            """Convert string representation back to 2D board."""
19            for row in range(2):
20                for col in range(3):
21                    board[row][col] = int(state[row * 3 + col])
22      
23        def get_next_states() -> List[str]:
24            """Generate all possible next states from current board configuration."""
25            next_states = []
26          
27            # Find the position of the empty tile (0)
28            zero_row, zero_col = next((i, j) for i in range(2) for j in range(3) if board[i][j] == 0)
29          
30            # Try moving the empty tile in all four directions
31            directions = [[0, -1], [0, 1], [1, 0], [-1, 0]]  # left, right, down, up
32          
33            for delta_row, delta_col in directions:
34                new_row = zero_row + delta_row
35                new_col = zero_col + delta_col
36              
37                # Check if the new position is within bounds
38                if 0 <= new_row < 2 and 0 <= new_col < 3:
39                    # Swap empty tile with adjacent tile
40                    board[zero_row][zero_col], board[new_row][new_col] = board[new_row][new_col], board[zero_row][zero_col]
41                    next_states.append(board_to_string())
42                    # Swap back to restore original state
43                    board[zero_row][zero_col], board[new_row][new_col] = board[new_row][new_col], board[zero_row][zero_col]
44          
45            return next_states
46      
47        # Initialize BFS
48        start_state = board_to_string()
49        target_state = "123450"
50      
51        # Check if already solved
52        if start_state == target_state:
53            return 0
54      
55        # BFS setup
56        visited = {start_state}
57        queue = deque([start_state])
58        moves = 0
59      
60        # BFS traversal
61        while queue:
62            moves += 1
63            # Process all states at current level
64            for _ in range(len(queue)):
65                current_state = queue.popleft()
66                string_to_board(current_state)
67              
68                # Explore all possible next states
69                for next_state in get_next_states():
70                    if next_state == target_state:
71                        return moves
72                  
73                    if next_state not in visited:
74                        visited.add(next_state)
75                        queue.append(next_state)
76      
77        # No solution found
78        return -1
79
1class Solution {
2    // Array to store string representation of the board (6 cells total for 2x3 board)
3    private String[] boardStringArray = new String[6];
4    // 2D array representing the current board state
5    private int[][] board;
6
7    /**
8     * Solves the sliding puzzle problem using BFS
9     * @param board Initial 2x3 board configuration
10     * @return Minimum number of moves to reach target state, or -1 if impossible
11     */
12    public int slidingPuzzle(int[][] board) {
13        this.board = board;
14      
15        // Convert initial board to string representation
16        String startState = gets();
17        String targetState = "123450";
18      
19        // Check if already in target state
20        if (targetState.equals(startState)) {
21            return 0;
22        }
23      
24        // BFS setup: visited set and queue
25        Set<String> visited = new HashSet<>();
26        Deque<String> queue = new ArrayDeque<>();
27        queue.offer(startState);
28        visited.add(startState);
29      
30        int moves = 0;
31      
32        // BFS traversal
33        while (!queue.isEmpty()) {
34            moves++;
35            int levelSize = queue.size();
36          
37            // Process all states at current level
38            for (int i = 0; i < levelSize; i++) {
39                String currentState = queue.poll();
40              
41                // Convert string back to board for manipulation
42                setb(currentState);
43              
44                // Generate all possible next states
45                for (String nextState : next()) {
46                    // Check if we reached the target
47                    if (nextState.equals(targetState)) {
48                        return moves;
49                    }
50                  
51                    // Add unvisited states to queue
52                    if (!visited.contains(nextState)) {
53                        visited.add(nextState);
54                        queue.offer(nextState);
55                    }
56                }
57            }
58        }
59      
60        // Target state unreachable
61        return -1;
62    }
63
64    /**
65     * Converts the current board to a string representation
66     * @return String representation of the board
67     */
68    private String gets() {
69        for (int row = 0; row < 2; row++) {
70            for (int col = 0; col < 3; col++) {
71                boardStringArray[row * 3 + col] = String.valueOf(board[row][col]);
72            }
73        }
74        return String.join("", boardStringArray);
75    }
76
77    /**
78     * Sets the board state from a string representation
79     * @param state String representation of the board
80     */
81    private void setb(String state) {
82        for (int row = 0; row < 2; row++) {
83            for (int col = 0; col < 3; col++) {
84                board[row][col] = state.charAt(row * 3 + col) - '0';
85            }
86        }
87    }
88
89    /**
90     * Finds the position of the empty cell (0) in the board
91     * @return Array containing [row, column] of the empty cell
92     */
93    private int[] find0() {
94        for (int row = 0; row < 2; row++) {
95            for (int col = 0; col < 3; col++) {
96                if (board[row][col] == 0) {
97                    return new int[] {row, col};
98                }
99            }
100        }
101        return new int[] {0, 0}; // Default return (should never reach here)
102    }
103
104    /**
105     * Generates all possible next states from the current board state
106     * @return List of string representations of all possible next states
107     */
108    private List<String> next() {
109        // Find the empty cell position
110        int[] emptyPosition = find0();
111        int emptyRow = emptyPosition[0];
112        int emptyCol = emptyPosition[1];
113      
114        // Direction vectors: up, right, down, left
115        int[] directions = {-1, 0, 1, 0, -1};
116        List<String> nextStates = new ArrayList<>();
117      
118        // Try moving the empty cell in all 4 directions
119        for (int dir = 0; dir < 4; dir++) {
120            int newRow = emptyRow + directions[dir];
121            int newCol = emptyCol + directions[dir + 1];
122          
123            // Check if the new position is within bounds
124            if (newRow >= 0 && newRow < 2 && newCol >= 0 && newCol < 3) {
125                // Swap empty cell with adjacent cell
126                swap(emptyRow, emptyCol, newRow, newCol);
127                // Add the new state to result
128                nextStates.add(gets());
129                // Swap back to restore original state
130                swap(emptyRow, emptyCol, newRow, newCol);
131            }
132        }
133      
134        return nextStates;
135    }
136
137    /**
138     * Swaps two cells in the board
139     * @param row1 Row of first cell
140     * @param col1 Column of first cell
141     * @param row2 Row of second cell
142     * @param col2 Column of second cell
143     */
144    private void swap(int row1, int col1, int row2, int col2) {
145        int temp = board[row1][col1];
146        board[row1][col1] = board[row2][col2];
147        board[row2][col2] = temp;
148    }
149}
150
1class Solution {
2public:
3    int slidingPuzzle(vector<vector<int>>& board) {
4        // Convert initial board state to string representation
5        string startState = boardToString(board);
6        string targetState = "123450";
7      
8        // If already solved, return 0
9        if (startState == targetState) return 0;
10      
11        // Track visited states to avoid cycles
12        unordered_set<string> visited;
13        visited.insert(startState);
14      
15        // BFS queue to explore states level by level
16        queue<string> bfsQueue{{startState}};
17        int moves = 0;
18      
19        // BFS to find minimum moves
20        while (!bfsQueue.empty()) {
21            moves++;
22            int levelSize = bfsQueue.size();
23          
24            // Process all states at current level
25            for (int i = 0; i < levelSize; i++) {
26                string currentState = bfsQueue.front();
27                bfsQueue.pop();
28              
29                // Convert string back to board for generating next states
30                stringToBoard(currentState, board);
31              
32                // Generate all possible next states
33                vector<string> nextStates = generateNextStates(board);
34              
35                for (const string& nextState : nextStates) {
36                    // Check if we reached the target
37                    if (nextState == targetState) return moves;
38                  
39                    // Add unvisited states to queue
40                    if (!visited.count(nextState)) {
41                        visited.insert(nextState);
42                        bfsQueue.push(nextState);
43                    }
44                }
45            }
46        }
47      
48        // No solution found
49        return -1;
50    }
51
52private:
53    // Convert 2x3 board to string representation
54    string boardToString(vector<vector<int>>& board) {
55        string result = "";
56        for (int row = 0; row < 2; row++) {
57            for (int col = 0; col < 3; col++) {
58                result.push_back('0' + board[row][col]);
59            }
60        }
61        return result;
62    }
63
64    // Convert string representation back to 2x3 board
65    void stringToBoard(string state, vector<vector<int>>& board) {
66        for (int row = 0; row < 2; row++) {
67            for (int col = 0; col < 3; col++) {
68                board[row][col] = state[row * 3 + col] - '0';
69            }
70        }
71    }
72
73    // Generate all possible next states by sliding the empty tile
74    vector<string> generateNextStates(vector<vector<int>>& board) {
75        vector<string> nextStates;
76      
77        // Find position of empty tile (0)
78        pair<int, int> emptyPos = findEmptyTile(board);
79        int emptyRow = emptyPos.first;
80        int emptyCol = emptyPos.second;
81      
82        // Direction vectors: up, right, down, left
83        vector<int> directions = {-1, 0, 1, 0, -1};
84      
85        // Try moving empty tile in all four directions
86        for (int dir = 0; dir < 4; dir++) {
87            int newRow = emptyRow + directions[dir];
88            int newCol = emptyCol + directions[dir + 1];
89          
90            // Check if new position is valid
91            if (newRow >= 0 && newRow < 2 && newCol >= 0 && newCol < 3) {
92                // Swap empty tile with adjacent tile
93                swapTiles(emptyRow, emptyCol, newRow, newCol, board);
94                nextStates.push_back(boardToString(board));
95                // Swap back to restore original state
96                swapTiles(emptyRow, emptyCol, newRow, newCol, board);
97            }
98        }
99      
100        return nextStates;
101    }
102
103    // Swap tiles at two positions on the board
104    void swapTiles(int row1, int col1, int row2, int col2, vector<vector<int>>& board) {
105        int temp = board[row1][col1];
106        board[row1][col1] = board[row2][col2];
107        board[row2][col2] = temp;
108    }
109
110    // Find the position of the empty tile (0) on the board
111    pair<int, int> findEmptyTile(vector<vector<int>>& board) {
112        for (int row = 0; row < 2; row++) {
113            for (int col = 0; col < 3; col++) {
114                if (board[row][col] == 0) {
115                    return {row, col};
116                }
117            }
118        }
119        return {0, 0}; // Should never reach here in valid input
120    }
121};
122
1function slidingPuzzle(board: number[][]): number {
2    // Convert initial board state to string representation
3    let startState: string = boardToString(board);
4    const targetState: string = "123450";
5  
6    // If already solved, return 0
7    if (startState === targetState) return 0;
8  
9    // Track visited states to avoid cycles
10    const visited: Set<string> = new Set();
11    visited.add(startState);
12  
13    // BFS queue to explore states level by level
14    const bfsQueue: string[] = [startState];
15    let moves: number = 0;
16  
17    // BFS to find minimum moves
18    while (bfsQueue.length > 0) {
19        moves++;
20        const levelSize: number = bfsQueue.length;
21      
22        // Process all states at current level
23        for (let i = 0; i < levelSize; i++) {
24            const currentState: string = bfsQueue.shift()!;
25          
26            // Convert string back to board for generating next states
27            const currentBoard: number[][] = stringToBoard(currentState);
28          
29            // Generate all possible next states
30            const nextStates: string[] = generateNextStates(currentBoard);
31          
32            for (const nextState of nextStates) {
33                // Check if we reached the target
34                if (nextState === targetState) return moves;
35              
36                // Add unvisited states to queue
37                if (!visited.has(nextState)) {
38                    visited.add(nextState);
39                    bfsQueue.push(nextState);
40                }
41            }
42        }
43    }
44  
45    // No solution found
46    return -1;
47}
48
49// Convert 2x3 board to string representation
50function boardToString(board: number[][]): string {
51    let result: string = "";
52    for (let row = 0; row < 2; row++) {
53        for (let col = 0; col < 3; col++) {
54            result += board[row][col].toString();
55        }
56    }
57    return result;
58}
59
60// Convert string representation back to 2x3 board
61function stringToBoard(state: string): number[][] {
62    const board: number[][] = [[0, 0, 0], [0, 0, 0]];
63    for (let row = 0; row < 2; row++) {
64        for (let col = 0; col < 3; col++) {
65            board[row][col] = parseInt(state[row * 3 + col]);
66        }
67    }
68    return board;
69}
70
71// Generate all possible next states by sliding the empty tile
72function generateNextStates(board: number[][]): string[] {
73    const nextStates: string[] = [];
74  
75    // Find position of empty tile (0)
76    const emptyPos: [number, number] = findEmptyTile(board);
77    const emptyRow: number = emptyPos[0];
78    const emptyCol: number = emptyPos[1];
79  
80    // Direction vectors: up, right, down, left
81    const directions: number[] = [-1, 0, 1, 0, -1];
82  
83    // Try moving empty tile in all four directions
84    for (let dir = 0; dir < 4; dir++) {
85        const newRow: number = emptyRow + directions[dir];
86        const newCol: number = emptyCol + directions[dir + 1];
87      
88        // Check if new position is valid
89        if (newRow >= 0 && newRow < 2 && newCol >= 0 && newCol < 3) {
90            // Create a copy of the board to modify
91            const newBoard: number[][] = board.map(row => [...row]);
92          
93            // Swap empty tile with adjacent tile
94            swapTiles(emptyRow, emptyCol, newRow, newCol, newBoard);
95            nextStates.push(boardToString(newBoard));
96        }
97    }
98  
99    return nextStates;
100}
101
102// Swap tiles at two positions on the board
103function swapTiles(row1: number, col1: number, row2: number, col2: number, board: number[][]): void {
104    const temp: number = board[row1][col1];
105    board[row1][col1] = board[row2][col2];
106    board[row2][col2] = temp;
107}
108
109// Find the position of the empty tile (0) on the board
110function findEmptyTile(board: number[][]): [number, number] {
111    for (let row = 0; row < 2; row++) {
112        for (let col = 0; col < 3; col++) {
113            if (board[row][col] === 0) {
114                return [row, col];
115            }
116        }
117    }
118    return [0, 0]; // Should never reach here in valid input
119}
120

Time and Space Complexity

Time Complexity: O((m*n)! * m*n)

The sliding puzzle problem involves finding the shortest path from the initial board state to the target state "123450". This is essentially a BFS traversal through the state space graph.

  • The total number of possible board states is (m*n)! where m=2 and n=3, giving us 6! = 720 possible states
  • For each state, we need O(m*n) time to:
    • Convert between board and string representations (gets() and setb() both take O(6) time)
    • Find the position of 0: O(m*n)
    • Generate neighbors: up to 4 neighbors, each requiring O(m*n) operations for swapping and string conversion
  • In the worst case, BFS visits all possible states
  • Therefore, the total time complexity is O(6! * 6) = O(720 * 6) = O(4320), which simplifies to O((m*n)! * m*n)

Space Complexity: O((m*n)!)

  • The vis set can store up to (m*n)! = 6! = 720 unique states in the worst case
  • The BFS queue can also contain up to O((m*n)!) states in the worst case (though typically much less)
  • The temporary array t and board manipulations use O(m*n) = O(6) space
  • The dominant factor is the visited set and queue, giving us O((m*n)!) space complexity

For this specific 2x3 puzzle, both complexities have constants: O(720 * 6) for time and O(720) for space, but in general form for an m×n puzzle, they are O((m*n)! * m*n) and O((m*n)!) respectively.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient State Representation and Comparison

Many implementations create new board objects or use nested lists directly as dictionary keys, which causes errors since lists are unhashable. Some try using tuples of tuples, which works but creates unnecessary overhead.

Problem Example:

# This will cause TypeError: unhashable type: 'list'
visited = {board}  # Can't use list as set/dict key

# This works but is inefficient
visited = {tuple(tuple(row) for row in board)}

Solution: Convert the board to a string representation for efficient hashing and comparison. This reduces memory usage and speeds up lookups.

2. Not Restoring Board State After Generating Moves

A critical bug occurs when modifying the board to generate next states without restoring it, causing incorrect state generation in subsequent iterations.

Problem Example:

def get_next_states():
    next_states = []
    # Find zero position...
    for dr, dc in directions:
        if valid_position:
            board[zero_row][zero_col], board[new_row][new_col] = board[new_row][new_col], board[zero_row][zero_col]
            next_states.append(board_to_string())
            # MISSING: Swap back to restore original state!
    return next_states

Solution: Always swap back the tiles after recording the new state to maintain the board's integrity for generating other moves.

3. Processing States Level by Level Incorrectly

Failing to process all states at the current distance before incrementing the move counter leads to incorrect minimum move calculations.

Problem Example:

while queue:
    current = queue.popleft()
    moves += 1  # Wrong! Increments for each state, not each level
    # Process current state...

Solution: Use a for loop with range(len(queue)) to process exactly the states at the current level before incrementing moves:

while queue:
    moves += 1
    for _ in range(len(queue)):  # Process entire level
        current = queue.popleft()
        # Generate and check next states...

4. Forgetting Edge Cases

Not checking if the initial state is already the target state, leading to unnecessary computation or incorrect results.

Solution: Always check if start_state == target_state before starting BFS and return 0 immediately if true.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

BFS Fundamentals

https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS

Memoization

Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More