Common coding patterns and techniques

 

1. Hashmaps (Dictionaries in Python)

When to Use:

• Fast lookups & insertions → O(1) average time complexity.
• Counting frequencies → e.g., character counts, word frequencies.
• Finding duplicates in O(n) time.
• Grouping items by common properties (like anagrams).
• Mapping relationships (e.g., parent-child, graph adjacency lists).

Examples:

• Two Sum (Find two numbers that sum to a target)
• Group Anagrams
• Longest Substring Without Repeating Characters

---

2. Sliding Window

When to Use:

• Subarrays or substrings with constraints.
• Finding max/min/k-distinct elements in a subarray.
• Fixed or dynamic window size problems.

Examples:

• Longest Substring Without Repeating Characters
• Maximum Sum Subarray of Size K
• Smallest Subarray with a Given Sum

Key Trick: Use a set or hashmap to track seen characters.

---

3. Two Pointers

When to Use:

• Sorted arrays or linked lists.
• Finding pairs that meet conditions.
• Reversing sequences in-place.
• Merging two sorted lists/arrays.

Examples:

• Two Sum (Sorted Array)
• Remove Duplicates from Sorted Array
• Container with Most Water

---

4. Prefix Sum

When to Use:

• Range sum queries in O(1) time.
• Finding subarrays with a given sum.
• Cumulative calculations.

Examples:

• Subarray Sum Equals K
• Range Sum Query
• Equilibrium Index

---

5. Binary Search

When to Use:

• Searching in sorted data.
• Finding min/max values (like square root, rotated array search).
• Optimization problems (e.g., minimum days to ship packages).

Examples:

• Search in Rotated Sorted Array
• Find First and Last Position of Element
• Kth Smallest Element in a Sorted Matrix

---

6. Depth-First Search (DFS) & Breadth-First Search (BFS)

When to Use:

• Graph traversal (trees, graphs, islands).
• Finding paths in mazes or puzzles.
• Backtracking problems.

Examples:

• Number of Islands (DFS/BFS)
• Word Ladder (BFS)
• Find All Paths in a Graph

---

7. Dynamic Programming (DP)

When to Use:

• Problems that have overlapping subproblems.
• Problems that can be broken down into smaller problems.
• Finding optimal solutions (min/max, longest/shortest, etc.).

Examples:

• Fibonacci Series
• Longest Increasing Subsequence
• 0/1 Knapsack Problem

🔹 Key Trick: Use memoization to avoid redundant calculations.

---

8. Sorting Algorithms

When to Use:

• Sorting numbers/strings before searching.
• Sorting before using two-pointer approach.
• Sorting to remove duplicates, find missing elements.

Examples:

• Merge Sort (O(n log n))
• Quick Sort (O(n log n))
• Counting Sort (O(n) for small ranges)

---

How to Choose the Right Algorithm?

Problem Type	Best Approach
Find unique elements?	Hashmap / Set
Find longest/shortest substring?	Sliding Window
Search in sorted data?	Binary Search
Find pairs or triplets?	Two Pointers / Hashmap
Graph traversal?	DFS / BFS
Optimize subproblems?	Dynamic Programming
Subarrays with sum constraint?	Prefix Sum / Hashmap