Overview of DSA Problem Solving Techniques

1. Brute Force Technique

• ✅ Try all possible combinations or solutions.
• 📌 Use when constraints are small (e.g., ≤10⁴).
• ⚠️ High time complexity; not optimal for large inputs.

2. Greedy Algorithm Technique

• ✅ Make the locally optimal choice at each step.
• 📌 Use when the problem has the greedy-choice property and optimal substructure.
• ⚠️ Doesn’t always guarantee global optimality unless proven.

3. Divide and Conquer

• ✅ Split the problem into subproblems, solve recursively, then combine.
• 📌 Useful in sorting, searching, matrix operations.
• ⚠️ Recursion overhead; must handle base cases carefully.

4. Dynamic Programming (DP)

• ✅ Break problems into overlapping subproblems with optimal substructure.
• 📌 Use when subproblems repeat (e.g., Fibonacci, Knapsack).
• ⚠️ Needs memoization/tabulation and careful state definition.

5. Backtracking

• ✅ Try all options and undo choices that don't work (recursive).
• 📌 Use in permutations, combinations, constraint satisfaction.
• ⚠️ Can be exponential in complexity; pruning is critical.

6. Recursion

• ✅ Solve problems by solving smaller instances of the same problem.
• 📌 Useful in tree traversal, divide & conquer, DP.
• ⚠️ Stack overflow risk for deep recursion; base case required.

7. Sliding Window

• ✅ Maintain a window to track optimal subarray or substring.
• 📌 Use when working with contiguous sequences (e.g., longest subarray with sum ≤ K).
• ⚠️ Only works when window movement rules are clear.

8. Two Pointers

• ✅ Use two indices to traverse from both ends or in sync.
• 📌 Works well in sorted arrays, strings, or when scanning pairs.
• ⚠️ Data must allow ordered traversal or merging logic.

9. Binary Search

• ✅ Divide search space in half to locate the answer efficiently.
• 📌 Use when the array/search space is sorted or monotonic.
• ⚠️ Conditions must ensure a strictly increasing/decreasing space.

10. Tree / Graph Traversal

• ✅ Visit nodes using DFS (depth-first) or BFS (breadth-first).
• 📌 Use for pathfinding, connectivity, tree-based problems.
• ⚠️ Must handle cycles (in graphs) and visited states.

11. Bit Manipulation

• ✅ Use bitwise operators to solve problems efficiently.
• 📌 Useful in toggling, masking, subset generation, XOR tricks.
• ⚠️ Requires understanding of binary operations.

12. Hashing Technique

• ✅ Use hash maps/sets for quick lookups and counting.
• 📌 Best for frequency maps, duplicates, prefix sums, etc.
• ⚠️ Hash collisions and memory usage can be concerns.

13. Heaps Technique

• ✅ Use a min-heap or max-heap for efficient extreme value tracking.
• 📌 Use in priority queues, top-k elements, scheduling problems.
• ⚠️ Requires heap property maintenance via insertion/deletion.