DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Solve the Rat in a Maze problem using backtracking — navigate a grid, mark visited cells, backtrack on dead ends, and find all possible paths.
Problem Statement
Given an N×N binary grid where 1 represents an open cell and 0 represents a wall, a rat starts at the top-left corner (0,0) and must reach the bottom-right corner (N-1, N-1). The rat can move in four directions: Down (D), Right (R), Up (U), and Left (L). Find all possible paths (or determine if one exists), without visiting any cell more than once.
Intuition
Picture yourself in a physical maze. At each intersection, you have up to four corridors to try. You pick one and walk forward. If you hit a wall or a cell you have already visited, you turn around and try a different corridor from the last intersection. This is exactly what the algorithm does — recursively explore directions, marking cells as visited to avoid cycles, and unmarking them when backtracking.
Algorithm Steps
- Start at cell (0, 0). If it is blocked (value 0), no solution exists.
- Mark the current cell as visited.
- If the current cell is the destination (N-1, N-1), record the path.
- For each direction (D, L, R, U — often sorted alphabetically for lexicographic paths):
- Compute the next cell coordinates.
- If the next cell is within bounds, is open (value 1), and is not visited, recurse from that cell.
- After exploring all directions, unmark the current cell (backtrack) so it is available for other paths.
Dry Run on a 4×4 Grid
Example
Grid: Legend: 1=open, 0=wall
1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1
| Start (0,0) | mark visited |
| Move D | (1,0) → mark visited |
| Move D | (2,0) → mark visited |
| Move D | (3,0) = 0, WALL. Skip. |
| Move R | (2,1) → mark visited |
| Move D | (3,1) → mark visited |
| Move R | (3,2) → mark visited |
| Move R | (3,3) → DESTINATION! Path: "DDRDRR" |
| Move R | (2,2) = 0, WALL. Skip. |
| Move R | (1,1) → mark visited |
| Move D | (2,1) → mark visited |
| Move D | (3,1) → mark visited |
| Move R | (3,2) → mark visited |
| Move R | (3,3) → DESTINATION! Path: "DRDDRR" |
Both paths reach the destination. The algorithm finds all valid paths by exhaustive backtracking.
Python Implementation — Find All Paths
Example
def find_all_paths(maze):
n = len(maze)
if maze[0][0] == 0 or maze[n-1][n-1] == 0:
return []
paths = []
visited = [[False] * n for _ in range(n)]
# Direction vectors: Down, Left, Right, Up (alphabetical order)
directions = [(1, 0, 'D'), (0, -1, 'L'), (0, 1, 'R'), (-1, 0, 'U')]
def backtrack(row, col, path):
if row == n - 1 and col == n - 1:
paths.append(path)
return
for dr, dc, char in directions:
new_row, new_col = row + dr, col + dc
if (0 <= new_row < n and 0 <= new_col < n and
maze[new_row][new_col] == 1 and not visited[new_row][new_col]):
visited[new_row][new_col] = True
backtrack(new_row, new_col, path + char)
visited[new_row][new_col] = False # backtrack
visited[0][0] = True
backtrack(0, 0, "")
return sorted(paths)
# Test
maze = [
[1, 0, 0, 0],
[1, 1, 0, 1],
[1, 1, 0, 0],
[0, 1, 1, 1]
]
result = find_all_paths(maze)
for p in result:
print(p)
# Output: DDRDRR, DRDDRR
C++ Implementation
Example
#include <vector>
#include <string>
#include <iostream>
using namespace std;
class RatInMaze {
int n;
vector<string> paths;
int dx[4] = {1, 0, 0, -1}; // D, L, R, U
int dy[4] = {0, -1, 1, 0};
char dir[4] = {'D', 'L', 'R', 'U'};
public:
vector<string> solve(vector<vector<int>>& maze) {
n = maze.size();
if (maze[0][0] == 0) return {};
vector<vector<bool>> visited(n, vector<bool>(n, false));
visited[0][0] = true;
backtrack(maze, visited, 0, 0, "");
return paths;
}
private:
void backtrack(vector<vector<int>>& maze, vector<vector<bool>>& visited,
int row, int col, string path) {
if (row == n - 1 && col == n - 1) {
paths.push_back(path);
return;
}
for (int i = 0; i < 4; i++) {
int nr = row + dx[i], nc = col + dy[i];
if (nr >= 0 && nr < n && nc >= 0 && nc < n &&
maze[nr][nc] == 1 && !visited[nr][nc]) {
visited[nr][nc] = true;
backtrack(maze, visited, nr, nc, path + dir[i]);
visited[nr][nc] = false;
}
}
}
};
int main() {
vector<vector<int>> maze = {{1,0,0,0},{1,1,0,1},{1,1,0,0},{0,1,1,1}};
RatInMaze solver;
auto result = solver.solve(maze);
for (auto& p : result) cout << p << endl;
}
Single Path Variant (Return true/false)
Sometimes the problem only asks whether a path exists:
Example
def has_path(maze):
n = len(maze)
visited = [[False] * n for _ in range(n)]
def dfs(row, col):
if row == n - 1 and col == n - 1:
return True
visited[row][col] = True
for dr, dc in [(1,0), (0,1), (-1,0), (0,-1)]:
nr, nc = row + dr, col + dc
if (0 <= nr < n and 0 <= nc < n and
maze[nr][nc] == 1 and not visited[nr][nc]):
if dfs(nr, nc):
return True
visited[row][col] = False # only needed if finding ALL paths
return False
return dfs(0, 0) if maze[0][0] == 1 else False
Key insight: If you only need *one* path, you do NOT need to unmark visited cells (no backtrack). If you need *all* paths, you must unmark after each recursive call returns.
Complexity Analysis
| Metric | Value | Explanation |
|---|---|---|
| Time (all paths) | O(4^(N²)) | Worst case: every cell reachable, 4 choices each |
| Time (one path) | O(N²) | Each cell visited at most once |
| Space | O(N²) | Visited matrix + recursion stack up to N² deep |
In practice, walls and the visited constraint prune heavily, making the actual runtime much smaller than the theoretical bound.
Common Variations
- Only Down and Right moves: Simpler — no cycles possible, no need for visited array. Each path has exactly (2N-2) moves.
- Weighted grid: Find the path with minimum cost — combine backtracking with pruning (if current cost exceeds known best, prune).
- Multiple rats or multiple destinations: Explore paths for each independently or find intersecting paths.
- Print the grid with path marked: Replace visited cells with a marker on the solution path.
Real-World Applications
- Robot navigation: Autonomous robots planning paths through physical spaces with obstacles
- Network routing: Finding paths through network topologies with failed nodes
- Game AI: NPC pathfinding in tile-based games (though BFS/A* is usually preferred for shortest path)
- PCB routing: Trace routing on circuit boards avoiding existing traces
Key Takeaways
The Rat in a Maze problem is a natural application of backtracking to grid traversal. The core pattern is: check bounds and constraints, mark visited, recurse in all valid directions, then unmark. Remember that unmarking is only necessary when you need *all* paths — for a single path, early termination without backtracking suffices.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Rat in a Maze.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, backtracking, rat, maze
Related Data Structures & Algorithms Topics
Continue learning this concept
BacktrackingBacktracking FundamentalsMaster the backtracking algorithmic paradigm — understand state-space trees, pruning strategies, and how backtracking systematically explores solution spaces.BacktrackingBacktracking Practice ProblemsMaster essential backtracking interview problems — Word Search, Permutations, Combination Sum, and Palindrome Partitioning with detailed approaches and code.BacktrackingN-Queens ProblemSolve the classic N-Queens problem using backtracking — learn constraint checking, state-space exploration, and trace through a complete 4-Queens walkthrough.BacktrackingSubset GenerationGenerate all subsets (power set) using backtracking and bit manipulation — understand the include/exclude pattern and enumerate 2^n possibilities efficiently.BacktrackingSudoku SolverBuild a complete Sudoku solver using backtracking with constraint propagation — validate placements across rows, columns, and 3×3 boxes, and backtrack on conflicts.RecursionBacktracking with RecursionLearn backtracking techniques combined with recursion for constraint problems.