72Laboratories

Essential Problem-Solving Patterns for DSA

Mastering Data Structures and Algorithms (DSA) requires understanding key problem-solving patterns that recur across problems. These patterns help recognize the problem’s structure and apply efficient techniques. Below is a concise overview of essential patterns, optimized for clarity and practical use.

---

1. Sliding Window

• Use Case: Contiguous subarrays/substrings with constraints (e.g., max sum, longest substring with k distinct characters).
• Key Idea: Maintain a “window” that expands/shrinks based on conditions, avoiding redundant computations.
• Examples:
  • Longest substring with at most k distinct characters
  • Maximum sum subarray of size k
  • Minimum window substring
• Implementation: Use two pointers (left, right) or a hash map to track elements.
• Time Complexity: O(n).

---

2. Two Pointers

• Use Case: Comparison/manipulation from two ends or positions (e.g., pair sum, reverse array).
• Key Idea: Two pointers traverse the data structure (array, list, string) from different directions/paces.
• Types:
  • Opposite Ends: Start/end (e.g., reverse array).
  • Same Direction: Fast/slow pointers (e.g., cycle detection).
  • Pair Sum: Find pairs summing to a target.
• Examples:
  • Two Sum (sorted array)
  • Remove duplicates from sorted array
  • Detect cycle in linked list
• Time Complexity: O(n).

---

3. Fast and Slow Pointers (Floyd’s Cycle Detection)

• Use Case: Cycles or midpoints in linked lists/arrays.
• Key Idea: Two pointers at different speeds (fast: 2x slow) to detect cycles or find midpoints.
• Examples:
  • Find middle of linked list
  • Detect cycle in linked list
  • Find cycle start
• Time Complexity: O(n), O(1) space.

---

4. Binary Search

• Use Case: Sorted data or halving search space (e.g., find element, rotated array).
• Key Idea: Divide search space in half each step.
• Variants:
  • Standard binary search
  • First/last occurrence
  • Rotated sorted array
  • Peak element
• Examples:
  • Search in sorted array
  • Square root of a number
  • Rotated sorted array
• Time Complexity: O(log n).

---

5. Depth-First Search (DFS)

• Use Case: Graph, tree, or grid traversal/exploration (e.g., connected components, pathfinding).
• Key Idea: Explore branch fully before backtracking (recursion/stack).
• Examples:
  • Number of islands
  • Path sum in binary tree
  • Detect cycle in graph
• Time Complexity: O(V + E) for graphs; O(n) for trees.
• Space Complexity: O(h) (h = height/depth).

---

6. Breadth-First Search (BFS)

• Use Case: Level-order traversal or shortest path in unweighted graphs (e.g., maze).
• Key Idea: Explore neighbors at current level before next (queue).
• Examples:
  • Shortest path in grid
  • Level-order binary tree traversal
  • Word ladder
• Time Complexity: O(V + E) for graphs; O(n) for trees.
• Space Complexity: O(w) (w = max width).

---

7. Backtracking

• Use Case: Explore all possible solutions (e.g., permutations, N-Queens).
• Key Idea: Build solution incrementally, abandon invalid partial solutions.
• Examples:
  • N-Queens
  • Subsets
  • Permutations
  • Sudoku solver
• Time Complexity: Often exponential (e.g., O(n!) for permutations).
• Implementation: Recursion with “undo” mechanism.

---

8. Dynamic Programming (DP)

• Use Case: Optimization or overlapping subproblems (e.g., knapsack, longest common subsequence).
• Key Idea: Break into subproblems, store results (memoization/tabulation).
• Types:
  • Top-Down: Recursive with memoization.
  • Bottom-Up: Iterative with table.
• Examples:
  • Fibonacci
  • 0/1 Knapsack
  • Longest increasing subsequence
  • Minimum path sum
• Time Complexity: Varies (e.g., O(n) for Fibonacci, O(n²) for LCS).
• Space Complexity: O(n) to O(n²).

---

9. Greedy

• Use Case: Local optimal choices lead to global optimum (e.g., activity selection, MST).
• Key Idea: Make best choice at each step without reconsidering.
• Examples:
  • Activity selection
  • Kruskal’s/Prim’s MST
  • Huffman coding
• Time Complexity: Varies (e.g., O(n log n) for sorting-based).
• Tip: Verify greedy choice property and optimal substructure.

---

10. Divide and Conquer

• Use Case: Break into independent subproblems, solve, combine (e.g., merge sort).
• Key Idea: Divide, solve recursively, merge results.
• Examples:
  • Merge sort
  • Quick sort
  • Closest pair of points
• Time Complexity: Varies (e.g., O(n log n) for merge sort).
• Space Complexity: Varies (e.g., O(n) for merge sort).

---

11. Topological Sorting

• Use Case: Directed acyclic graphs (DAGs) with dependencies (e.g., course scheduling).
• Key Idea: Order vertices so edge u→v means u before v.
• Approaches:
  • DFS-based
  • Kahn’s algorithm (BFS-based)
• Examples:
  • Course schedule
  • Alien dictionary
• Time Complexity: O(V + E).
• Space Complexity: O(V).

---

12. Union-Find (Disjoint Set)

• Use Case: Grouping or connectivity (e.g., connected components, Kruskal’s).
• Key Idea: Maintain disjoint groups, support union/merge and find.
• Optimizations: Path compression, union by rank.
• Examples:
  • Kruskal’s MST
  • Number of connected components
  • Friend circles
• Time Complexity: Nearly O(1) per operation (amortized).
• Space Complexity: O(n).

---

13. Monotonic Stack/Queue

• Use Case: Next/previous greater/smaller element (e.g., histogram area).
• Key Idea: Maintain stack/queue in increasing/decreasing order.
• Examples:
  • Next greater element
  • Largest rectangle in histogram
  • Trapping rainwater
• Time Complexity: O(n).
• Space Complexity: O(n).

---

14. Prefix Sum

• Use Case: Cumulative sums or range queries (e.g., subarray sum equals k).
• Key Idea: Precompute prefix sums for efficient queries.
• Examples:
  • Subarray sum equals k
  • Range sum query
• Time Complexity: O(n) precomputation, O(1) query.
• Space Complexity: O(n).

---

15. Bit Manipulation

• Use Case: Binary operations or optimizations (e.g., single number).
• Key Idea: Use bitwise operations (AND, OR, XOR, shifts).
• Examples:
  • Single number
  • Count set bits
  • Power of two
• Time Complexity: O(1) for fixed-size integers.
• Space Complexity: O(1).

---

How to Practice

1. Identify Pattern: Look for keywords (e.g., “subarray” → sliding window, “sorted” → binary search).
2. Solve by Category: Use LeetCode, HackerRank, Codeforces for tagged problems.
3. Build Intuition: Note why a pattern applies and how it optimizes.
4. Mock Interviews: Simulate timed coding for speed and accuracy.

If you need a curated problem list for a specific pattern or help with a DSA problem, let me know!