DSA Problem Solving Techniques | Brute Force, Greedy, DP, and More

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.