Rat in a Maze Problem | Backtracking Explained Step by Step | Java DSA

Lecture Resources https://github.com/Tiwarishashwat/Java-Plus-DSA-Placement-Course/tree/main/Lecture-101%20-%20Rat%20in%20a%20maze In this video, we solve the Rat in a Maze problem using Backtracking in Java — one of the most important recursion-based problems for coding interviews. 🔍 Problem Overview You are given an N x N maze where: 1 → path is open 0 → path is blocked A rat starts from the top-left corner (0,0) and needs to reach the bottom-right corner (n-1,n-1). The rat can move in four directions: D → Down L → Left R → Right U → Up Your task is to find all possible paths the rat can take. 🧠 Core Concepts Used Recursion Backtracking Visited marking Path building using StringBuilder Undoing choices (backtrack step) ⚙️ How the Algorithm Works Start from (0,0) Check boundary conditions and blocked cells Mark the current cell as visited Explore all 4 directions (D, L, R, U) Add path when destination is reached Backtrack by: Removing last direction Marking cell as unvisited again 📌 Key Backtracking Idea Try → Explore → Undo This ensures: No infinite loops All valid paths are explored Correct paths are restored after recursion ⏱️ Complexity Analysis Time Complexity: Exponential (all possible paths) Space Complexity: O(N²) due to recursion stack + visited grid 🔥 Why This Problem is Important ✔ Very common in GFG, FAANG & interviews ✔ Builds foundation for: N-Queens Sudoku Solver Word Search Maze & grid backtracking problems Timestamp: 0:00 - Rat in a maze 8:50 - Code 16:59 - Outro