DSA_Problem_Solving_Checklist.md

✅ Ultimate DSA Problem-Solving Checklist

When solving any DSA problem, it helps to systematically analyze algorithms, data structures, and optimization opportunities. Use this checklist to think clearly and code efficiently.

---

1. Mini Algorithm Analysis Checklist

Input Size (n)

• How large is the input?
• How does the algorithm scale as n grows?

Operations per Element

• Comparisons? Swaps? Arithmetic steps?
• Just estimate trends, not exact counts.

Best, Average, Worst Case

• Does the order of input affect performance?
• Example: an already sorted array may help or hurt.

Data Structures Used

• Array, list, hash table, tree, heap, etc.
• Are they suitable for the operations performed?

Time Complexity

• Constant → O(1)
• Logarithmic → O(log n)
• Linear → O(n)
• Linearithmic → O(n log n)
• Quadratic → O(n²), etc.

Space Complexity

• Extra arrays, temporary buffers, recursion stack?
• Is it in-place (O(1) extra space) or uses O(n)?

Loop Structure

• Single loop → O(n)
• Nested loops → O(n²)
• Divide & conquer → often O(n log n)

Early Stopping Opportunities

• Can you break early if the answer is found?

Redundant Computation

• Are calculations repeated unnecessarily?
• Can caching/memoization help?

Better Alternatives

• Use hash tables for O(1) lookups
• Binary search for sorted data
• Heap for priority operations
• Dynamic programming for overlapping subproblems

---

2. Operations & Memory Awareness

Besides swaps and comparisons, check:

Traversals

• How many elements do you walk through?

Recursion Depth

• How many recursive calls?
• How deep is the call stack?

Memory Usage

• Extra arrays, temp variables, recursion stack

Insertions / Deletions

• Costly?
• Shifting elements in arrays? Pointer updates in linked lists?

Access Operations

• O(1) access (arrays) vs O(n) access (linked lists)

Data Structure Overhead

• Pointers, dynamic resizing, tree balancing, hash collisions

---

3. What Impacts Time Complexity

• Input Size (n) – bigger input → more operations
• Input Order – sorted vs unsorted, best/avg/worst case
• Type of Operations – comparison (cheap), swap (more costly), recursion (stack overhead)
• Data Structure Choice – list search O(n) vs hash table O(1) avg
• Algorithm Strategy – brute-force O(n²), divide & conquer O(n log n)
• Memory Access Patterns – arrays faster than linked lists due to locality

---

4. What Impacts Space Complexity

• Extra data structures → arrays, stacks, trees
• Recursion → each call uses stack memory
• Temporary variables → buffers, helper arrays
• In-place vs out-of-place → O(1) vs O(n)

---

5. Optimizing Solutions

Reduce Work

• Skip unnecessary operations
• Early stopping / pruning

Choose the Right Data Structure

• Fast search → hash table
• Fast sorted traversal → BST
• Fast insert/delete → linked list
• Fast random access → array

Algorithmic Paradigms

• Divide & conquer, dynamic programming, greedy, memoization

Avoid Redundant Computation

• Precompute, use prefix sums, caching

Improve Memory Access

• Use arrays over linked lists where possible
• In-place operations reduce extra memory

---

6. Quick Reference

• Check: traversals, recursion depth, memory usage, insert/delete cost, access pattern, data structure overhead
• Time Complexity depends on: input size/order, operation type, data structure, algorithm strategy, memory access
• Space Complexity depends on: extra structures, recursion, temp variables, in-place vs copies
• Optimize by: choosing better algorithms, better data structures, reducing work, caching, avoiding redundant operations

---

✨ Extra Tips for Writing Efficient DSA Code

• Favor clarity first, then optimize
• Measure time vs space trade-offs
• Use built-in data structures (Python: dict, set, deque, heapq) wisely
• Think in terms of patterns: sliding window, two pointers, prefix sums, etc.
• Practice mental dry runs for small inputs to catch logic errors