Most DSA interviews test the same set of patterns again and again. Whether it is TCS, Infosys, Amazon, Google, or any startup, the problems change but the underlying patterns stay the same. If you learn to recognize these patterns, you can solve most interview problems without memorizing hundreds of questions.
This cheat sheet covers every major DSA pattern, when to use it, what type of problems fall under it, and the key idea behind each one. Bookmark this page and come back to it before every interview.
Why Patterns Matter More Than Problems
A lot of students make the mistake of solving 500+ LeetCode problems randomly. They solve a problem, feel good, and move to the next one. But when a slightly different version shows up in an interview, they get stuck.
The reason is simple. They memorized solutions instead of understanding patterns. Once you know a pattern, you can apply it to 20 or 30 different problems. That is a much better use of your time.
Think of it this way. If someone asks you to find two numbers that add up to a target in a sorted array, and you know the two pointer pattern, you do not need to have seen that exact problem before. You just recognize the pattern and apply it. Same goes for finding the longest substring without repeating characters. If you know the sliding window, the problem is half solved before you even start coding.
The patterns listed below cover roughly 90% of what you will face in interviews at Indian product companies, service companies, and startups.
1. Two Pointers
The two pointer pattern uses two variables (usually called left and right) that move through an array or string from different positions.
When to use it:
- The input is sorted
- You need to find pairs or triplets that satisfy a condition
- Useful when comparing elements from both ends of an array
Common problems:
Two Sum (sorted array), Three Sum, Remove Duplicates from Sorted Array, Trapping Rain Water
Key idea:
Instead of checking every possible pair using two nested loops (O(n²)), you use two pointers that move towards each other based on some condition. This reduces the time complexity to O(n).
How to spot it:
If the problem says “sorted array” and asks you to find a pair or group of elements, think two pointers first.
2. Sliding Window
Sliding window is one of the most frequently asked patterns in interviews. It works on problems where you need to find something (maximum, minimum, count) within a contiguous subarray or substring.
When to use it:
- The problem involves a subarray or substring
- You need to optimize from a brute force approach
Common problems:
Maximum Sum Subarray of Size K, Longest Substring Without Repeating Characters, Minimum Window Substring, Fruits Into Baskets, Longest Repeating Character Replacement
Key idea:
Maintain a window (two pointers) and expand or shrink it based on conditions. As the window slides forward, you add new elements and remove old ones, avoiding recomputation.
Fixed window vs variable window:
- Fixed window: Size is given (e.g., size K)
- Variable window: Find smallest/largest window satisfying a condition
3. Binary Search
Binary search is not just about searching in a sorted array. Its real power is search space reduction.
When to use it:
- Input is sorted
- You are searching in a monotonic space (increasing/decreasing)
Common problems:
Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array, Koko Eating Bananas, Median of Two Sorted Arrays, Aggressive Cows, Book Allocation Problem
Key idea:
Check the middle element and eliminate half of the search space each time → O(log n)
Important for Indian interviews:
Problems like Book Allocation, Aggressive Cows, Painter’s Partition are extremely common. These are “binary search on answer” problems where you search on the answer space instead of the array.
4. Hashing
Hashing is the go-to technique when you need fast lookups, counting, or tracking elements.
When to use it:
- Need O(1) lookup
- Counting frequency of elements
- Checking if something exists
Common problems:
Two Sum (unsorted), Longest Consecutive Sequence, Subarray Sum Equals K, Valid Anagram
Key idea:
Use a hash map (dictionary) to store elements and their properties (index, frequency, etc.), converting slow lookups into O(1) operations.
Watch out for:
Worst-case hash collisions, but in interviews, average O(1) is what matters.
5. Stack and Queue
Stack problems usually involve matching or tracking elements in order. The monotonic stack is a very important subpattern.
When to use it:
- Matching brackets
- Finding next greater/smaller elements
- Evaluating expressions
Common problems:
Valid Parentheses, Next Greater Element, Daily Temperatures, Largest Rectangle in Histogram, Min Stack, Evaluate Reverse Polish Notation, Implement Queue Using Stacks
Key idea:
- Stack → Last In First Out (LIFO)
- Monotonic stack → maintain increasing or decreasing order
Monotonic stack trick:
For every element, pop elements that are smaller (or larger). The remaining top gives the answer.
6. Linked List Patterns
Linked list problems test pointer manipulation skills.
When to use it:
- Problem involves a linked list
- Need in-place rearrangement
Common problems:
Reverse Linked List, Detect Cycle, Find Middle, Merge Two Lists, Remove Nth Node, Palindrome Linked List, Intersection
Key tricks:
- Slow and fast pointer (middle, cycle detection)
- Reverse technique
- Dummy node (simplifies edge cases)
7. Trees (BFS and DFS)
Tree problems are extremely common and mostly follow BFS or DFS.
When to use BFS:
- Level order traversal
- Shortest path
- Process nodes level by level
When to use DFS:
- Path-based problems
- Checking tree properties
- Computing depth
Common problems:
Maximum Depth, Level Order Traversal, Validate BST, Lowest Common Ancestor, Diameter, Right Side View, Zigzag Traversal
Key idea (DFS):
Ask:
- What do I need from the left subtree?
- What do I need from the right subtree?
- How do I combine them?
Key idea (BFS):
Use a queue and process nodes level by level.
8. Graph Traversal
Graphs extend trees with cycles and multiple paths.
When to use it:
- Problems involving connections, grids, networks
Common problems:
Number of Islands, Course Schedule, Rotten Oranges, Word Ladder, Number of Provinces, Surrounded Regions, Topological Sort
Key ideas:
- Track visited nodes
- BFS → shortest path
- DFS → connected components
Topological sort:
Used for task ordering with dependencies (Kahn’s algorithm or DFS).
9. Recursion and Backtracking
Backtracking is recursion with undoing choices.
When to use it:
- Find all combinations, permutations, subsets
Common problems:
Subsets, Permutations, Combination Sum, N Queens, Sudoku Solver, Word Search, Palindrome Partitioning
Key idea:
Think of it as a decision tree.
Template:
- Define base case
- Loop through choices
- Make a choice
- Recurse
- Undo choice (backtrack)
Pruning:
Skip invalid paths early to improve performance.
10. Dynamic Programming
Dynamic Programming (DP) is optimized recursion.
When to use it:
- Overlapping subproblems
- Optimal substructure
Common problems:
Climbing Stairs, House Robber, LCS, Knapsack, Edit Distance, Coin Change, Matrix Chain Multiplication
Approach:
- Start with recursion
- Identify state variables
- Add memoization
- Convert to tabulation
Common categories:
- 1D DP (Linear)
- 2D DP (Grid)
- String DP
- Knapsack variants
- Interval DP
- Tree DP
Important for Indian interviews:
- 0/1 Knapsack and variants
- Longest Common Subsequence (LCS)
11. Greedy
Greedy algorithms make the best local choice at each step.
When to use it:
- When local optimal → global optimal
Common problems:
Fractional Knapsack, Activity Selection, Job Scheduling, Minimum Platforms, Jump Game, Gas Station
Key idea:
Sort input and make locally optimal decisions.
12. Heap / Priority Queue
A heap gives quick access to the minimum or maximum element.
When to use it:
- Kth largest/smallest problems
- Top K elements
- Merging sorted lists
Common problems:
Kth Largest Element, Top K Frequent Elements, Merge K Sorted Lists, Median from Data Stream, Task Scheduler
Key idea:
- Use min heap / max heap
- Maintain a heap of size K
13. Bit Manipulation
Less frequent but important for optimization-heavy problems.
When to use it:
- Finding unique elements
- Checking power of 2
- Bit counting
Common problems:
Single Number, Power of Two, Counting Bits, Missing Number
Key operations:
- AND, OR, XOR, shifts
- XOR properties:
- a XOR a = 0
- a XOR 0 = a
How to Use This Cheat Sheet
Do not try to master all patterns at once.
- Week 1–2: Two Pointers, Sliding Window, Hashing
- Week 3–4: Binary Search, Stack, Linked List
- Week 5–6: Trees, Graphs
- Week 7–8: Recursion, Backtracking, DP
- Ongoing: Greedy, Heap, Bit Manipulation
For each pattern, solve 5 to 8 problems. Focus on understanding, not memorizing.
One Last Tip
After solving a problem, spend 2 minutes asking:
- What pattern did I use?
- How would I recognize this pattern in a new problem?
This habit builds pattern recognition faster than solving more problems blindly.
Start Your DSA Journey
If you are just getting started with DSA and Python, check out our Zero to Hero Python DSA course. It covers everything from basics to advanced topics in a structured way.
Already comfortable with the fundamentals and want to practice problems pattern by pattern? Our Master DSA with LeetCode course walks you through 150+ handpicked problems organized exactly by the patterns covered in this cheat sheet.
