Katkat
Back

Solve a Key-Door Corridor Maze

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to model a search space beyond simple coordinate traversal by incorporating state-dependent constraints (keys) using Breadth-First Search.

Problem Statement

You are navigating a corridor represented by a string of length n. The corridor consists of empty cells ('.'), walls ('#'), keys (lowercase letters 'a'-'z'), and locked doors (uppercase letters 'A'-'Z').

  • You start at index 0.
  • Moving to an adjacent cell takes 1 unit of time.
  • To pass through a door (e.g., 'A'), you must have already picked up the corresponding key ('a').
  • Keys can be collected by stepping on their index and are stored in your inventory permanently.

Return the minimum time to reach the last index n - 1. If it is impossible, return -1.

Function Signature

def min_time_to_exit(corridor: str) -> int:

Constraints

  • n (length of corridor) is between 1 and 2000.
  • You can only carry one of each key type.

Example 1

Input: corridor = ".a.A.b.B." Output: 8 Explanation: Move to index 1 (key 'a'), back to 3 (door 'A'), then 5 (key 'b'), then 7 (door 'B'). Total steps: 8.

Example 2

Input: corridor = ".A.a." Output: -1 Explanation: The door 'A' appears before key 'a', making it unreachable.

Edge Cases

  • Corridor with no doors or keys.
  • Corridor where the exit is blocked by a door for which the key is unreachable.
  • Corridors with multiple instances of the same key.

Hints

Hint 1

A standard BFS finds the shortest path, but your current 'position' alone is not enough to define a state.

Hint 2

Define a state as a tuple of (current_index, bitmask_of_collected_keys).

Hint 3

Since the corridor is one-dimensional, observe that you only care about keys you have collected to open doors that appear later in your path.

Follow-up questions

  • How would the complexity change if the corridor were a 2D grid instead of a 1D string?
  • If keys could be used multiple times but were consumed upon use, how would that change the state representation?
  • What if there are multiple keys of the same type? Does the state definition need to change?