// Golden Tips
1. If the coding problem requires performing an operation that needs faster search in O(1), try to use Set
or a Map.
2. If the coding problem requires finding/manipulating/dealing with the top, bottom, maximum,
minimum, closest, and farthest "K" elements among given "N" elements, try to use a Heap.
3. If the coding problem has input as a sorted Array, List, or Matrix, try to use Two Pointer strategy or try
to use Binary Search.
4. If the coding problem requires trying all Permutations and Combinations, we can use either
Backtracking or Breadth First Search.
5. If the coding problem has input in the form of a Tree or Graph, then most of the time can be solved by
applying Tree Traversals or Graph Traversals algorithms called Breadth First Search (BFS) and Depth
First Search (DFS).
6. If the coding problem is around a Singly Linked List, and If you are stuck in traversals logic, then try to
use either Two Pointers or Slow/Fast Pointers.
7. If the coding problem has a recursive solution but its hard to visualize/code, try using a Stack data
structure with a loop.
8. If the coding problem revolves around iterating an array, and takes O(N2) time complexity, O(1)
space complexity then try to use a HashMap/HashSet. It makes the algorithm faster with O(N) time
complexity but takes more space with O(N) space complexity.
9. If the coding problem revolves around iterating an array and takes O(N2) time complexity, and O(1)
space complexity then try to sort the array. It makes the algorithm faster with O(N log N) time
complexity and O(1) space complexity.
10. If the coding problem requires optimization around the recursive the solution, there could be a
possibility that dynamic programming can be used.
11. If the coding problem has a group of strings or some manipulation/find/storing needs to be done
around the substring, there is a high possibility that either Tries or HashMap can be used.
1. If Input Array is Sorted
• Binary Search:
• Use when you need to search for an element or find boundaries (e.g., first or last occurrence)
efficiently.
• Time complexity: O(log n).
• Two Pointers:
• Use when solving problems involving pairs or subarrays, such as finding two numbers that sum to
a target or removing duplicates.
• Time complexity: O(n).
2. If Asked for All Permutations/Subsets
• Backtracking:
• Used when the problem involves generating all possible solutions (e.g., permutations,
combinations, subsets).
• Backtracking explores all possibilities by recursively building solutions and backtracking when
constraints are violated.
• Examples: Generate all permutations of a string, Generate subsets of an array.
3. If Given a Graph
• Breadth-First Search (BFS):
• Use when finding the shortest path in an unweighted graph.
• Works well for level-by-level traversal.
• Depth-First Search (DFS):
• Use when exploring all paths or finding connected components.
• Recursive or iterative (using a stack).
4. If Recursion Is Banned
• Use a Stack: Convert recursive solutions into iterative ones by explicitly using a stack.
• Examples: In-order, pre-order, and post-order traversal of binary trees, Iterative DFS for graphs.
5. For Max/Min, Subarray/Subset/Options
• Dynamic Programming (DP):
• Solve problems involving optimization or overlapping subproblems.
• Examples: Longest Increasing Subsequence, Maximum Subarray Sum (Kadane’s Algorithm),
Subset Sum Problem.
6. Linked List
• Two Pointers:
• Use slow and fast pointers for problems like detecting cycles, finding the middle of a list, or
reversing a portion of the list.
• Examples: Detecting a loop (Floyd’s Cycle Detection Algorithm), Finding the intersection of two
linked lists.
7. If Must Solve In-Place
• Swap Corresponding Values:
• Use for problems like reversing an array or rearranging elements.
• Time complexity: O(n).
• Store Multiple Values in the Same Pointer:
• Modify the array or use the same memory space creatively.
• Examples: Rearrange an array by cyclic replacement, Flatten a tree into a linked list.
8. If Asked for Common Strings
• Map/Set:
• Use for O(1) time lookups to check for common elements.
• Space complexity: O(n).
• Example: Find common elements between two arrays.
• Trie: Use for prefix-based problems (e.g., autocomplete or longest common prefix).
• Sort Input: Sorting allows for binary search or two-pointer techniques to solve problems.
• Space complexity: O(1).
• Time complexity: O(n log n).
9. If Asked for Top/Least K Elements
• Heap:
• Use for efficiently finding the top/least K elements.
• Max-heap for the smallest K, Min-heap for the largest K.
• Time complexity: O(n log k).
• Quick Select:
• Use for finding the Kth largest/smallest element.
• Time complexity: O(n) on average, O(n²) worst case.
10. Sliding Window
• Use: Problems involving subarrays or substrings with specific properties (e.g.,
maximum/minimum, unique elements).
• Examples: Longest substring without repeating characters, Maximum sum of a subarray of
size k, Count anagrams in a string.
• Approach:
• Use a dynamic “window” (two pointers) to explore possible solutions efficiently.
• Adjust the window size by incrementing pointers as needed.
• Complexity: Time complexity: O(n) for most problems.
11. Union-Find (Disjoint Set Union — DSU)
• When to Use: Problems involving connected components or grouping.
• Examples: Number of islands, Kruskal’s algorithm for Minimum Spanning Tree (MST), Detecting
cycles in an undirected graph.
• Approach: Use a parent array to represent components and union and find operations to manage
groups.
• Complexity: Time complexity: O(α(n)) (almost constant).
12. Greedy Algorithms
• Use: Optimization problems where locally optimal choices lead to a globally optimal solution.
• Examples: Interval scheduling problems (e.g., meeting room scheduling), Huffman encoding,
Fractional knapsack problem.
• Approach: Make the best choice at each step without reconsidering previous choices.
• Complexity: Often O(n log n) due to sorting.
13. Monotonic Stack/Queue
• Use: Problems involving the “next greater/smaller element.”
• Examples: Daily temperatures, Largest rectangle in histogram, Trapping rainwater.
• Approach: Use a stack or queue to maintain a monotonic order of elements.
• Complexity: Time complexity: O(n) for most problems.
14. Prefix Sum
• Use: Problems involving range sums or cumulative sums.
• Examples: Subarray sum equals K, Count subarrays with a given sum, Product of array except self
(without division).
• Approach: Use a prefix sum array or hashmap to store cumulative sums and query ranges
efficiently.
• Complexity: Time complexity: O(n) for computation, O(1) for queries.
15. Bit Manipulation
• Use: Problems involving binary representation or subsets.
• Examples: Single number (XOR for unique elements), Counting bits, Subset generation.
• Approach: Use bitwise operators (AND, OR, XOR, SHIFT) for efficient computation.
• Complexity: Time complexity: Varies, but often O(n) or O(log n).
16. Segment Tree/Fenwick Tree
• Use: Range query problems with updates (e.g., range sum, range minimum, range maximum).
• Examples: Dynamic sum or minimum queries on an array, Number of smaller elements to the
right.
• Approach: Use a tree structure to preprocess data and perform queries/updates efficiently.
• Complexity: Time complexity: O(log n) for queries and updates.
17. Kadane’s Algorithm
• Use: Problems asking for the maximum sum of a subarray.
• Examples: Maximum subarray sum, Circular subarray sum.
• Approach: Use dynamic programming to maintain the maximum subarray sum ending at each
index.
• Complexity: Time complexity: O(n).