Skip to content

Latest commit

 

History

History

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 

Readme.md

Certainly! Breadth-First Search (BFS) is a fundamental graph traversal algorithm that’s commonly applied to problems involving trees, graphs, and grids. Here’s a list of some classic and commonly encountered BFS problems on LeetCode:


1. BFS on Trees

  1. Binary Tree Level Order Traversal - Problem 102

    • Traverse a binary tree level by level.
  2. Binary Tree Zigzag Level Order Traversal - Problem 103

    • Traverse a binary tree level by level, alternating the direction at each level.
  3. Binary Tree Right Side View - Problem 199

    • Get the rightmost node at each level of a binary tree.
  4. Minimum Depth of Binary Tree - Problem 111

    • Find the shortest path from the root node to a leaf node.
  5. Cousins in Binary Tree - Problem 993

    • Check if two nodes are at the same depth but have different parents.

2. BFS on Graphs

  1. Shortest Path in Binary Matrix - Problem 1091

    • Find the shortest path in a binary matrix using BFS.
  2. Word Ladder - Problem 127

    • Transform one word into another by changing one letter at a time, finding the minimum transformation steps.
  3. Word Ladder II - Problem 126

    • Similar to Word Ladder but asks for all shortest transformation sequences.
  4. Rotting Oranges - Problem 994

    • Simulate the spread of rot among oranges in a grid.
  5. Course Schedule - Problem 207

    • Determine if you can finish all courses given prerequisites (cycle detection in a directed graph).

3. BFS on Grids (2D Arrays)

  1. Number of Islands - Problem 200

    • Find the number of connected islands in a grid.
  2. Pacific Atlantic Water Flow - Problem 417

    • Determine which cells can flow to both the Pacific and Atlantic oceans.
  3. Surrounded Regions - Problem 130

    • Capture regions in a grid surrounded by a boundary.
  4. As Far from Land as Possible - Problem 1162

    • Find the water cell with the maximum distance from any land cell.
  5. 01 Matrix - Problem 542

    • For each cell in a matrix, find the distance to the nearest zero.

4. BFS in Puzzle or Pathfinding Problems

  1. Open the Lock - Problem 752

    • Find the minimum number of turns required to unlock a lock given a list of deadends.
  2. Sliding Puzzle - Problem 773

    • Solve a 2x3 sliding puzzle to match the target configuration.
  3. Jump Game III - Problem 1306

    • Determine if you can reach a position with a zero in an array by jumping.
  4. The Maze - Problem 490

    • Check if there’s a path in a grid maze from start to destination.
  5. The Maze II - Problem 505

    • Find the shortest path in a grid maze.

5. Multi-Source BFS Problems

  1. Cut Off Trees for Golf Event - Problem 675

    • Find the shortest path to cut trees in a grid with obstacles.
  2. Shortest Distance from All Buildings - Problem 317

    • Find the minimum distance to build a house accessible to all buildings in a grid.
  3. Walls and Gates - Problem 286

    • Fill each empty room with the distance to its nearest gate.

6. BFS for Connected Components

  1. Graph Valid Tree - Problem 261

    • Check if an undirected graph forms a valid tree.
  2. Connected Components in an Undirected Graph - Problem 323

    • Count the number of connected components in an undirected graph.
  3. Clone Graph - Problem 133

    • Create a deep copy of a graph.
  4. Is Graph Bipartite? - Problem 785

    • Determine if a graph can be colored with two colors.

This list provides a range of BFS problems from various categories on LeetCode. Let me know if you’d like more details on any of these problems!