Top 15 DSA Patterns for Coding Interviews India 2026: The Complete Cheatsheet

When to use: Finding max/min of a subarray of fixed or variable size. Reduces O(n²) brute force to O(n).

Types: Fixed window (size k given) vs. Variable window (expand/contract based on condition).

• Max Sum Subarray of Size K
• Longest Substring Without Repeating Chars
• Minimum Window Substring
• Fruit Into Baskets

When to use: Eliminates nested loops on sorted arrays. Reduces O(n²) to O(n).

• Two Sum II (sorted input)
• 3Sum
• Container With Most Water
• Valid Palindrome II
• Remove Duplicates from Sorted Array

When to use: Cycle detection in O(1) space. Finding intersection of linked lists. Identifying kth from end.

• Linked List Cycle
• Linked List Cycle II (start of cycle)
• Middle of Linked List
• Happy Number

When to use: Sorting by start time first, then iterating with merge logic.

• Merge Intervals
• Insert Interval
• Non-overlapping Intervals
• Meeting Rooms II

When to use: Place each number at its correct index by swapping. Then scan for mismatches.

• Find Missing Number
• Find All Duplicates in Array
• Set Mismatch
• First Missing Positive

When to use: Any problem requiring processing by levels or finding shortest path. Use a queue (deque in Python).

• Binary Tree Level Order Traversal
• Rotting Oranges
• Word Ladder
• 0/1 Matrix
• Shortest Path in Binary Matrix

When to use: Explore all possibilities; undo ("backtrack") when a path doesn't work. The core pattern: choose, explore, unchoose.

• Subsets
• Permutations
• Combination Sum
• N-Queens
• Word Search
• Palindrome Partitioning

When to use: Classic: sorted array, O(log n) search. On Answer: the answer lies in a range; binary search for valid answer instead of elements.

• Search in Rotated Sorted Array
• Find Minimum in Rotated Array
• Koko Eating Bananas
• Capacity to Ship Packages
• Median of Two Sorted Arrays

When to use: Min-heap of size K for "Top K largest". Max-heap for "Top K smallest". Don't sort the whole array when you only need K elements.

• Kth Largest Element in Array
• Top K Frequent Elements
• K Closest Points to Origin
• Find K Pairs with Smallest Sums

Key 1D patterns: Fibonacci-style (dp[i] = dp[i-1] + dp[i-2]), Kadane's algorithm (max subarray), coin change, climbing stairs.

• Climbing Stairs
• House Robber
• Coin Change
• Maximum Subarray (Kadane's)
• Longest Increasing Subsequence
• Word Break

Key 2D patterns: Grid DP (dp[i][j] depends on dp[i-1][j] and dp[i][j-1]). String DP (dp[i][j] represents answer for first i chars of s1 and j chars of s2).

• Unique Paths
• Minimum Path Sum
• Longest Common Subsequence
• Edit Distance
• 0/1 Knapsack

• Number of Islands
• Number of Connected Components
• Course Schedule (Cycle Detection)
• Network Delay Time (Dijkstra)
• Redundant Connection (Union-Find)

When to use: Maintain a stack of elements in monotonically increasing or decreasing order. Pop when the current element violates the order.

• Daily Temperatures
• Next Greater Element I & II
• Largest Rectangle in Histogram
• Trapping Rain Water

When to use: Efficient prefix operations on strings. Each node represents a character; the path from root to node spells a prefix.

• Implement Trie
• Word Search II
• Design Add and Search Words
• Maximum XOR of Two Numbers (Bit Trie)

Key operations: XOR self-cancels (a^a=0). AND with n-1 removes lowest set bit. Shift operators for multiplication/division by 2. Bit masking for subsets.

• Single Number
• Number of 1 Bits
• Reverse Bits
• Power of Two
• Sum of Two Integers (no + operator)