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, labeled ‘0’ to ‘9’. The wheels can rotate freely, and 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, meaning if the lock displays any of these codes, the wheels of the lock get stuck, and you cannot turn them anymore.

Given a target representing the code that you want to unlock, 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 deadend "0102".

Clarifying Questions:

  1. Are all inputs guaranteed to be valid (within bounds and non-empty)?
    • Yes, assume all inputs are valid.
  2. Can we assume the deadends list does not contain duplicates?
    • Yes, you can assume there are no duplicate deadends.
  3. What type of outcomes should be handled?
    • Handle basic cases where the target may be achieved directly, and complex cases with deadends preventing easy movement.

Strategy:

  1. Breadth-First Search (BFS):
    • Use BFS because it explores all possible states level by level, ensuring the shortest path is found.
    • Start from the initial state, “0000”, and explore all possible one-move states.
    • Use a queue to manage the BFS process and a set to track states that have already been visited.
    • Handle deadends by initializing the visited set with them.
    • Return the depth (number of moves) when the target state is reached.
    • If the queue is exhausted without finding the target, return -1.
  2. Movement Calculation:
    • For each digit in the current state, consider moving ‘up’ and ‘down’ (from 0 can go to 9, and from 9 can go to 0).

Code:

#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>

using namespace std;

int openLock(vector<string>& deadends, string target) {
    unordered_set<string> dead(deadends.begin(), deadends.end());
    unordered_set<string> visited;
    queue<string> q;
    int steps = 0;

    q.push("0000");
    visited.insert("0000");

    while (!q.empty()) {
        int qsize = q.size();
        for (int i = 0; i < qsize; ++i) {
            string curr = q.front();
            q.pop();
            
            // If the current state is in the deadends, skip it
            if (dead.find(curr) != dead.end()) continue;
            
            // If the target is found, return steps
            if (curr == target) return steps;

            // Explore the next states
            for (int j = 0; j < 4; ++j) {
                string up = curr;
                string down = curr;

                // Rotate the j-th wheel up
                up[j] = (curr[j] - '0' + 1) % 10 + '0';
                if (visited.find(up) == visited.end()) {
                    q.push(up);
                    visited.insert(up);
                }
                
                // Rotate the j-th wheel down
                down[j] = (curr[j] - '0' + 9) % 10 + '0';
                if (visited.find(down) == visited.end()) {
                    q.push(down);
                    visited.insert(down);
                }
            }
        }
        ++steps;
    }

    // If the target was never reached
    return -1;
}

int main() {
    vector<string> deadends = {"0201","0101","0102","1212","2002"};
    string target = "0202";
    cout << openLock(deadends, target) << endl; // Output: 6
    return 0;
}

Time Complexity:

This approach ensures the shortest path is found from the start state to the target while avoiding deadends efficiently through BFS.

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