DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master the 7 most important coding patterns: sliding window, two pointers, fast & slow pointers, merge intervals, cyclic sort, top-K elements, and modified binary search.
Why Patterns Matter
Most interview problems are variations of 10-15 core patterns. Once you recognize the pattern, the solution structure becomes clear — you just need to adapt the template. This is why experienced interviewees solve problems faster: they are not inventing solutions from scratch, they are pattern-matching.
Pattern 1: Sliding Window
When to use: Problems involving contiguous subarrays/substrings with a constraint (maximum sum, minimum length, at most K distinct characters).
Key signal words: "subarray," "substring," "contiguous," "window," "consecutive"
Template (Variable-Size Window):
Example
def sliding_window(arr, condition):
left = 0
window_state = {} # track window contents
result = 0
for right in range(len(arr)):
# Expand window: add arr[right] to window state
update_window(window_state, arr[right])
# Shrink window while condition is violated
while not valid(window_state, condition):
remove_from_window(window_state, arr[left])
left += 1
# Update result with current valid window
result = max(result, right - left + 1)
return result
Example: Longest Substring Without Repeating Characters
Example
def length_of_longest_substring(s):
char_index = {}
left = 0
max_length = 0
for right in range(len(s)):
if s[right] in char_index and char_index[s[right]] >= left:
left = char_index[s[right]] + 1
char_index[s[right]] = right
max_length = max(max_length, right - left + 1)
return max_length
# "abcabcbb" → 3 ("abc")
# "bbbbb" → 1 ("b")
Pattern 2: Two Pointers
When to use: Sorted arrays where you need to find pairs/triplets satisfying a condition, or partitioning problems.
Key signal: Sorted input, pair finding, in-place array manipulation.
Template (Pair Sum):
Example
def two_pointer_pair(arr, target):
arr.sort()
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1 # Need larger sum
else:
right -= 1 # Need smaller sum
return [-1, -1]
Example: 3Sum (Find Triplets That Sum to Zero)
Example
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue # Skip duplicates
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
Pattern 3: Fast & Slow Pointers (Floyd's Cycle Detection)
When to use: Linked list cycle detection, finding the middle of a list, or finding the start of a cycle.
Key insight: The slow pointer moves 1 step, fast moves 2 steps. If there is a cycle, they WILL meet. If no cycle, fast reaches the end.
Template:
python example
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
def find_cycle_start(head):
slow = fast = head
# Phase 1: Detect cycle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # No cycle
# Phase 2: Find start
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slowExample: Find the Duplicate Number (Array as Linked List)
Example
def find_duplicate(nums):
# Treat array as linked list: index → value → next index
slow = fast = nums[0]
# Phase 1: Find meeting point
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: Find entry point
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
Pattern 4: Merge Intervals
When to use: Problems involving overlapping intervals, scheduling, or meeting rooms.
Key signal: Given a list of intervals, merge/count/find gaps.
Template:
Example
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
last = merged[-1]
if current[0] <= last[1]: # Overlapping
last[1] = max(last[1], current[1])
else:
merged.append(current)
return merged
Example: Meeting Rooms II (Minimum Rooms Needed)
Example
import heapq
def min_meeting_rooms(intervals):
intervals.sort(key=lambda x: x[0])
heap = [] # Tracks end times of ongoing meetings
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heappop(heap) # Room freed up
heapq.heappush(heap, end)
return len(heap) # Peak simultaneous meetings
Pattern 5: Cyclic Sort
When to use: Problems involving arrays with numbers in range [1, n] or [0, n] where you need to find missing/duplicate numbers.
Key insight: Place each number at its "correct" index (value i at index i-1). After one pass, any misplaced number reveals the answer.
Template:
Example
def cyclic_sort(nums):
i = 0
while i < len(nums):
correct_idx = nums[i] - 1 # Where this number should be
if nums[i] != nums[correct_idx]:
nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
else:
i += 1
return nums
Example: Find All Missing Numbers
Example
def find_missing_numbers(nums):
# Place each number at its correct index
i = 0
while i < len(nums):
correct = nums[i] - 1
if nums[i] != nums[correct]:
nums[i], nums[correct] = nums[correct], nums[i]
else:
i += 1
# Numbers not at their correct position → those indices are missing
return [i + 1 for i in range(len(nums)) if nums[i] != i + 1]
# [4,3,2,7,8,2,3,1] → [5, 6]
Pattern 6: Top-K Elements
When to use: Finding the K largest/smallest/most frequent elements.
Key insight: Use a heap of size K. For K largest, use a min-heap (root is the Kth largest). For K smallest, use a max-heap.
Template:
Example
import heapq
def top_k_elements(nums, k, key=lambda x: x):
heap = []
for num in nums:
heapq.heappush(heap, (key(num), num))
if len(heap) > k:
heapq.heappop(heap)
return [item for _, item in heap]
Example: K Closest Points to Origin
Example
def k_closest(points, k):
# Max-heap of size k (negate distance for max behavior)
heap = []
for x, y in points:
dist = -(x*x + y*y)
heapq.heappush(heap, (dist, x, y))
if len(heap) > k:
heapq.heappop(heap)
return [[x, y] for _, x, y in heap]
Pattern 7: Modified Binary Search
When to use: Sorted/rotated arrays, or when searching in a space where you can eliminate half the candidates each step.
Key variations: Search in rotated array, find first/last occurrence, search in matrix.
Template (Find First True):
python example
def binary_search_first_true(lo, hi, condition):
while lo < hi:
mid = (lo + hi) // 2
if condition(mid):
hi = mid # mid could be answer, search left
else:
lo = mid + 1 # mid is too small
return loExample: Search in Rotated Sorted Array
Example
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
Pattern Recognition Cheatsheet
| Problem Signal | Pattern |
|---|---|
| "Longest/shortest subarray with condition" | Sliding Window |
| "Pair in sorted array" | Two Pointers |
| "Cycle in linked list" | Fast & Slow |
| "Overlapping intervals" | Merge Intervals |
| "Missing/duplicate in [1,n]" | Cyclic Sort |
| "Kth largest/smallest" | Top-K (Heap) |
| "Sorted array search" | Modified Binary Search |
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Essential Coding Patterns for Interviews.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, interview, preparation, coding
Related Data Structures & Algorithms Topics
Continue learning this concept
Interview PreparationDSA Cheatsheet: Quick ReferenceComplete quick-reference cheatsheet covering all data structures with operations and complexities, algorithm complexities, and when-to-use guidelines.Interview PreparationEssential DSA Interview Questions25+ categorized DSA interview questions with approach hints covering arrays, strings, linked lists, trees, graphs, and dynamic programming.Interview PreparationFAANG DSA Sheet: Company-Specific Patterns and ProblemsCompany-specific DSA patterns for Amazon, Google, Meta, Apple, and Microsoft with 50+ curated problems organized by difficulty and category.Interview PreparationProblem Solving Strategies for Coding InterviewsA structured framework for approaching any coding problem: understand, explore examples, brute force, optimize, code, and test. Plus common mistakes and how to think aloud.ArraysArray Interview Problems and SolutionsSolve classic array problems including rotation, duplicate finding, and subarray challenges.Dynamic ProgrammingDynamic Programming Interview ProblemsMaster essential DP interview problems: coin change, edit distance, rod cutting, climbing stairs, and house robber with clear approaches and solutions.