MANG Problem #50: Sliding Puzzle (Hard)

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

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.

2. Approach: BFS on String States

This is finding the shortest path in an unweighted graph, where each "Node" is a specific configuration of the board.

State Representation: A 2D matrix is hard to hash and store in a visited set. We serialize the 2x3 board into a 6-character string (e.g., "123450").
Target State: "123450".
Transitions (Edges):
- The 0 tile can swap with its neighbors.
- Since we flattened a 2x3 grid to 1D, the neighbors of index i are hardcoded:
  - 0 can swap with 1, 3
  - 1 can swap with 0, 2, 4
  - 2 can swap with 1, 5
  - 3 can swap with 0, 4
  - 4 can swap with 1, 3, 5
  - 5 can swap with 2, 4
BFS: Push the initial string to a Queue. Generate all valid swaps, check if they equal the target, and push unseen states back to the Queue.

3. Java Implementation

public int slidingPuzzle(int[][] board) {
    String target = "123450";
    StringBuilder start = new StringBuilder();
    for (int[] row : board) {
        for (int val : row) {
            start.append(val);
        }
    }
    
    if (start.toString().equals(target)) return 0;
    
    // Map 1D index to valid neighbor 1D indices
    int[][] dirs = new int[][]{
        {1, 3}, {0, 2, 4}, {1, 5},
        {0, 4}, {1, 3, 5}, {2, 4}
    };
    
    Queue<String> q = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    
    q.offer(start.toString());
    visited.add(start.toString());
    int moves = 0;
    
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            String curr = q.poll();
            if (curr.equals(target)) return moves;
            
            int zeroIndex = curr.indexOf('0');
            for (int dir : dirs[zeroIndex]) {
                String nextState = swap(curr, zeroIndex, dir);
                if (!visited.contains(nextState)) {
                    visited.add(nextState);
                    q.offer(nextState);
                }
            }
        }
        moves++;
    }
    return -1;
}

private String swap(String str, int i, int j) {
    char[] chars = str.toCharArray();
    char temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;
    return new String(chars);
}

4. 5-Minute "Video-Style" Walkthrough

The Graph Abstraction: There is no matrix traversal here. Think of "412503" as Node A. Swapping 0 with 5 gives "412053", which is Node B. We are just running standard BFS from Node A to Node Target.
The Index Map: The dirs array is the secret weapon. It translates 2D adjacency into 1D arrays, completely eliminating the need for complex if (r > 0) ... bounds checking during the BFS loop.
The Serialization: Using Strings makes equality checks curr.equals(target) and HashSet lookups incredibly fast and built-in to Java.

5. Interview Discussion

Interviewer: "What is the time complexity?"
You: "O(V + E). The number of vertices $V$ is the total possible states of a 2x3 board, which is $6! = 720$. For each state, we have at most 3 edges. So it's extremely fast and strictly bounded."
Interviewer: "Can we use A* Search for this?"
You: "Yes. For a 2x3 board, BFS is fast enough. If the board was 4x4 (15-puzzle), BFS would time out. We would need A* using the Manhattan Distance of each tile from its target position as the heuristic."

5. Verbal Interview Script (Staff Tier)

Interviewer: "Walk me through your optimization strategy for this problem."

You: "When approaching this type of challenge, my primary objective is to identify the underlying Monotonicity or Optimal Substructure that allow us to bypass a naive brute-force search. In my implementation of 'MANG Problem #50: Sliding Puzzle (Hard)', I focused on reducing the time complexity by leveraging a HashMap-based lookup. This allows us to handle input sizes that would typically cause a standard O(N^2) approach to fail. Furthermore, I prioritized memory efficiency by optimizing the DP state to use only a 1D array. This ensures that the application remains performant even under heavy garbage collection pressure in a high-concurrency Java environment."

6. Staff-Level Interview Follow-Ups

Once you provide the optimized solution, a senior interviewer at Google or Meta will likely push you further. Here is how to handle the most common follow-ups:

Follow-up 1: "How does this scale to a Distributed System?"

If the input data is too large to fit on a single machine (e.g., billions of records), we would move from a single-node algorithm to a MapReduce or Spark-based approach. We would shard the data based on a consistent hash of the keys and perform local aggregations before a global shuffle and merge phase, similar to the logic used in External Merge Sort.

Follow-up 2: "What are the Concurrency implications?"

In a multi-threaded Java environment, we must ensure that our state (e.g., the DP table or the frequency map) is thread-safe. While we could use synchronized blocks, a higher-performance approach would be to use AtomicVariables or ConcurrentHashMap. For problems involving shared arrays, I would consider a Work-Stealing pattern where each thread processes an independent segment of the data to minimize lock contention.

7. Performance Nuances (The Java Perspective)

Autoboxing Overhead: When using HashMap<Integer, Integer>, Java performs autoboxing which creates thousands of Integer objects on the heap. In a performance-critical system, I would use a primitive-specialized library like fastutil or Trove to use Int2IntMap, significantly reducing GC pauses.
Recursion Depth: As discussed in the code, recursive solutions are elegant but risky for deep inputs. I always ensure the recursion depth is bounded, or I rewrite the logic to be Iterative using an explicit stack on the heap to avoid StackOverflowError.

Key Takeaways

The 0 tile can swap with its neighbors.
Since we flattened a 2x3 grid to 1D, the neighbors of index i are hardcoded:
0 can swap with 1, 3