Array DSA Patterns

A Complete Beginner's Guide — Python Edition

This guide is written for complete beginners. Every concept is explained from scratch — no prior DSA
knowledge assumed.
All code examples are written in Python.

7 Patterns • Real LeetCode Problems • Step-by-Step Walkthroughs

Before You Start Reading This Guide

What is this guide?

When you first learn DSA, it seems like there are hundreds of different problems to
💡 memorise. But actually, most array problems follow just 7 patterns. Learn these patterns
and you can solve hundreds of problems — even ones you've never seen before.

What is an Array?
An array is a list of items stored one after another in memory. In Python, we use lists for this:

# An array (list) in Python

nums = [3, 1, 4, 1, 5, 9, 2, 6]

# Access by index (starts at 0)

print(nums[0]) # 3 (first element)
print(nums[-1]) # 6 (last element)

# Length
print(len(nums)) # 8

# Slice: nums[start:end] gives elements from index start to end-1

print(nums[1:4]) # [1, 4, 1]

How to Use This Guide

For each pattern, follow this 3-step learning process:

STEP 1: Read the 'What is this pattern?' section — understand the IDEA before the code.
STEP 2: Walk through the dry run yourself with pen and paper — trace every step.
STEP 3: Close the guide and re-write the code from memory. Only look back if stuck.

A warning about memorisation

⚠️ Do NOT memorise code. Understand WHY the pattern works. If you understand the idea,
you can always recreate the code — even in an interview.
 1 Two Pointers

What is this pattern?

Imagine you're looking for two people in a room who together weigh exactly 100kg. The slow way:
check every possible pair (person 1 + person 2, person 1 + person 3, etc.). The fast way: sort everyone
by weight, then use one person from the lightest end and one from the heaviest end — if they're too
heavy, move the heavy person lighter; if too light, move the light person heavier.

That is exactly the Two Pointers pattern. We place one pointer (left) at the start of the array and one
(right) at the end. We move them toward each other based on what we find.

How to recognise this pattern

The problem involves a SORTED array. It asks you to find a pair or triplet that meets some
🔍 condition (sums to a target, etc.). Or it asks you to reverse, check palindrome, or remove
duplicates in-place.

The Template
Here is the two-pointer skeleton you will use again and again:

def two_pointers(nums):
left = 0 # Start pointer at the beginning
right = len(nums) - 1 # Start pointer at the end

while left < right: # Keep going until pointers meet

current = nums[left] + nums[right] # (or whatever logic you need)

if current == target:
# Found what we need!
return [left, right]
elif current < target:
left += 1 # Sum too small -> move left pointer right to get bigger
value
else:
right -= 1 # Sum too big -> move right pointer left to get smaller
value

return [] # Nothing found

Problem 1: Two Sum II (Sorted Array)

Problem Statement
Given a sorted array of integers and a target number, find two numbers that add up to the
target.
Return their 1-based indices (index starting from 1, not 0).

Example: nums = [2, 7, 11, 15], target = 9

Answer: [1, 2] because nums[0] + nums[1] = 2 + 7 = 9

Step 1 — Understand the problem

Before writing any code, ask yourself: What do I have? What do I need?

What I HAVE: What I NEED:

- A sorted array (important!) - Two indices i, j where nums[i] + nums[j] = target
- A target sum - Return [i+1, j+1] (1-based)

Step 2 — Why Two Pointers works here

Because the array is SORTED, we know:
• If nums[left] + nums[right] is too SMALL, we need a bigger number — move left pointer right
• If nums[left] + nums[right] is too BIG, we need a smaller number — move right pointer left
• If it equals target — done!

The key insight

🧠 In a sorted array, moving left pointer right INCREASES the sum. Moving right pointer left
DECREASES the sum. We use this to zero in on the target.

Step 3 — Dry Run (trace through by hand)

Array: [2, 7, 11, 15], Target = 9

Step left index right index nums[left] nums[right Sum Action

]
Start 0 3 2 15 17 17 > 9 →
move right
left
Step 1 0 2 2 11 13 13 > 9 →
move right
left
Step 2 0 1 2 7 9 9 == 9 →
 FOUND!
Return
[1,2]

Step 4 — Python Code

def two_sum_sorted(nums, target):
left = 0
right = len(nums) - 1

while left < right:

current_sum = nums[left] + nums[right]

if current_sum == target:
# +1 because problem wants 1-based indices
return [left + 1, right + 1]
elif current_sum < target:
left += 1 # Need a bigger number
else:
right -= 1 # Need a smaller number

return [] # No solution found

# Test it:
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]
print(two_sum_sorted([2, 3, 4], 6)) # [1, 3]

Time and Space Complexity

Time: O(n) — we go through the array at most once (each pointer moves at most n times)
Space: O(1) — we only use two extra variables (left and right), no extra array needed

Compare to brute force: O(n²) time because you'd check every pair with two nested loops.

Problem 2: Container With Most Water

Problem Statement
You are given heights = [1, 8, 6, 2, 5, 4, 8, 3, 7].
Each value is the height of a vertical line. Find two lines that form a container holding the
most water.

Water held = min(height[left], height[right]) × (right - left)

Answer: 49 (lines at index 1 and 8: min(8,7) × (8-1) = 7 × 7 = 49)

def max_water(heights):
left = 0
right = len(heights) - 1
max_area = 0

while left < right:

# Width = distance between the two lines
width = right - left
# Height = the shorter line (water overflows over the short side)
height = min(heights[left], heights[right])
# Area of water this container holds
area = width * height

max_area = max(max_area, area)

# Move the pointer that points to the SHORTER line

# Why? Moving the taller line can only make things worse (width
decreases AND height stays same/worse)
if heights[left] < heights[right]:
left += 1
else:
right -= 1

return max_area

print(max_water([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49
 2 Sliding Window

What is this pattern?

Picture a train with 3 carriages moving along a track. As the train moves forward, it loses one carriage
at the back and gains one at the front. The 'window' of 3 carriages slides across the track.

The Sliding Window pattern is exactly this. We maintain a 'window' (a range of elements) and slide it
across the array. Instead of re-computing everything from scratch each time, we just add the new
element on the right and remove the old element on the left.

How to recognise this pattern

The problem asks about a CONTIGUOUS subarray or substring (elements in a row, no
🔍 skipping). Keywords: 'subarray of size k', 'longest subarray with condition', 'minimum length
subarray', 'substring with no repeats'.

Two Types of Sliding Window

Fixed Size Window Variable Size Window

Window size k is GIVEN to you. Window grows and shrinks based on a condition.
You always add one from the right Expand right when condition is NOT met.
and remove one from the left. Shrink left when condition is MET or violated.

Example: 'Max sum of k consecutive elements' Example: 'Longest substring without repeats'

Problem 1: Max Sum Subarray of Size K (Fixed Window)

Problem Statement
Given an array and a number k, find the maximum sum of any k consecutive elements.

Example: nums = [2, 1, 5, 1, 3, 2], k = 3

Subarrays of size 3: [2,1,5]=8, [1,5,1]=7, [5,1,3]=9, [1,3,2]=6
Answer: 9

The naive approach (slow)

For every starting position, add up k numbers. This is O(n × k) time:
 # Slow approach - DON'T use this
def max_sum_slow(nums, k):
max_sum = 0
for i in range(len(nums) - k + 1): # Each starting position
window_sum = sum(nums[i:i+k]) # Add k elements every time
max_sum = max(max_sum, window_sum)
return max_sum
# Problem: sum() loops k times for every position -> O(n*k)

The sliding window approach (fast)

Key insight: when the window slides one step, the sum changes by just TWO elements: we add the
new right element and subtract the old left element. No need to re-sum everything!

def max_sum_subarray(nums, k):

# Step 1: Calculate sum of the first window
window_sum = sum(nums[:k]) # Sum of first k elements
max_sum = window_sum

# Step 2: Slide the window across the rest

for i in range(k, len(nums)):
# Add the new element coming in from the right (nums[i])
# Remove the old element going out from the left (nums[i - k])
window_sum = window_sum + nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)

return max_sum

print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3)) # 9

Dry run
nums = [2, 1, 5, 1, 3, 2], k = 3

i Window Add (nums[i]) Remove window_sum max_sum

(nums[i-k])
Init [2, 1, 5] - - 8 8
3 [1, 5, 1] 1 2 7 8
4 [5, 1, 3] 3 1 9 9
5 [1, 3, 2] 2 5 6 9
Problem 2: Longest Substring Without Repeating Characters (Variable
Window)

Problem Statement
Given a string, find the length of the longest substring with no repeated characters.

Example: s = 'abcabcbb'
Answer: 3 (the substring 'abc')

Here the window size is NOT fixed. We grow the window from the right, and when we find a repeated
character, we shrink from the left until there are no more repeats.

def longest_no_repeat(s):
char_set = set() # Tracks which characters are in our current window
left = 0 # Left boundary of window
max_length = 0

for right in range(len(s)): # right pointer grows the window

# If current char already in window, shrink from left until it's gone
while s[right] in char_set:
char_set.remove(s[left]) # Remove left char from window
left += 1 # Move left boundary right

# Now s[right] is NOT in the window, so we can safely add it

char_set.add(s[right])

# Window size = right - left + 1

max_length = max(max_length, right - left + 1)

return max_length

print(longest_no_repeat('abcabcbb')) # 3
print(longest_no_repeat('pwwkew')) # 3

Dry run
s = 'abcabc'

right s[right] char_set left Window max_length

0 a {a} 0 a 1
1 b {a,b} 0 ab 2
2 c {a,b,c} 0 abc 3
3 a →remove a, 1 bca 3
left=1,
{b,c,a}
4 b →remove b, 2 cab 3
left=2,
{c,a,b}
5 c →remove c, 3 abc 3
left=3,
{a,b,c}
 3 Prefix Sum

What is this pattern?

Think about a bank account. To find out how much money you spent between day 10 and day 20, you
don't re-add up every transaction in that range. Instead, you look at the balance on day 20 and subtract
the balance on day 9. That's a prefix sum.

A prefix sum array pre-computes the running total. prefix[i] = sum of all elements from index 0 to i-1.
Then any range sum can be found in O(1) time with just one subtraction.

How to recognise this pattern

Keywords: 'subarray sum equals k', 'range sum query', 'count subarrays with sum'. The
🔍 problem asks about sums of subarrays, especially when there are multiple queries on the
same array.

Building a Prefix Sum Array

nums = [1, 2, 3, 4, 5]
prefix = [0, 1, 3, 6, 10, 15]
# ^ ^
# prefix[0]=0 prefix[5]=15 (total sum)

# Rule: prefix[i] = prefix[i-1] + nums[i-1]

# Or equivalently: prefix[i+1] = prefix[i] + nums[i]

def build_prefix(nums):
prefix = [0] * (len(nums) + 1) # One extra slot at the start (= 0)
for i in range(len(nums)):
prefix[i + 1] = prefix[i] + nums[i]
return prefix

# Range sum from index l to r (inclusive):

# sum(l, r) = prefix[r+1] - prefix[l]
# Example: sum(1, 3) = prefix[4] - prefix[1] = 10 - 1 = 9 (= 2+3+4 ✓)

Problem 1: Range Sum Query

Problem Statement
 Given an array, answer multiple queries: 'what is the sum from index l to r?'

nums = [1, 2, 3, 4, 5]
Query(0, 2) → 1+2+3 = 6
Query(1, 3) → 2+3+4 = 9

class RangeSum:
def __init__(self, nums):
# Build prefix array once at the start
[Link] = [0] * (len(nums) + 1)
for i in range(len(nums)):
[Link][i + 1] = [Link][i] + nums[i]

def query(self, left, right):

# O(1) answer using the formula
return [Link][right + 1] - [Link][left]

rs = RangeSum([1, 2, 3, 4, 5])
print([Link](0, 2)) # 6 (1+2+3)
print([Link](1, 3)) # 9 (2+3+4)
print([Link](0, 4)) # 15 (all)

Problem 2: Subarray Sum Equals K (Advanced)

Problem Statement
Given an array and a target k, count the number of subarrays whose sum equals k.

nums = [1, 2, 3], k = 3

Subarrays: [1,2] (sum=3), [3] (sum=3) → Answer: 2

This is trickier. We want to count all (l, r) pairs where sum(l, r) = k, i.e. prefix[r+1] - prefix[l] = k, i.e.
prefix[l] = prefix[r+1] - k.

The clever insight

As we scan right, for each position we ask: 'how many previous prefix sums equal
🧠 (current_prefix - k)?' We track this with a dictionary that counts how many times we've seen
each prefix sum.

def subarray_sum_k(nums, k):

# seen_sums maps: prefix_sum_value -> how many times we've seen it
 seen_sums = {0: 1} # We start with prefix sum 0 seen once (empty prefix)
current_sum = 0
count = 0

for num in nums:

current_sum += num

# We need: current_sum - prefix[l] = k

# So: prefix[l] = current_sum - k
needed = current_sum - k

# How many times have we seen 'needed' as a prefix sum?

# Each one gives us a valid subarray ending here
count += seen_sums.get(needed, 0)

# Record that we've now seen current_sum

seen_sums[current_sum] = seen_sums.get(current_sum, 0) + 1

return count

print(subarray_sum_k([1, 2, 3], 3)) # 2

print(subarray_sum_k([1, 1, 1], 2)) # 2

Dry run
nums = [1, 2, 3], k = 3

num current_sum needed (sum- seen_sums.g count seen_sums

k) et(needed)
Start 0 - - 0 {0:1}
1 1 -2 0 0 {0:1, 1:1}
2 3 0 1 1 {0:1, 1:1,
3:1}
3 6 3 1 2 {0:1, 1:1,
3:1, 6:1}
 4 Fast & Slow Pointers

What is this pattern?

Imagine a circular running track. If one runner goes twice as fast as another, the faster runner will
eventually lap the slower one and they'll meet. But on a straight track, the faster runner just gets further
ahead and they never meet.

We can use this to detect cycles. The slow pointer moves 1 step at a time. The fast pointer moves 2
steps. If there's a cycle, they will eventually meet. If there's no cycle, the fast pointer reaches the end.

How to recognise this pattern

Keywords: 'detect cycle', 'find middle element', 'happy number', 'find duplicate (use array as
🔍 implicit linked list)'. The core idea is always: can I model this as a sequence of values and
detect if it loops?

Problem 1: Happy Number

Problem Statement
A happy number is defined by the process: Replace the number by the sum of squares of its
digits.
Repeat until it reaches 1 (happy) or loops forever (not happy).

Example: 19 → 1² + 9² = 82 → 8² + 2² = 68 → 6² + 8² = 100 → 1² + 0² + 0² = 1 Happy!

We need to detect if the sequence loops (which means it will never reach 1).

def sum_of_squares(n):
total = 0
while n > 0:
digit = n % 10 # Last digit
total += digit ** 2
n //= 10 # Remove last digit
return total

def is_happy(n):
slow = n
fast = sum_of_squares(n) # Fast starts one step ahead

# Keep going until they meet OR fast reaches 1

 while fast != 1 and slow != fast:
slow = sum_of_squares(slow) # Move slow 1 step
fast = sum_of_squares(sum_of_squares(fast)) # Move fast 2 steps

return fast == 1 # If fast reached 1, it's happy!

print(is_happy(19)) # True
print(is_happy(4)) # False (enters a cycle)

Problem 2: Find the Duplicate Number

Problem Statement
Given an array of n+1 numbers where each number is between 1 and n, find the duplicate.
You cannot modify the array. Use O(1) extra space.

Example: nums = [1, 3, 4, 2, 2] → Answer: 2

Trick: treat the array like a linked list where nums[i] points to index nums[i].
A duplicate means two indices point to the same next index → a cycle exists!

Why this is a cycle problem

Think of it this way: index 0 → nums[0], index nums[0] → nums[nums[0]], etc. Because
🧠 there's a duplicate value, two different indices point to the same next index — creating a
cycle. Floyd's algorithm finds where the cycle begins, which is the duplicate.

def find_duplicate(nums):
# Phase 1: Detect that a cycle exists (find meeting point inside cycle)
slow = nums[0]
fast = nums[0]

while True: # We're guaranteed a cycle exists, so this will stop

slow = nums[slow] # Move 1 step
fast = nums[nums[fast]] # Move 2 steps
if slow == fast: # They met inside the cycle
break

# Phase 2: Find the entrance to the cycle (= the duplicate)

# Mathematical property: start one pointer from beginning, one from meeting
point
# They will meet exactly at the cycle entrance
finder = nums[0]
 while finder != slow:
finder = nums[finder]
slow = nums[slow]

return slow # This is the duplicate number

print(find_duplicate([1, 3, 4, 2, 2])) # 2
print(find_duplicate([3, 1, 3, 4, 2])) # 3
 5 Merge Intervals

What is this pattern?

Suppose you have a list of meetings for the day: 9–11am, 10am–12pm, 2–3pm, 2:30–4pm. To plan
your day, you want to merge the overlapping ones: 9am–12pm (first two overlap), 2–4pm (last two
overlap).

The Merge Intervals pattern handles problems involving ranges [start, end]. The key insight: if you
SORT by start time, overlapping intervals will always be next to each other. Then one pass is enough.

How to recognise this pattern

The input has pairs of numbers representing ranges: [start, end]. Keywords: 'merge
🔍 overlapping intervals', 'insert interval', 'meeting rooms', 'minimum number of meeting
rooms', 'non-overlapping intervals'.

When do two intervals overlap?

Two intervals [a, b] and [c, d] overlap when c <= b (the second one starts before the first one ends).
After sorting by start:

OVERLAP (merge them): NO OVERLAP (keep separate):

[1, 4] and [2, 6] [1, 3] and [5, 8]
→ 2 <= 4, so they overlap → 5 > 3, no overlap
→ Merge to [1, 6] → Keep both as-is
(take min of starts, max of ends) (second starts after first ends)

Problem 1: Merge Overlapping Intervals

Problem Statement
Given a list of intervals, merge all overlapping intervals.

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Because [1,3] and [2,6] overlap → merged to [1,6]

def merge_intervals(intervals):
# Step 1: Sort by start time
 # (Crucial! Without sorting, overlapping intervals might not be adjacent)
[Link](key=lambda x: x[0])

merged = [intervals[0]] # Start with the first interval

for current in intervals[1:]: # Look at each remaining interval

last = merged[-1] # The last interval we've merged so far

# Do current and last overlap?

# They overlap if current starts before last ends
if current[0] <= last[1]:
# Merge: extend last interval's end if needed
last[1] = max(last[1], current[1])
else:
# No overlap: add current as a new interval
[Link](current)

return merged

print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]

Dry run
Sorted intervals: [[1,3],[2,6],[8,10],[15,18]]

current last in merged Overlap? Action merged so far

Start [1,3] - Add first [[1,3]]
interval
[2,6] [1,3] 2 <= 3 YES Extend: [[1,6]]
max(3,6)=6 →
last becomes
[1,6]
[8,10] [1,6] 8 <= 6? NO No overlap, [[1,6],[8,10]]
add new
[15,18] [8,10] 15 <= 10? NO No overlap, [[1,6],[8,10],
add new [15,18]]
 6 Cyclic Sort

What is this pattern?

Imagine you have name tags numbered 1 to 5, but they're mixed up in random boxes. The rule is: tag
number i should be in box i. Instead of using a sorted algorithm, you can fix the entire mess in one
pass: pick up whatever is in the current box, and place it in the correct box. Repeat until every box has
the right tag.

This works when your array contains numbers in the range [1, n] (or [0, n]). The key: number i belongs
at index i - 1. After placing everything, anything out of place is a missing or duplicate number.

How to recognise this pattern

The array contains numbers in range [1, n] or [0, n]. Keywords: 'find missing number', 'find
🔍 all duplicates', 'find all missing numbers', 'find the duplicate'. The constraint is always that
numbers fall in a specific range equal to the array size.

The Core Algorithm

# After sorting, nums[i] should equal i + 1
# (number 1 at index 0, number 2 at index 1, etc.)

def cyclic_sort(nums):
i = 0
while i < len(nums):
# Where should nums[i] go?
correct_index = nums[i] - 1

if nums[i] != nums[correct_index]: # Is it already in the right place?

# Swap nums[i] with the element at its correct position
nums[i], nums[correct_index] = nums[correct_index], nums[i]
# DON'T increment i — the swapped element might also be wrong
else:
i += 1 # This element is correctly placed, move on

return nums

print(cyclic_sort([3, 1, 5, 4, 2])) # [1, 2, 3, 4, 5]

print(cyclic_sort([2, 6, 4, 3, 1, 5])) # [1, 2, 3, 4, 5, 6]
Problem: Find Missing Number

Problem Statement
Given an array of n distinct numbers taken from [0, 1, ..., n], find the missing number.

nums = [3, 0, 1] → Answer: 2 (the range is [0,1,2,3], 2 is missing)

nums = [9,6,4,2,3,5,7,0,1] → Answer: 8

def find_missing(nums):
n = len(nums)
i = 0

# Step 1: Cyclic sort — put each number at its correct index

# Range is [0, n], so number j goes at index j
while i < n:
j = nums[i] # Where should nums[i] go?
if j < n and nums[i] != nums[j]: # j < n because n itself has no slot
nums[i], nums[j] = nums[j], nums[i]
else:
i += 1

# Step 2: Find the missing number

# After sorting, nums[i] should equal i
for i in range(n):
if nums[i] != i:
return i # This index has the wrong number → i is missing

return n # All indices 0..n-1 are correct, so n itself is missing

print(find_missing([3, 0, 1])) # 2
print(find_missing([9,6,4,2,3,5,7,0,1]))# 8

Dry run
nums = [3, 0, 1], n = 3. Number j goes at index j.

i nums[i] Correct index (j) Action Array after

0 3 3 (out of i++ (skip 3, [3,0,1]
range!) it has no
slot)
1 0 0 swap nums[1] [0,3,1]
and nums[0]
 1 3 3 (out of i++ (skip 3) [0,3,1]
range!)
2 1 1 swap nums[2] [0,1,3]
and nums[1]
2 3 3 (out of i++ [0,1,3]
range!)
Scan - - nums[2]=3 != 2 Answer: 2
→ return 2
 7 Top K Elements (Heap)

What is a Heap?
Before learning this pattern, you need to understand what a heap is. A heap is a special data structure
that always gives you the smallest (min-heap) or largest (max-heap) element in O(1) time, and
adding/removing elements takes only O(log n) time.

Min-Heap Max-Heap (trick in Python)

The SMALLEST element is always at the top. Python only has min-heap built-in.
For max-heap, negate your values!
Example heap: [1, 3, 5, 7, 9]
heap[0] = 1 (always minimum) Push -value → the most negative
(= largest original) is on top.
Python: import heapq
[Link](heap, value) ← add When you pop, negate again
[Link](heap) ← remove min to get the original value back.

import heapq

# Min-heap example
min_heap = []
[Link](min_heap, 5)
[Link](min_heap, 1)
[Link](min_heap, 3)
print(min_heap[0]) # 1 (smallest always at top)
print([Link](min_heap))# 1 (removes and returns smallest)

# Max-heap using negation trick

max_heap = []
[Link](max_heap, -5) # Push -5 (so 5 acts as 'largest')
[Link](max_heap, -1)
[Link](max_heap, -3)
print(-max_heap[0]) # 5 (negate back to get original)
print(-[Link](max_heap))# 5

The Pattern: Why Use a Heap of Size K?

If you want the K largest elements, the obvious approach is to sort (O(n log n)). But a heap gives you
O(n log k). When k is much smaller than n, this is much faster.
 The key insight
To find the K LARGEST elements, maintain a MIN-heap of size K. Why min-heap?
🧠 Because the smallest element in the heap is the 'weakest competitor'. When a new element
comes in, it replaces the smallest if it's bigger. At the end, all K elements remaining in the
heap are the K largest.

How to recognise this pattern

🔍 Keywords: 'K largest elements', 'K smallest elements', 'Kth largest', 'K most frequent', 'K
closest points'. Any time you need to track the top K of something.

Problem 1: Kth Largest Element

Problem Statement
Find the kth largest element in an array (not necessarily distinct).

nums = [3, 2, 1, 5, 6, 4], k = 2

Answer: 5 (sorted descending: [6,5,4,3,2,1], 2nd is 5)

import heapq

def kth_largest(nums, k):

min_heap = [] # Will hold the k largest elements seen so far

for num in nums:

[Link](min_heap, num) # Add current number

# If heap grows beyond k, remove the smallest

# (it can't be in the top k)
if len(min_heap) > k:
[Link](min_heap) # Remove smallest

# The heap now contains exactly the k largest elements

# The smallest of these k elements = kth largest overall
return min_heap[0] # Top of min-heap = smallest in heap

print(kth_largest([3, 2, 1, 5, 6, 4], 2)) # 5

print(kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)) # 4
Dry run
nums = [3, 2, 1, 5, 6, 4], k = 2

num heap before Push Pop if > k? heap after

3 [] [3] No (size=1) [3]
2 [3] [2,3] No (size=2) [2,3]
1 [2,3] [1,2,3] Yes! Pop 1 [2,3]
5 [2,3] [2,3,5] Yes! Pop 2 [3,5]
6 [3,5] [3,5,6] Yes! Pop 3 [5,6]
4 [5,6] [4,5,6] Yes! Pop 4 [5,6]

heap[0] = 5 = 2nd largest ✓

Problem 2: Top K Frequent Elements

Problem Statement
Given an array, return the k most frequent elements.

nums = [1,1,1,2,2,3], k = 2
Answer: [1, 2] (1 appears 3 times, 2 appears 2 times)

import heapq
from collections import Counter

def top_k_frequent(nums, k):

# Step 1: Count frequencies
freq = Counter(nums) # {1: 3, 2: 2, 3: 1}

# Step 2: Use a min-heap of size k

# Heap stores (frequency, number) pairs
# Min-heap will put the LEAST frequent on top (easy to evict)
min_heap = []

for num, count in [Link]():

[Link](min_heap, (count, num))
if len(min_heap) > k:
[Link](min_heap) # Remove least frequent

# Step 3: Extract the numbers from heap (ignore frequencies)

return [num for count, num in min_heap]
print(top_k_frequent([1,1,1,2,2,3], 2)) # [2, 1] or [1, 2]
Quick Reference: Which Pattern Do I Use?

When you see a new problem, ask these questions in order:

Is the array SORTED, and do I need to find a PAIR or TRIPLET?

1 → Use Two Pointers. Put left at start, right at end, move them toward each other.

Does the problem ask about a CONTIGUOUS SUBARRAY or SUBSTRING?

→ If the window size k is GIVEN: Fixed Sliding Window
2 → If you need the LONGEST/SHORTEST subarray meeting a condition: Variable
Sliding Window
→ If it's about COUNTING subarrays with a sum: Prefix Sum + HashMap

Does the problem involve CYCLES or finding a MIDDLE element?

3 → Use Fast & Slow Pointers. Slow moves 1 step, fast moves 2.

Does the input have INTERVALS [start, end]?

4 → Use Merge Intervals. Sort by start time, then do a greedy merge pass.

Does the array contain numbers in the range [1, n] and ask about
MISSING/DUPLICATE numbers?
5 → Use Cyclic Sort. Place each number at its correct index, then scan for
mismatches.

Does the problem ask for K LARGEST, K SMALLEST, or K MOST

FREQUENT?
6
→ Use Top K / Heap. Maintain a heap of size k.

Complexity Summary

Pattern Time Space Why?

Two Pointers O(n) O(1) Single pass, two
 indices

Sliding Window O(n) O(k) Each element enters

and leaves window
once

Prefix Sum O(n) build O(n) O(1) per query after

build

Fast & Slow O(n) O(1) Floyd's cycle

detection, no extra
space

Merge Intervals O(n log n) O(n) Sorting dominates;

merged list is output

Cyclic Sort O(n) O(1) Each swap places at

least one element
correctly

Top K / Heap O(n log k) O(k) Heap of size k; log k

per push/pop

Final Advice for Beginners

1. Don't skip the dry runs. Tracing through examples is how patterns become intuition.
2. Solve at least 3-5 problems per pattern before moving to the next. Repetition builds
confidence.
3. When you're stuck, ask: 'What property of the input am I not exploiting yet?'
4. Brute force first if needed — it's always valid to start slow and optimise.
5. Time yourself. Aim for 30 minutes per medium problem after practicing each pattern.