algoadvance

Leetcode 752. Open the Lock

Problem Statement:

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example, we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be stuck. Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Clarifying Questions:

  1. Will the deadends and target always be valid 4-digit strings consisting of characters 0-9?
    • Yes.
  2. Can the target be the same as the initial '0000' state?
    • Yes, in which case the result should be 0 moves.
  3. Are the deadends guaranteed to not include the initial state '0000'?
    • No, deadends might include '0000', in which case it’s impossible to start, and the answer should be -1.

Strategy:

  1. Breadth-First Search (BFS): Since we need the minimum number of turns (shortest path), BFS is appropriate.
  2. Queue for BFS: Use a queue to track the lock states at different levels of the BFS.
  3. Set for Dead-ends and Visited Nodes: Maintain a set for dead-ends and visited nodes to avoid revisiting.
  4. Generate Next States: Create a helper function to generate the next possible states from the current state by rotating each wheel forward and backward.

Code:

import java.util.*;

public class OpenLock {
    public int openLock(String[] deadends, String target) {
        String start = "0000";
        
        // Convert array to set for quick lookup
        Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));
        if (deadSet.contains(start)) {
            return -1;
        }

        // Queue for BFS
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        
        // Set for visited nodes
        Set<String> visited = new HashSet<>();
        visited.add(start);
        
        int depth = 0;
        
        // Perform BFS
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String current = queue.poll();
                
                // Check if we have reached the target
                if (current.equals(target)) {
                    return depth;
                }
                
                // Get all possible next states
                for (String next : getNextStates(current)) {
                    if (!deadSet.contains(next) && !visited.contains(next)) {
                        queue.offer(next);
                        visited.add(next);
                    }
                }
            }
            depth++; // Increment depth for each level of BFS
        }
        
        return -1; // Target not reachable
    }
    
    private List<String> getNextStates(String current) {
        List<String> nextStates = new ArrayList<>();
        char[] chars = current.toCharArray();
        
        for (int i = 0; i < 4; i++) {
            char originalChar = chars[i];
            
            // Move wheel upwards
            chars[i] = originalChar == '9' ? '0' : (char) (originalChar + 1);
            nextStates.add(new String(chars));
            
            // Move wheel downwards
            chars[i] = originalChar == '0' ? '9' : (char) (originalChar - 1);
            nextStates.add(new String(chars));
            
            // Restore the original character
            chars[i] = originalChar;
        }
        
        return nextStates;
    }
    
    public static void main(String[] args) {
        OpenLock ol = new OpenLock();
        String[] deadends = {"0201", "0101", "0102", "1212", "2002"};
        String target = "0202";
        System.out.println(ol.openLock(deadends, target)); // Output: 6
    }
}

Time Complexity:

Overall Time Complexity: O(10000) (as it explores the entire space of lock configurations).

Overall Space Complexity: O(10000) for the queue and visited set.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI