FAANG-Level DSA Patterns Guide
Welcome to the DSA Patterns Guide. Mastering Data Structures and Algorithms is less
about memorizing individual solutions and more about recognizing patterns. FAANG and
top-tier tech companies frequently test these core patterns. If you can identify the pattern, you
can generally solve any variation of the problem.
Below is a comprehensive analysis of the 15 Must-Know DSA Patterns, how to identify
them, and an expanded list of at least 10 essential questions for each pattern to help you master
them.
1. Sliding Window
Concept: Used to perform operations on a specific window size of a given array or linked list,
such as finding the longest subarray containing all 1s. Windows can be fixed-size or variable-
size.
How to identify:
• The problem input is a linear data structure (Linked List, Array, or String).
• You are asked to find the longest/shortest substring, subarray, or a desired value within
a continuous sequence.
Must-Do FAANG Questions:
1. Maximum Sum Subarray of Size K (Easy)
2. Smallest Subarray with a given sum (Easy)
3. Longest Substring Without Repeating Characters (Medium)
4. Longest Repeating Character Replacement (Medium)
5. Max Consecutive Ones III (Medium)
6. Permutation in String (Medium)
7. Find All Anagrams in a String (Medium)
8. Minimum Window Substring (Hard)
9. Subarrays with K Different Integers (Hard)
10. Sliding Window Maximum (Hard)
2. Two Pointers
Concept: Two pointers iterate through the data structure in tandem until one or both hit
a certain condition. Usually involves starting at the beginning and end of a sorted array and
moving towards each other, or starting at the same end and moving at different speeds.
How to identify:
1
• It features sorted arrays (or Linked Lists) and you need to find a set of elements that
fulfill certain constraints.
• The set of elements in the array is a pair, a triplet, or even a subarray.
Must-Do FAANG Questions:
1. Valid Palindrome (Easy)
2. Two Sum II - Input Array Is Sorted (Medium)
3. Squares of a Sorted Array (Easy)
4. 3Sum (Medium)
5. 3Sum Closest (Medium)
6. 4Sum (Medium)
7. Container With Most Water (Medium)
8. Sort Colors (Dutch National Flag pattern) (Medium)
9. Remove Duplicates from Sorted Array (Easy)
10. Trapping Rain Water (Hard)
3. Fast & Slow Pointers (Floyd’s Cycle Finding)
Concept: Also known as the Hare & Tortoise algorithm, this uses two pointers which move
through the array (or sequence/linked list) at different speeds.
How to identify:
• The problem deals with a loop in a linked list or array.
• When you need to find the position of a certain element or the overall length of the linked
list.
Must-Do FAANG Questions:
1. Linked List Cycle (Easy)
2. Middle of the Linked List (Easy)
3. Linked List Cycle II (Medium)
4. Find the Duplicate Number (Medium)
5. Happy Number (Easy)
6. Palindrome Linked List (Easy)
7. Reorder List (Medium)
8. Remove Nth Node From End of List (Medium)
9. Intersection of Two Linked Lists (Easy)
10. Circular Array Loop (Medium)
4. Merge Intervals
Concept: This pattern describes an efficient technique to deal with overlapping intervals. It
often requires sorting the intervals based on their start or end times.
How to identify:
• You are asked to produce a list with only mutually exclusive intervals.
• You hear the term ”overlapping intervals”.
2
Must-Do FAANG Questions:
1. Meeting Rooms (Easy)
2. Merge Intervals (Medium)
3. Insert Interval (Medium)
4. Non-overlapping Intervals (Medium)
5. Meeting Rooms II (Medium)
6. Intervals Intersection (Medium)
7. Task Scheduler (Medium)
8. Minimum Number of Arrows to Burst Balloons (Medium)
9. Employee Free Time (Hard)
10. Data Stream as Disjoint Intervals (Hard)
5. Cyclic Sort
Concept: An O(N ) sorting algorithm for sorting arrays containing numbers in a given range
(e.g., 1 to N ). It iteratively places numbers in their correct index (i.e., number 1 goes to index
0).
How to identify:
• You’re given an array containing numbers in a given range.
• You’re asked to find the missing, duplicate, or smallest missing positive number in O(N )
time and O(1) space.
Must-Do FAANG Questions:
1. Missing Number (Easy)
2. Find All Numbers Disappeared in an Array (Easy)
3. Find the Duplicate Number (Medium)
4. Find All Duplicates in an Array (Medium)
5. Set Mismatch (Easy)
6. Find the Corrupt Pair (Easy)
7. First Missing Positive (Hard)
8. Find the Smallest Missing Positive Number (Hard)
9. Find the First K Missing Positive Numbers (Hard)
10. Couples Holding Hands (Hard)
6. In-place Reversal of a LinkedList
Concept: Reversing links between nodes of a linked list in a single pass without using extra
memory.
How to identify:
• You are asked to reverse a linked list or parts of a linked list.
Must-Do FAANG Questions:
1. Reverse Linked List (Easy)
3
2. Reverse Linked List II (Medium)
3. Swap Nodes in Pairs (Medium)
4. Rotate List (Medium)
5. Swapping Nodes in a Linked List (Medium)
6. Palindrome Linked List (Easy)
7. Reorder List (Medium)
8. Reverse Alternating K-element Sub-list (Medium)
9. Reverse Nodes in Even Length Groups (Medium)
10. Reverse Nodes in k-Group (Hard)
7. Tree Breadth-First Search (BFS)
Concept: Uses a Queue to traverse a tree level-by-level.
How to identify:
• You are asked to traverse a tree level-by-level (or depth-by-depth).
• Finding the shortest path in an unweighted graph/tree.
Must-Do FAANG Questions:
1. Average of Levels in Binary Tree (Easy)
2. Minimum Depth of Binary Tree (Easy)
3. Maximum Depth of N-ary Tree (Easy)
4. Binary Tree Level Order Traversal (Medium)
5. Binary Tree Level Order Traversal II (Medium)
6. Binary Tree Zigzag Level Order Traversal (Medium)
7. Binary Tree Right Side View (Medium)
8. Populating Next Right Pointers in Each Node (Medium)
9. Connect Nodes at Same Level (Medium)
10. Word Ladder (Hard)
8. Tree Depth-First Search (DFS)
Concept: Uses recursion (or a stack) to traverse a tree from root to leaves.
How to identify:
• You are asked to traverse a tree, finding paths from root to leaf, or combining results from
subtrees.
Must-Do FAANG Questions:
1. Maximum Depth of Binary Tree (Easy)
2. Path Sum (Easy)
3. Diameter of Binary Tree (Easy)
4. Invert Binary Tree (Easy)
5. Path Sum II (Medium)
6. Path Sum III (Medium)
7. Lowest Common Ancestor of a Binary Tree (Medium)
8. Sum Root to Leaf Numbers (Medium)
9. Validate Binary Search Tree (Medium)
10. Binary Tree Maximum Path Sum (Hard)
4
9. Two Heaps
Concept: Uses two heaps (a Min Heap and a Max Heap) simultaneously. The Max Heap
stores the smaller half of the numbers, and the Min Heap stores the larger half. This allows
O(1) access to the median.
How to identify:
• Useful in situations where you need to continuously divide a set of elements into two parts
and find the max of one part and the min of the other.
Must-Do FAANG Questions:
1. Find Right Interval (Medium)
2. Next Interval (Medium)
3. Schedule Tasks on Minimum Machines (Medium)
4. Process Tasks Using Servers (Medium)
5. Find Median from Data Stream (Hard)
6. Sliding Window Median (Hard)
7. IPO / Maximize Capital (Hard)
8. Meeting Rooms III (Hard)
9. Minimum Number of Refueling Stops (Hard)
10. Trapping Rain Water II (Hard) - *Advanced heap application*
10. Subsets (Backtracking)
Concept: Explores all possible combinations/permutations recursively.
How to identify:
• The problem asks to find all permutations, combinations, or subsets of a given set.
Must-Do FAANG Questions:
1. Subsets (Medium)
2. Subsets II (Medium)
3. Permutations (Medium)
4. Permutations II (Medium)
5. Combination Sum (Medium)
6. Combination Sum II (Medium)
7. Combination Sum III (Medium)
8. Letter Combinations of a Phone Number (Medium)
9. Generate Parentheses (Medium)
10. Word Search (Medium)
11. Modified Binary Search
Concept: Whenever you are given a sorted array, linked list, or matrix, and are asked to find
a certain element, the best algorithm you can use is Binary Search.
How to identify:
5
• Search in a sorted or rotated sorted data structure.
Must-Do FAANG Questions:
1. Binary Search (Easy)
2. Find Peak Element (Medium)
3. Peak Index in a Mountain Array (Medium)
4. Find First and Last Position of Element in Sorted Array (Medium)
5. Search in Rotated Sorted Array (Medium)
6. Search in Rotated Sorted Array II (Medium)
7. Find Minimum in Rotated Sorted Array (Medium)
8. Search a 2D Matrix (Medium)
9. Search a 2D Matrix II (Medium)
10. Split Array Largest Sum (Hard)
12. Top ’K’ Elements (Heaps)
Concept: Use a Min-Heap (to keep the top K largest) or Max-Heap (to keep the top K small-
est).
How to identify:
• Any problem that asks us to find the top/smallest/frequent ’K’ elements among a given
set.
Must-Do FAANG Questions:
1. Kth Largest Element in a Stream (Easy)
2. Kth Largest Element in an Array (Medium)
3. Top K Frequent Elements (Medium)
4. K Closest Points to Origin (Medium)
5. Sort Characters By Frequency (Medium)
6. Top K Frequent Words (Medium)
7. Find K Pairs with Smallest Sums (Medium)
8. Kth Smallest Element in a Sorted Matrix (Medium)
9. Reorganize String (Medium)
10. Task Scheduler (Medium)
13. Monotonic Stack
Concept: A stack whose elements are strictly increasing or strictly decreasing. Excellent for
”next greater element” problems.
How to identify:
• You need to find the next strictly greater/smaller element for every element in an array.
O(N ) time complexity.
Must-Do FAANG Questions:
1. Next Greater Element I (Easy)
6
2. Next Greater Element II (Medium)
3. Daily Temperatures (Medium)
4. Online Stock Span (Medium)
5. Remove K Digits (Medium)
6. 132 Pattern (Medium)
7. Sum of Subarray Minimums (Medium)
8. Largest Rectangle in Histogram (Hard)
9. Maximal Rectangle (Hard)
10. Trapping Rain Water (Hard)
14. Graph / Topological Sort
Concept: Used to find a linear ordering of elements that have dependencies on each other.
Usually implemented using BFS (Kahn’s Algorithm) with in-degrees.
How to identify:
• The problem deals with graphs that have no directed cycles (DAGs).
• You are asked to schedule jobs, courses, or tasks where certain tasks depend on others.
Must-Do FAANG Questions:
1. Find Eventual Safe States (Medium)
2. Minimum Height Trees (Medium)
3. Sequence Reconstruction (Medium)
4. Parallel Courses (Medium)
5. Course Schedule (Medium)
6. Course Schedule II (Medium)
7. Course Schedule IV (Medium)
8. Parallel Courses III (Hard)
9. Alien Dictionary (Hard)
10. Reconstruct Itinerary (Hard)
15. Dynamic Programming (1D & 2D)
Concept: Breaking down an optimization problem into simpler sub-problems, solving each
sub-problem just once, and storing their solutions (memoization or tabulation).
How to identify:
• The problem asks for the maximum/minimum/longest/shortest of something.
• ”Count the number of ways” to do something.
• Overlapping subproblems.
Must-Do FAANG Questions:
1. Climbing Stairs (Easy)
2. House Robber (Medium)
3. House Robber II (Medium)
4. Coin Change (Medium)
5. Maximum Product Subarray (Medium)
7
6. Partition Equal Subset Sum (Medium)
7. Word Break (Medium)
8. Longest Increasing Subsequence (Medium)
9. Longest Common Subsequence (Medium)
10. Edit Distance (Hard)