Compute shortest path to collect all keys

Q: Compute shortest path to collect all keys

This question evaluates proficiency in state-space representation, graph search and shortest-path techniques, compact state encoding (such as bitmasking), and algorithmic time/space complexity analysis within the Coding & Algorithms domain.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given an m×n grid containing walls (#), open cells (.), a single start cell (@), up to six keys labeled 'a'–'f', and matching doors 'A'–'F' that can be passed only after obtaining their corresponding key. From any cell, you may move one step up, down, left, or right to an in-bounds non-wall cell. Return the minimum number of steps required to collect all keys, or -1 if it is impossible. Handle m, n up to 30. Describe your state representation, search strategy, pruning, and how you detect revisits efficiently. Provide time and space complexity and key test cases.

Compute shortest path to collect all keys

Overview

Comments (0)