LeetCode 773: Sliding Puzzle Solution

Master LeetCode problem 773 (Sliding Puzzle), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

773. Sliding Puzzle

Hard

Array Dynamic Programming Backtracking Breadth-First Search Memoization Matrix

Problem Explanation

Explanation

To solve this problem, we can use a breadth-first search (BFS) algorithm. We can represent the board configuration as a string to keep track of visited states efficiently. We start with the initial board state, then explore all possible states reachable from the current state by making valid moves. We continue this process until we reach the target state or exhaust all possible moves.

Algorithm:
1. Create a queue to store the board configurations and a set to keep track of visited configurations.
2. Convert the initial board state to a string and add it to the queue and visited set.
3. Perform BFS by iterating through the queue:
  - For each board state in the queue, generate all possible next states by making valid moves.
  - If a next state is the target state, return the number of moves taken to reach it.
  - Otherwise, if the next state has not been visited, add it to the queue and mark it as visited.
4. If the target state is not reached, return -1.
Time Complexity: Let N be the total number of possible board states. In the worst-case scenario, we may need to visit all states, leading to a time complexity of O(N).
Space Complexity: The space complexity is also O(N) to store the visited states.

Solution Code

import java.util.*;

class Solution {
    public int slidingPuzzle(int[][] board) {
        int[][] target = {{1, 2, 3}, {4, 5, 0}};
        String targetStr = Arrays.deepToString(target).replaceAll("\\[|\\]|,|\\s", "");
        
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        String initial = Arrays.deepToString(board).replaceAll("\\[|\\]|,|\\s", "");
        queue.offer(initial);
        visited.add(initial);
        
        int moves = 0;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
                if (curr.equals(targetStr)) return moves;
                
                int zeroIdx = curr.indexOf('0');
                int row = zeroIdx / 3, col = zeroIdx % 3;
                
                for (int[] dir : dirs) {
                    int newRow = row + dir[0];
                    int newCol = col + dir[1];
                    
                    if (newRow < 0 || newRow >= 2 || newCol < 0 || newCol >= 3) continue;
                    
                    char[] nextState = curr.toCharArray();
                    int newZeroIdx = newRow * 3 + newCol;
                    nextState[zeroIdx] = nextState[newZeroIdx];
                    nextState[newZeroIdx] = '0';
                    
                    String nextStr = new String(nextState);
                    
                    if (!visited.contains(nextStr)) {
                        queue.offer(nextStr);
                        visited.add(nextStr);
                    }
                }
            }
            moves++;
        }

        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 773 (Sliding Puzzle)?

This page provides optimized solutions for LeetCode problem 773 (Sliding Puzzle) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 773 (Sliding Puzzle)?

The time complexity for LeetCode 773 (Sliding Puzzle) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 773 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 773 in Java, C++, or Python.

Back to LeetCode Solutions