What is the time complexity of Sliding Puzzle?

The optimal solution has a time complexity of O(6!).

What data structures are used to solve Sliding Puzzle?

This problem uses Array, Dynamic Programming, Backtracking, Breadth-First Search, Memoization, Matrix. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Sliding Puzzle?

Insight 1: The problem can be modeled as a graph where each state of the board is a node, and edges represent possible moves. Breadth-First Search (BFS) is suitable for finding the shortest path in a graph. Insight 2: States can be represented as strings or tuples to easily track visited states and avoid cycles.

Which companies ask LeetCode 773. Sliding Puzzle in interviews?

This problem is frequently asked at Airbnb, Nvidia.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Sliding Puzzle - LeetCode 773 Solution

Sliding Puzzle - Complete Solution Guide

Sliding Puzzle is LeetCode problem 773, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

On an 2 x 3 board, there are five tiles labeled from 1 to 5 , and an empty square represented by 0 . A move consists of choosing 0 and a 4-directionally adjacent number and swapping it. The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]] . Given the puzzle board board , return the least number of moves required so that the state of the board is solved . If it is impossible for the state of the board to be solved, return -1 . Example 1: Input: board = [[1,2,3],[4,0,5]]

Detailed Explanation

The problem presents a sliding puzzle on a 2x3 board with tiles numbered 1 to 5 and an empty space represented by 0. The goal is to find the minimum number of moves (swapping the 0 with an adjacent tile) to reach the solved state [[1, 2, 3], [4, 5, 0]]. If the puzzle cannot be solved, the function should return -1. The input is a 2x3 integer array representing the initial state of the board, and the output is an integer representing the minimum number of moves or -1 if unsolvable.

Solution Approach

The solution employs Breadth-First Search (BFS) to explore the possible states of the puzzle. The initial state is the root node. Each neighbor of a node represents a valid move (swapping the 0 with an adjacent number). BFS guarantees finding the shortest path to the target state. A set is used to keep track of visited states to prevent cycles and redundant computations. The `neighbors` data structure speeds up the determination of valid moves from each position.

Step-by-Step Algorithm

Step 1: Initialize the target state as a tuple (1, 2, 3, 4, 5, 0).
Step 2: Convert the input 2D board into a 1D tuple representing the start state.
Step 3: Create a `neighbors` dictionary (or array) to store the valid moves for each position of the '0'.
Step 4: Initialize a queue with the starting state and the number of moves (initially 0).
Step 5: Initialize a set to keep track of visited states to avoid revisiting them and entering infinite loops.
Step 6: While the queue is not empty:
Step 7: Dequeue a state and its corresponding number of moves.
Step 8: Find the index of '0' in the current state.
Step 9: Iterate through the possible neighbor indices for the '0'.
Step 10: Generate the next state by swapping '0' with its neighbor.
Step 11: If the next state is the target state, return the current number of moves + 1.
Step 12: If the next state has not been visited, add it to the visited set and enqueue it with the number of moves + 1.
Step 13: If the queue becomes empty and the target state has not been found, return -1 (puzzle is unsolvable).

Key Insights

Insight 1: The problem can be modeled as a graph where each state of the board is a node, and edges represent possible moves. Breadth-First Search (BFS) is suitable for finding the shortest path in a graph.
Insight 2: States can be represented as strings or tuples to easily track visited states and avoid cycles.
Insight 3: Using a `neighbors` array/map to store the possible moves from each position of the zero avoids redundant calculations.
Insight 4: Deterministic problems like this one might not always be solvable, so a check for unsolvability should be implemented if applicable (though it's not strictly necessary here, BFS will naturally terminate with -1).
Insight 5: Transforming the 2D array into a 1D array (or tuple/string) simplifies the swapping logic and state comparison.

Complexity Analysis

Time Complexity: O(6!)

Space Complexity: O(6!)

Topics

This problem involves: Array, Dynamic Programming, Backtracking, Breadth-First Search, Memoization, Matrix.

Companies

Asked at: Airbnb, Nvidia.

Sliding Puzzle | LeetCode 773

Hard

Array Dynamic Programming Backtracking Breadth-First Search Memoization Matrix

Time: O(6!)Space: O(6!)

Solution Code

Available in:

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int slidingPuzzle(int[][] board) {
        int[] target_state = {1, 2, 3, 4, 5, 0};
        int[] start_state_array = new int[6];
        System.arraycopy(board[0], 0, start_state_array, 0, board[0].length);
        System.arraycopy(board[1], 0, start_state_array, board[0].length, board[1].length);

        if (Arrays.equals(start_state_array, target_state)) {
            return 0;
        }

        int[][] neighbors = {
            {1, 3},
            {0, 2, 4},
            {1, 5},
            {0, 4},
            {1, 3, 5},
            {2, 4}
        };

        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0, Arrays.hashCode(start_state_array), Arrays.hashCode(target_state), 0, start_state_array[0], start_state_array[1], start_state_array[2], start_state_array[3], start_state_array[4], start_state_array[5]});
        Set<Integer> visited = new HashSet<>();
        visited.add(Arrays.hashCode(start_state_array));

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int moves = current[3];
            int[] current_state_array = Arrays.copyOfRange(current, 4, 10);

            int zero_idx = -1;
            for (int i = 0; i < current_state_array.length; i++) {
                if (current_state_array[i] == 0) {
                    zero_idx = i;
                    break;
                }
            }

            for (int neighbor_idx : neighbors[zero_idx]) {
                int[] temp_list = Arrays.copyOf(current_state_array, current_state_array.length);
                int temp = temp_list[zero_idx];
                temp_list[zero_idx] = temp_list[neighbor_idx];
                temp_list[neighbor_idx] = temp;
                
                if (Arrays.equals(temp_list, target_state)) {
                    return moves + 1;
                }

                int next_state_hash = Arrays.hashCode(temp_list);
                if (!visited.contains(next_state_hash)) {
                    visited.add(next_state_hash);
                    queue.offer(new int[]{0, Arrays.hashCode(temp_list), Arrays.hashCode(target_state), moves + 1, temp_list[0], temp_list[1], temp_list[2], temp_list[3], temp_list[4], temp_list[5]});
                }
            }
        }

        return -1;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 773: Sliding Puzzle - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming Backtracking Breadth-First Search Memoization Matrix

Companies

AirbnbNvidia

Stats

Difficulty:Hard

Languages:4

Companies:2

Problem #:773

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

13 steps

1
Step 1: Initialize the target state as a tuple (1, 2, 3, 4, 5, 0).
2
Step 2: Convert the input 2D board into a 1D tuple representing the start state.
3
Step 3: Create a `neighbors` dictionary (or array) to store the valid moves for each position of the '0'.
4
Step 4: Initialize a queue with the starting state and the number of moves (initially 0).
5
Step 5: Initialize a set to keep track of visited states to avoid revisiting them and entering infinite loops.
6
Step 6: While the queue is not empty:
7
Step 7: Dequeue a state and its corresponding number of moves.
8
Step 8: Find the index of '0' in the current state.
9
Step 9: Iterate through the possible neighbor indices for the '0'.
10
Step 10: Generate the next state by swapping '0' with its neighbor.
11
Step 11: If the next state is the target state, return the current number of moves + 1.
12
Step 12: If the next state has not been visited, add it to the visited set and enqueue it with the number of moves + 1.
13
Step 13: If the queue becomes empty and the target state has not been found, return -1 (puzzle is unsolvable).

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(6!)

💾

Space Complexity

O(6!)

📝

Why?

There are at most 6! = 720 possible states of the board. BFS explores each state at most once. The time complexity is therefore proportional to the number of possible states. The space complexity is also O(6!) because in the worst case, we might need to store all possible states in the `visited` set and the queue simultaneously.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

A* Search

A* search could be used instead of BFS to potentially improve performance. A heuristic function could estimate the number of moves required to reach the target state from a given state. For example, Manhattan distance could be used to calculate the distance of each tile from its target position.

Time: Potentially better than O(6!) depending on the heuristic.Space: Potentially better or worse than O(6!) depending on the heuristic. It could reduce the states explored.

Trade-offs: A* Search might perform better than BFS, especially when the heuristic is accurate, but requires designing a good heuristic function which adds complexity. In the worst case, the heuristic is bad, A* might devolve into an algorithm similar to BFS or DFS. For this problem given the upper bound on the number of states (720), BFS is a very reasonable and potentially faster approach because A* requires additional computation of the heuristic at each step.

✨

Key Insights

1Insight 1: The problem can be modeled as a graph where each state of the board is a node, and edges represent possible moves. Breadth-First Search (BFS) is suitable for finding the shortest path in a graph.
2Insight 2: States can be represented as strings or tuples to easily track visited states and avoid cycles.
3Insight 3: Using a `neighbors` array/map to store the possible moves from each position of the zero avoids redundant calculations.
4Insight 4: Deterministic problems like this one might not always be solvable, so a check for unsolvability should be implemented if applicable (though it's not strictly necessary here, BFS will naturally terminate with -1).
5Insight 5: Transforming the 2D array into a 1D array (or tuple/string) simplifies the swapping logic and state comparison.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: The initial board is already in the target state. The solution correctly returns 0 in this case.
Edge case 2: The puzzle is unsolvable. BFS explores all reachable states and returns -1 if the target state is not found.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not using a visited set, which leads to infinite loops and exceeding time limits.

✗Common mistake 2: Incorrectly calculating the neighbor indices, leading to invalid moves and incorrect results.

✗Common mistake 3: Not handling the case where the puzzle is unsolvable, which can cause the program to run indefinitely or crash.

✗Common mistake 4: Representing the board state inefficiently, which can significantly impact performance and memory usage.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Pathfinding algorithms in games, such as finding the shortest path for a character to reach a destination while avoiding obstacles. This is a simplified analogy to more sophisticated pathfinding systems.

🏦Real-world scenario 2: Route planning for robots or autonomous vehicles. The algorithm can be used to find the optimal sequence of actions to achieve a goal, such as navigating a warehouse or assembling a product.

🎮Real-world scenario 3: Solving configuration problems in manufacturing or logistics, where the goal is to find the optimal arrangement of parts or resources to minimize costs or maximize efficiency.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 24, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Should I use top-down (memoization) or bottom-up (tabulation)?

Start with top-down (recursion + memoization) as it directly maps to the recursive thinking and handles only needed subproblems. Convert to bottom-up for better space efficiency and to avoid stack overflow. Bottom-up is often faster due to no recursion overhead.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Sliding Puzzle"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?