[AlgoMastery]
Topics›Queue›BFS with State
📖

BFS with State

Queue
~20 min read
5 practice problems

Overview

BFS with state extends standard BFS to track additional state information beyond just the node/position. Instead of visiting each node once, we visit each (node, state) combination once, where state can represent keys collected, steps taken, obstacles broken, or any other relevant information.

BFS with state is essential for problems where the path to a node matters (like collecting keys, breaking walls, or tracking steps), and the same physical location may need to be visited multiple times with different states. It transforms the problem into a state-space search where each state is a (position, additional_info) tuple.

Key characteristics:

  • State tracking - Track additional information beyond position
  • State-space search - Search in (node, state) space
  • Multiple visits - Same node can be visited with different states
  • State transitions - States change based on actions
  • Visited per state - Mark (node, state) as visited, not just node

How BFS with State Works

BFS with state follows these steps:

  1. State representation - Represent state as (node, state_info)
  2. Initialize - Start with initial (source, initial_state)
  3. While queue is not empty:
  • Dequeue (node, state)
  • Check if (node, state) visited
  • Process node with current state
  • Generate new states based on actions
  • Enqueue (neighbor, new_state) if not visited
  • Mark (node, state) as visited
  1. Repeat until queue is empty or target found

The key difference is tracking state and visiting (node, state) combinations.

Basic BFS with State

BFS tracking keys collected:

function bfsWithKeys(graph: number[][], start: number, keys: Set<number>): number {
  const n = graph.length;
  const queue: [number, Set<number>][] = [[start, new Set(keys)]];
  const visited = new Set<string>();
  
  while (queue.length > 0) {
    const [node, currentKeys] = queue.shift()!;
    const stateKey = `${node}-${Array.from(currentKeys).sort().join(',')}`;
    
    if (visited.has(stateKey)) continue;
    visited.add(stateKey);
    
    // Process node
    // ...
    
    for (const neighbor of graph[node]) {
      const newKeys = new Set(currentKeys);
      // Update keys if needed
      // newKeys.add(newKey);
      
      const newStateKey = `${neighbor}-${Array.from(newKeys).sort().join(',')}`;
      if (!visited.has(newStateKey)) {
        queue.push([neighbor, newKeys]);
      }
    }
  }
  
  return -1;
}

Time: O(V × 2^K) where K is number of keys, Space: O(V × 2^K)

Key insight: State is combination of position and keys held.

Pattern 1: Shortest Path in a Grid with Obstacles

Find shortest path with at most K obstacles:

function shortestPath(grid: number[][], k: number): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const queue: [number, number, number, number][] = [[0, 0, 0, 0]]; // [r, c, obstacles, steps]
  const visited = new Set<string>();
  
  while (queue.length > 0) {
    const [r, c, obstacles, steps] = queue.shift()!;
    const stateKey = `${r},${c},${obstacles}`;
    
    if (visited.has(stateKey)) continue;
    visited.add(stateKey);
    
    if (r === rows - 1 && c === cols - 1) {
      return steps;
    }
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
        const newObstacles = obstacles + (grid[nr][nc] === 1 ? 1 : 0);
        
        if (newObstacles <= k) {
          const newStateKey = `${nr},${nc},${newObstacles}`;
          if (!visited.has(newStateKey)) {
            queue.push([nr, nc, newObstacles, steps + 1]);
          }
        }
      }
    }
  }
  
  return -1;
}

Time: O(rows × cols × k), Space: O(rows × cols × k)

Key insight: State includes obstacles broken so far.

Pattern 2: Keys and Rooms

Collect all keys and reach target:

function shortestPathAllKeys(grid: string[]): number {
  const rows = grid.length;
  const cols = grid[0].length;
  let startR = 0, startC = 0;
  let keyCount = 0;
  
  // Find start and count keys
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '@') {
        startR = r;
        startC = c;
      } else if (grid[r][c] >= 'a' && grid[r][c] <= 'z') {
        keyCount++;
      }
    }
  }
  
  const targetKeys = (1 << keyCount) - 1; // All keys collected
  const queue: [number, number, number, number][] = [[startR, startC, 0, 0]]; // [r, c, keys, steps]
  const visited = new Set<string>();
  
  while (queue.length > 0) {
    const [r, c, keys, steps] = queue.shift()!;
    const stateKey = `${r},${c},${keys}`;
    
    if (visited.has(stateKey)) continue;
    visited.add(stateKey);
    
    if (keys === targetKeys) {
      return steps;
    }
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      
      if (
        nr >= 0 && nr < rows &&
        nc >= 0 && nc < cols &&
        grid[nr][nc] !== '#'
      ) {
        let newKeys = keys;
        
        // Collect key
        if (grid[nr][nc] >= 'a' && grid[nr][nc] <= 'z') {
          const keyIndex = grid[nr][nc].charCodeAt(0) - 'a'.charCodeAt(0);
          newKeys |= (1 << keyIndex);
        }
        
        // Check if have key for lock
        if (grid[nr][nc] >= 'A' && grid[nr][nc] <= 'Z') {
          const lockIndex = grid[nr][nc].charCodeAt(0) - 'A'.charCodeAt(0);
          if ((newKeys & (1 << lockIndex)) === 0) {
            continue; // Don't have key
          }
        }
        
        const newStateKey = `${nr},${nc},${newKeys}`;
        if (!visited.has(newStateKey)) {
          queue.push([nr, nc, newKeys, steps + 1]);
        }
      }
    }
  }
  
  return -1;
}

Time: O(rows × cols × 2^keys), Space: O(rows × cols × 2^keys)

Key insight: Use bitmask to represent keys collected.

Pattern 3: Sliding Puzzle

Solve sliding puzzle with BFS tracking board state:

function slidingPuzzle(board: number[][]): number {
  const target = '123450';
  const start = board.flat().join('');
  
  if (start === target) return 0;
  
  const queue: [string, number][] = [[start, 0]];
  const visited = new Set<string>([start]);
  
  while (queue.length > 0) {
    const [state, moves] = queue.shift()!;
    
    if (state === target) return moves;
    
    const zeroIndex = state.indexOf('0');
    const r = Math.floor(zeroIndex / 3);
    const c = zeroIndex % 3;
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      
      if (nr >= 0 && nr < 2 && nc >= 0 && nc < 3) {
        const newIndex = nr * 3 + nc;
        const arr = state.split('');
        [arr[zeroIndex], arr[newIndex]] = [arr[newIndex], arr[zeroIndex]];
        const newState = arr.join('');
        
        if (!visited.has(newState)) {
          visited.add(newState);
          queue.push([newState, moves + 1]);
        }
      }
    }
  }
  
  return -1;
}

Time: O(6! × 6) = O(4320), Space: O(4320)

Key insight: State is the entire board configuration.

Pattern 4: Word Ladder with Constraints

Word ladder tracking steps and visited words:

function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  
  const queue: [string, number][] = [[beginWord, 1]];
  const visited = new Set<string>([beginWord]);
  
  while (queue.length > 0) {
    const [word, steps] = queue.shift()!;
    
    if (word === endWord) return steps;
    
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {
        const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
        
        if (wordSet.has(newWord) && !visited.has(newWord)) {
          visited.add(newWord);
          queue.push([newWord, steps + 1]);
        }
      }
    }
  }
  
  return 0;
}

Time: O(M × N × 26) where M is word length, N is word list size

Key insight: State includes current word and steps taken.

Pattern 5: Minimum Moves to Reach Target with Rotations

Snake game with rotations:

function minimumMoves(grid: number[][]): number {
  const n = grid.length;
  const queue: [number, number, number, number][] = [[0, 1, 0, 0]]; // [tailR, tailC, horizontal, steps]
  const visited = new Set<string>(['0,1,0']);
  const target = `${n-1},${n-1},0`;
  
  while (queue.length > 0) {
    const [tailR, tailC, horizontal, steps] = queue.shift()!;
    const stateKey = `${tailR},${tailC},${horizontal}`;
    
    if (stateKey === target) return steps;
    
    // Move right
    if (horizontal === 1) {
      if (tailC + 2 < n && grid[tailR][tailC + 2] === 0) {
        const newState = `${tailR},${tailC + 1},1`;
        if (!visited.has(newState)) {
          visited.add(newState);
          queue.push([tailR, tailC + 1, 1, steps + 1]);
        }
      }
    } else {
      if (tailC + 1 < n && grid[tailR][tailC + 1] === 0 && grid[tailR + 1][tailC + 1] === 0) {
        const newState = `${tailR},${tailC + 1},0`;
        if (!visited.has(newState)) {
          visited.add(newState);
          queue.push([tailR, tailC + 1, 0, steps + 1]);
        }
      }
    }
    
    // Move down (similar logic)
    // Rotate (change horizontal state)
    // ...
  }
  
  return -1;
}

Time: O(n²), Space: O(n²)

Key insight: State includes orientation (horizontal/vertical).

Pattern 6: Escape a Large Maze

Escape maze with limited steps:

function isEscapePossible(blocked: number[][], source: number[], target: number[]): boolean {
  const blockedSet = new Set(blocked.map(([r, c]) => `${r},${c}`));
  const maxSteps = blocked.length * (blocked.length - 1) / 2;
  
  function bfs(start: number[], end: number[]): boolean {
    const queue: [number, number, number][] = [[start[0], start[1], 0]];
    const visited = new Set<string>([`${start[0]},${start[1]}`]);
    
    while (queue.length > 0) {
      const [r, c, steps] = queue.shift()!;
      
      if (r === end[0] && c === end[1]) return true;
      if (steps >= maxSteps) return true; // Escaped blocked area
      
      const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
      for (const [dr, dc] of directions) {
        const nr = r + dr;
        const nc = c + dc;
        const key = `${nr},${nc}`;
        
        if (
          nr >= 0 && nr < 1000000 &&
          nc >= 0 && nc < 1000000 &&
          !blockedSet.has(key) &&
          !visited.has(key)
        ) {
          visited.add(key);
          queue.push([nr, nc, steps + 1]);
        }
      }
    }
    
    return false;
  }
  
  return bfs(source, target) && bfs(target, source);
}

Time: O(B²) where B is number of blocked cells

Key insight: Track steps to detect escape from blocked area.

Pattern 7: Open the Lock

Open lock with deadends, tracking current combination:

function openLock(deadends: string[], target: string): number {
  const deadendSet = new Set(deadends);
  if (deadendSet.has('0000')) return -1;
  
  const queue: [string, number][] = [['0000', 0]];
  const visited = new Set<string>(['0000']);
  
  while (queue.length > 0) {
    const [combination, turns] = queue.shift()!;
    
    if (combination === target) return turns;
    
    // Try turning each wheel
    for (let i = 0; i < 4; i++) {
      const digit = parseInt(combination[i]);
      
      // Turn up
      const up = (digit + 1) % 10;
      const newCombUp = combination.slice(0, i) + up + combination.slice(i + 1);
      if (!deadendSet.has(newCombUp) && !visited.has(newCombUp)) {
        visited.add(newCombUp);
        queue.push([newCombUp, turns + 1]);
      }
      
      // Turn down
      const down = (digit - 1 + 10) % 10;
      const newCombDown = combination.slice(0, i) + down + combination.slice(i + 1);
      if (!deadendSet.has(newCombDown) && !visited.has(newCombDown)) {
        visited.add(newCombDown);
        queue.push([newCombDown, turns + 1]);
      }
    }
  }
  
  return -1;
}

Time: O(10^4) = O(10000), Space: O(10000)

Key insight: State is the lock combination.

When to Use BFS with State

Use BFS with state when you see these signals:

  • "Keys and locks" - Need to collect keys before opening locks
  • "Obstacles with limit" - Can break at most K obstacles
  • "Steps tracking" - Need to track steps or moves
  • "State transitions" - State changes based on actions
  • "Same position different states" - Same location visited with different states
  • "Configuration search" - Searching in configuration space
  • "Puzzle solving" - Sliding puzzle, lock combinations

Key distinction:

  • BFS with State - Track additional state, visit (node, state)
  • Regular BFS - Only track position, visit node once
  • DFS with State - Similar but depth-first

BFS with State vs Regular BFS

| Aspect | BFS with State | Regular BFS |

|--------|---------------|-------------|

| Visited | (node, state) combinations | Nodes only |

| State tracking | Track additional info | No state tracking |

| Multiple visits | Same node with different states | Visit node once |

| Complexity | O(V × S) where S is state space | O(V + E) |

| Use case | Keys, obstacles, steps | Simple shortest path |

Remember:

  • BFS with state for problems requiring state tracking
  • Regular BFS for simple shortest path problems

Template (BFS with State)

function bfsWithStateTemplate(
  graph: number[][],
  start: number,
  initialState: StateType
): number {
  const queue: [number, StateType][] = [[start, initialState]];
  const visited = new Set<string>();
  
  while (queue.length > 0) {
    const [node, state] = queue.shift()!;
    const stateKey = `${node}-${serializeState(state)}`;
    
    if (visited.has(stateKey)) continue;
    visited.add(stateKey);
    
    // Check if target reached
    if (isTarget(node, state)) {
      return getSteps(state);
    }
    
    for (const neighbor of graph[node]) {
      const newState = updateState(state, node, neighbor);
      const newStateKey = `${neighbor}-${serializeState(newState)}`;
      
      if (!visited.has(newStateKey) && isValidState(newState)) {
        queue.push([neighbor, newState]);
      }
    }
  }
  
  return -1;
}

Template (2D Grid with State)

function bfs2DWithStateTemplate(
  grid: number[][],
  start: [number, number],
  initialState: StateType
): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const queue: [number, number, StateType][] = [[start[0], start[1], initialState]];
  const visited = new Set<string>();
  
  while (queue.length > 0) {
    const [r, c, state] = queue.shift()!;
    const stateKey = `${r},${c},${serializeState(state)}`;
    
    if (visited.has(stateKey)) continue;
    visited.add(stateKey);
    
    // Process cell with state
    // ...
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
        const newState = updateState(state, grid[nr][nc]);
        const newStateKey = `${nr},${nc},${serializeState(newState)}`;
        
        if (!visited.has(newStateKey) && isValidState(newState)) {
          queue.push([nr, nc, newState]);
        }
      }
    }
  }
  
  return -1;
}

Time and Space Complexity

General BFS with State

  • Time: O(V × S) where V is nodes, S is state space size
  • Space: O(V × S) for visited set and queue

Specific Examples

  • Keys and rooms: O(rows × cols × 2^keys)
  • Obstacles: O(rows × cols × k) where k is max obstacles
  • Sliding puzzle: O(6! × 6) = O(4320)
  • Lock combination: O(10^4) = O(10000)

Note: State space can be exponential (like 2^keys), making these problems harder.

Practice Tips

  1. Identify state - Determine what additional info to track
  2. State representation - Use bitmask, set, or object for state
  3. State serialization - Convert state to string for visited set
  4. State transitions - Define how state changes with actions
  5. Visited per state - Mark (node, state) as visited
  6. State validation - Check if state is valid before enqueueing
  7. Early termination - Return when target state reached

Common Mistakes

  1. Not tracking state - Forgetting to include state in visited check
  2. Wrong state representation - Not serializing state correctly
  3. State space explosion - Not optimizing state representation
  4. Missing state transitions - Not updating state correctly
  5. Visited wrong - Marking node visited instead of (node, state)
  6. State validation - Not checking if state is valid
  7. Memory issues - State space too large, causing memory problems

Real-World Applications

BFS with state is used extensively in:

  • Game AI - Pathfinding with keys, obstacles, power-ups
  • Robotics - Navigation with constraints and state
  • Puzzle Games - Solving sliding puzzles, lock combinations
  • Security Systems - Access control with keys and permissions
  • Resource Management - Tracking resources during pathfinding
  • Adventure Games - Collecting items, unlocking doors
  • Escape Rooms - Solving puzzles with state dependencies
  • Maze Navigation - Navigation with dynamic obstacles

Related Concepts

  • Breadth-First Search (BFS) - Foundation for BFS with state
  • State-Space Search - General concept of searching state space
  • Dynamic Programming - Sometimes overlaps with state tracking
  • Graph Traversal - Extending graph traversal with state
  • Bitmasking - Common technique for state representation

Summary

BFS with state extends BFS to track additional information:

  • State tracking - Track keys, obstacles, steps, etc.
  • State-space search - Search in (node, state) space
  • Multiple visits - Same node with different states
  • State transitions - States change based on actions
  • Essential - For keys/locks, obstacles, puzzle problems

Key takeaways:

  • Identify what state to track
  • Represent state efficiently (bitmask, set, etc.)
  • Mark (node, state) as visited, not just node
  • Define state transitions correctly
  • Essential for problems requiring state tracking

Mastering BFS with state will help you solve keys and rooms, obstacle problems, and puzzle-solving challenges efficiently in coding interviews.

← PreviousMulti-Source BFSNext →Bidirectional BFS