Concepts:
- Built-in sorting algorithms (Timsort in Python)
- Custom sorting with key functions and comparators
- Stable vs unstable sorting, in-place vs out-of-place
- Sorting as preprocessing step for other algorithms
Essential Sorting Templates:
# Basic sorting operations
arr = [3, 1, 4, 1, 5, 9, 2, 6]
# In-place sorting
arr.sort() # Ascending: [1, 1, 2, 3, 4, 5, 6, 9]
arr.sort(reverse=True) # Descending: [9, 6, 5, 4, 3, 2, 1, 1]
# Return new sorted list
sorted_arr = sorted(arr) # Original unchanged
sorted_desc = sorted(arr, reverse=True)
# Custom key functions
words = ["apple", "pie", "cherry", "a"]
words.sort(key=len) # Sort by length: ['a', 'pie', 'apple', 'cherry']
words.sort(key=str.lower) # Case-insensitive sort
# Sort by multiple criteria
students = [("Alice", 85, 20), ("Bob", 90, 19), ("Charlie", 85, 21)]
# Sort by grade (desc), then by age (asc)
students.sort(key=lambda x: (-x[1], x[2]))
# Sort tuples/lists by specific positions
points = [(1, 3), (2, 1), (1, 1), (2, 3)]
points.sort() # Sort by first element, then second: [(1, 1), (1, 3), (2, 1), (2, 3)]
points.sort(key=lambda x: x[1]) # Sort by second element: [(2, 1), (1, 1), (1, 3), (2, 3)]
# Sort strings by custom criteria
def sort_by_vowels_then_length(word):
vowel_count = sum(1 for c in word.lower() if c in 'aeiou')
return (vowel_count, len(word))
words.sort(key=sort_by_vowels_then_length)Advanced Sorting Patterns:
# Merge intervals (requires sorting)
def merge_intervals(intervals):
"""Merge overlapping intervals"""
if not intervals:
return []
# Sort by start time
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
last = merged[-1]
if current[0] <= last[1]: # Overlapping
merged[-1] = [last[0], max(last[1], current[1])]
else:
merged.append(current)
return merged
# Meeting rooms problem
def can_attend_meetings(intervals):
"""Check if person can attend all meetings"""
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i-1][1]:
return False
return True
# Minimum meeting rooms required
def min_meeting_rooms(intervals):
"""Find minimum number of meeting rooms required"""
if not intervals:
return 0
start_times = sorted([i[0] for i in intervals])
end_times = sorted([i[1] for i in intervals])
rooms = 0
end_ptr = 0
for start in start_times:
if start >= end_times[end_ptr]:
end_ptr += 1
else:
rooms += 1
return rooms
# Custom comparator for complex objects
from functools import cmp_to_key
def compare_strings(a, b):
"""Custom comparator: shorter strings first, then lexicographic"""
if len(a) != len(b):
return len(a) - len(b)
if a < b:
return -1
elif a > b:
return 1
else:
return 0
words = ["apple", "pie", "a", "cherry"]
words.sort(key=cmp_to_key(compare_strings))
# Largest number from array
def largest_number(nums):
"""Arrange numbers to form largest possible number"""
def compare(a, b):
if a + b > b + a:
return -1
elif a + b < b + a:
return 1
else:
return 0
nums_str = list(map(str, nums))
nums_str.sort(key=cmp_to_key(compare))
result = ''.join(nums_str)
return '0' if result[0] == '0' else result
# Sort by frequency
def sort_by_frequency(arr):
"""Sort array by frequency of elements"""
from collections import Counter
freq = Counter(arr)
# Sort by frequency (desc), then by value (asc)
return sorted(arr, key=lambda x: (-freq[x], x))
# Top K frequent elements
def top_k_frequent(nums, k):
"""Find k most frequent elements"""
from collections import Counter
import heapq
freq = Counter(nums)
return heapq.nlargest(k, freq.keys(), key=freq.get)Sorting Algorithm Implementations:
# Quick Sort
def quick_sort(arr, low=0, high=None):
"""Quick sort implementation"""
if high is None:
high = len(arr) - 1
if low < high:
pivot_idx = partition(arr, low, high)
quick_sort(arr, low, pivot_idx - 1)
quick_sort(arr, pivot_idx + 1, high)
def partition(arr, low, high):
"""Partition function for quick sort"""
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# Merge Sort
def merge_sort(arr):
"""Merge sort implementation"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
"""Merge two sorted arrays"""
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# Counting Sort (for bounded integers)
def counting_sort(arr, max_val):
"""Counting sort for integers in range [0, max_val]"""
count = [0] * (max_val + 1)
# Count frequencies
for num in arr:
count[num] += 1
# Reconstruct sorted array
result = []
for val, freq in enumerate(count):
result.extend([val] * freq)
return result
# Bucket Sort
def bucket_sort(arr):
"""Bucket sort for floating point numbers in [0, 1)"""
n = len(arr)
buckets = [[] for _ in range(n)]
# Distribute elements into buckets
for num in arr:
bucket_idx = int(num * n)
buckets[bucket_idx].append(num)
# Sort individual buckets and concatenate
result = []
for bucket in buckets:
bucket.sort()
result.extend(bucket)
return resultSorting-Based Problem Patterns:
# 3Sum problem (requires sorting)
def three_sum(nums):
"""Find all unique triplets that sum to zero"""
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
target = -nums[i]
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
result.append([nums[i], nums[left], nums[right]])
# Skip duplicates
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 current_sum < target:
left += 1
else:
right -= 1
return result
# Sort colors (Dutch National Flag)
def sort_colors(nums):
"""Sort array of 0s, 1s, and 2s in-place"""
low = mid = 0
high = len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else: # nums[mid] == 2
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
# Don't increment mid as we need to check swapped element
# Find kth largest element
def find_kth_largest(nums, k):
"""Find kth largest element using sorting"""
nums.sort(reverse=True)
return nums[k-1]
# Alternative: Using quickselect (more efficient)
def quickselect_kth_largest(nums, k):
"""Find kth largest using quickselect algorithm"""
import random
def quickselect(arr, k):
if len(arr) == 1:
return arr[0]
pivot = random.choice(arr)
smaller = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
larger = [x for x in arr if x > pivot]
if k <= len(larger):
return quickselect(larger, k)
elif k <= len(larger) + len(equal):
return pivot
else:
return quickselect(smaller, k - len(larger) - len(equal))
return quickselect(nums, k)
# Wiggle sort
def wiggle_sort(nums):
"""Reorder array so nums[0] < nums[1] > nums[2] < nums[3]..."""
nums.sort()
n = len(nums)
temp = nums[:]
# Fill odd indices with larger half
# Fill even indices with smaller half
left, right = (n - 1) // 2, n - 1
for i in range(n):
if i % 2 == 0:
nums[i] = temp[left]
left -= 1
else:
nums[i] = temp[right]
right -= 1Pro Tips:
- Python's
sort()is stable and uses Timsort (hybrid of merge sort and insertion sort) - Use
keyparameter instead ofcmpfor custom sorting (more efficient) - Sort first when dealing with intervals, pairs, or triplets problems
- Consider counting sort for bounded integer ranges
- Sorting often reduces problem complexity from O(nΒ²) to O(n log n)
- Learn to identify when sorting is beneficial as preprocessing step
Concepts:
- Efficient O(log n) search in sorted arrays
- Lower bound, upper bound, and condition-based binary search
- Works on any monotonic function, not just arrays
- Template method for optimization problems
Essential Binary Search Templates:
# Standard Binary Search (exact match)
def binary_search(arr, target):
"""Find index of target in sorted array, return -1 if not found"""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 # Avoid overflow
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Lower Bound (first position >= target)
def lower_bound(arr, target):
"""Find first index where arr[i] >= target"""
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
# Upper Bound (first position > target)
def upper_bound(arr, target):
"""Find first index where arr[i] > target"""
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left
# Find range of target (first and last occurrence)
def search_range(arr, target):
"""Find first and last position of target"""
def find_first():
left, right = 0, len(arr) - 1
first = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
first = mid
right = mid - 1 # Continue searching left
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return first
def find_last():
left, right = 0, len(arr) - 1
last = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
last = mid
left = mid + 1 # Continue searching right
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return last
first = find_first()
if first == -1:
return [-1, -1]
last = find_last()
return [first, last]Advanced Binary Search Patterns:
# Search in Rotated Sorted Array
def search_rotated_array(nums, target):
"""Find target in rotated sorted array"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# Check which half is sorted
if nums[left] <= nums[mid]: # Left half is sorted
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # Right half is sorted
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
# Find Minimum in Rotated Sorted Array
def find_min_rotated(nums):
"""Find minimum element in rotated sorted array"""
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
# Minimum is in right half
left = mid + 1
else:
# Minimum is in left half (including mid)
right = mid
return nums[left]
# Find Peak Element
def find_peak_element(nums):
"""Find any peak element (nums[i] > nums[i-1] and nums[i] > nums[i+1])"""
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[mid + 1]:
# Peak is in left half (including mid)
right = mid
else:
# Peak is in right half
left = mid + 1
return left
# Search in 2D Matrix
def search_2d_matrix(matrix, target):
"""Search target in 2D matrix where each row and column is sorted"""
if not matrix or not matrix[0]:
return False
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = left + (right - left) // 2
mid_val = matrix[mid // cols][mid % cols]
if mid_val == target:
return True
elif mid_val < target:
left = mid + 1
else:
right = mid - 1
return False
# Alternative: Search 2D Matrix II (different constraint)
def search_2d_matrix_ii(matrix, target):
"""Search in matrix where rows and columns are sorted separately"""
if not matrix or not matrix[0]:
return False
row, col = 0, len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
col -= 1
else:
row += 1
return FalseBinary Search on Answer (Optimization Problems):
# Minimum Speed to Eat Bananas
def min_eating_speed(piles, hours):
"""Find minimum eating speed to finish all bananas within hours"""
def can_finish(speed):
import math
time_needed = sum(math.ceil(pile / speed) for pile in piles)
return time_needed <= hours
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
if can_finish(mid):
right = mid
else:
left = mid + 1
return left
# Capacity to Ship Packages
def ship_within_days(weights, days):
"""Find minimum ship capacity to ship all packages within days"""
def can_ship(capacity):
days_needed = 1
current_weight = 0
for weight in weights:
if current_weight + weight > capacity:
days_needed += 1
current_weight = weight
else:
current_weight += weight
return days_needed <= days
left, right = max(weights), sum(weights)
while left < right:
mid = left + (right - left) // 2
if can_ship(mid):
right = mid
else:
left = mid + 1
return left
# Split Array Largest Sum
def split_array(nums, m):
"""Split array into m subarrays to minimize largest sum"""
def can_split(max_sum):
subarrays = 1
current_sum = 0
for num in nums:
if current_sum + num > max_sum:
subarrays += 1
current_sum = num
else:
current_sum += num
return subarrays <= m
left, right = max(nums), sum(nums)
while left < right:
mid = left + (right - left) // 2
if can_split(mid):
right = mid
else:
left = mid + 1
return left
# Find Kth Smallest Element in Sorted Matrix
def kth_smallest_matrix(matrix, k):
"""Find kth smallest element in sorted matrix"""
def count_less_equal(target):
count = 0
row, col = len(matrix) - 1, 0
while row >= 0 and col < len(matrix[0]):
if matrix[row][col] <= target:
count += row + 1
col += 1
else:
row -= 1
return count
left, right = matrix[0][0], matrix[-1][-1]
while left < right:
mid = left + (right - left) // 2
if count_less_equal(mid) < k:
left = mid + 1
else:
right = mid
return left
# Aggressive Cows / Magnetic Force
def max_distance(positions, m):
"""Place m balls to maximize minimum distance between any two balls"""
positions.sort()
def can_place(min_dist):
count = 1
last_pos = positions[0]
for pos in positions[1:]:
if pos - last_pos >= min_dist:
count += 1
last_pos = pos
return count >= m
left, right = 1, positions[-1] - positions[0]
while left < right:
mid = left + (right - left + 1) // 2 # Bias towards right
if can_place(mid):
left = mid
else:
right = mid - 1
return leftPro Tips:
- Always use
left + (right - left) // 2to avoid integer overflow - For "find first/last valid position", use the template pattern
- Binary search on answer is powerful for optimization problems
- Consider the search space carefully - it doesn't have to be array indices
- Pay attention to boundary conditions and off-by-one errors
- When the condition function is expensive, binary search provides logarithmic complexity
Concepts:
- Make locally optimal choices that lead to global optimum
- Greedy choice property and optimal substructure
- Often involves sorting as preprocessing step
- Common in interval problems, scheduling, and optimization
Essential Greedy Templates:
# Activity Selection / Interval Scheduling
def max_non_overlapping_intervals(intervals):
"""Select maximum number of non-overlapping intervals"""
if not intervals:
return 0
# Sort by end time (greedy choice)
intervals.sort(key=lambda x: x[1])
count = 1
last_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= last_end: # Non-overlapping
count += 1
last_end = end
return count
# Minimum number of arrows to burst balloons
def find_min_arrows(points):
"""Find minimum arrows needed to burst all balloons"""
if not points:
return 0
points.sort(key=lambda x: x[1]) # Sort by end position
arrows = 1
arrow_pos = points[0][1]
for start, end in points[1:]:
if start > arrow_pos: # Need new arrow
arrows += 1
arrow_pos = end
return arrows
# Jump Game
def can_jump(nums):
"""Check if you can reach the last index"""
max_reach = 0
for i in range(len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])
if max_reach >= len(nums) - 1:
return True
return True
def jump_game_min_jumps(nums):
"""Find minimum number of jumps to reach the end"""
if len(nums) <= 1:
return 0
jumps = 0
current_end = 0
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end:
jumps += 1
current_end = farthest
if current_end >= len(nums) - 1:
break
return jumpsAdvanced Greedy Patterns:
# Gas Station Problem
def can_complete_circuit(gas, cost):
"""Find starting gas station to complete circular tour"""
total_gas = sum(gas)
total_cost = sum(cost)
if total_gas < total_cost:
return -1
current_gas = 0
start = 0
for i in range(len(gas)):
current_gas += gas[i] - cost[i]
if current_gas < 0:
# Can't reach next station, try starting from next station
start = i + 1
current_gas = 0
return start
# Assign Cookies
def find_content_children(children, cookies):
"""Assign cookies to children to maximize satisfied children"""
children.sort()
cookies.sort()
child = cookie = 0
satisfied = 0
while child < len(children) and cookie < len(cookies):
if cookies[cookie] >= children[child]:
satisfied += 1
child += 1
cookie += 1
return satisfied
# Task Scheduler
def least_interval(tasks, n):
"""Find minimum time to complete all tasks with cooling period"""
from collections import Counter
import heapq
task_count = Counter(tasks)
max_heap = [-count for count in task_count.values()]
heapq.heapify(max_heap)
time = 0
while max_heap:
cycle = []
# Process one cooling cycle
for _ in range(n + 1):
if max_heap:
cycle.append(heapq.heappop(max_heap))
# Add back tasks that still need processing
for count in cycle:
if count < -1: # Still has remaining tasks
heapq.heappush(max_heap, count + 1)
# Add time for this cycle
time += (n + 1) if max_heap else len(cycle)
return time
# Reorganize String
def reorganize_string(s):
"""Reorganize string so no two adjacent characters are same"""
from collections import Counter
import heapq
char_count = Counter(s)
max_heap = [(-count, char) for char, count in char_count.items()]
heapq.heapify(max_heap)
result = []
prev_count, prev_char = 0, ''
while max_heap:
count, char = heapq.heappop(max_heap)
result.append(char)
# Add back previous character if it still has remaining count
if prev_count < 0:
heapq.heappush(max_heap, (prev_count, prev_char))
prev_count, prev_char = count + 1, char
result_str = ''.join(result)
return result_str if len(result_str) == len(s) else ""
# Remove K Digits
def remove_k_digits(num, k):
"""Remove k digits to make the smallest possible number"""
stack = []
for digit in num:
# Remove larger digits from the end while we can
while stack and stack[-1] > digit and k > 0:
stack.pop()
k -= 1
stack.append(digit)
# Remove remaining digits from the end
while k > 0:
stack.pop()
k -= 1
# Build result and handle leading zeros
result = ''.join(stack).lstrip('0')
return result if result else '0'
# Queue Reconstruction by Height
def reconstruct_queue(people):
"""Reconstruct queue based on height and number of taller people in front"""
# Sort by height desc, then by count asc
people.sort(key=lambda x: (-x[0], x[1]))
result = []
for person in people:
# Insert at position equal to count of taller people
result.insert(person[1], person)
return result
# Candy Distribution
def min_candy(ratings):
"""Distribute minimum candies such that higher rating gets more candy than neighbors"""
n = len(ratings)
candies = [1] * n
# Left to right pass
for i in range(1, n):
if ratings[i] > ratings[i-1]:
candies[i] = candies[i-1] + 1
# Right to left pass
for i in range(n-2, -1, -1):
if ratings[i] > ratings[i+1]:
candies[i] = max(candies[i], candies[i+1] + 1)
return sum(candies)
# Minimum Cost to Connect Sticks
def connect_sticks(sticks):
"""Find minimum cost to connect all sticks"""
import heapq
if len(sticks) <= 1:
return 0
heapq.heapify(sticks)
total_cost = 0
while len(sticks) > 1:
first = heapq.heappop(sticks)
second = heapq.heappop(sticks)
cost = first + second
total_cost += cost
heapq.heappush(sticks, cost)
return total_costPro Tips:
- Greedy algorithms require proof of correctness - verify greedy choice property
- Sorting is often the key preprocessing step
- Consider what metric to optimize (earliest end time, smallest size, etc.)
- Greedy doesn't always work - use when local optimum leads to global optimum
- Common greedy strategies: earliest deadline first, smallest first, largest first
- Combine with other techniques: priority queues, Union-Find, dynamic programming
Concepts:
- LIFO (Last In, First Out) data structure
- Function call stack, expression evaluation, backtracking
- Monotonic stack: maintain elements in increasing/decreasing order
- Powerful for "next greater/smaller" element problems
Essential Stack Templates:
# Basic stack operations using list
stack = []
stack.append(item) # Push
item = stack.pop() # Pop (raises IndexError if empty)
top = stack[-1] # Peek (top element)
is_empty = len(stack) == 0
# Valid Parentheses
def is_valid_parentheses(s):
"""Check if parentheses are properly matched"""
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping: # Closing bracket
if not stack or stack.pop() != mapping[char]:
return False
else: # Opening bracket
stack.append(char)
return len(stack) == 0
# Evaluate Reverse Polish Notation
def eval_rpn(tokens):
"""Evaluate expression in Reverse Polish Notation"""
stack = []
operators = {'+', '-', '*', '/'}
for token in tokens:
if token in operators:
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
# Truncate towards zero
stack.append(int(a / b))
else:
stack.append(int(token))
return stack[0]
# Min Stack (stack with O(1) min operation)
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def top(self):
return self.stack[-1]
def get_min(self):
return self.min_stack[-1]Monotonic Stack Patterns:
# Next Greater Element
def next_greater_elements(nums):
"""Find next greater element for each element"""
n = len(nums)
result = [-1] * n
stack = [] # Store indices
for i in range(n):
# Pop elements that are smaller than current
while stack and nums[stack[-1]] < nums[i]:
result[stack.pop()] = nums[i]
stack.append(i)
return result
# Next Greater Element in Circular Array
def next_greater_elements_circular(nums):
"""Next greater element in circular array"""
n = len(nums)
result = [-1] * n
stack = []
# Process array twice to handle circular nature
for i in range(2 * n):
actual_i = i % n
while stack and nums[stack[-1]] < nums[actual_i]:
result[stack.pop()] = nums[actual_i]
if i < n: # Only push indices from first iteration
stack.append(actual_i)
return result
# Daily Temperatures
def daily_temperatures(temperatures):
"""Find how many days until warmer temperature"""
result = [0] * len(temperatures)
stack = [] # Store indices
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
prev_i = stack.pop()
result[prev_i] = i - prev_i
stack.append(i)
return result
# Largest Rectangle in Histogram
def largest_rectangle_area(heights):
"""Find area of largest rectangle in histogram"""
stack = []
max_area = 0
for i in range(len(heights)):
# Pop heights greater than current height
while stack and heights[stack[-1]] > heights[i]:
h = heights[stack.pop()]
# Width is from stack top to current index
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, h * w)
stack.append(i)
# Process remaining heights in stack
while stack:
h = heights[stack.pop()]
w = len(heights) if not stack else len(heights) - stack[-1] - 1
max_area = max(max_area, h * w)
return max_area
# Maximal Rectangle in Binary Matrix
def maximal_rectangle(matrix):
"""Find largest rectangle in binary matrix"""
if not matrix or not matrix[0]:
return 0
rows, cols = len(matrix), len(matrix[0])
heights = [0] * cols
max_area = 0
for row in matrix:
# Update heights for current row
for i in range(cols):
heights[i] = heights[i] + 1 if row[i] == '1' else 0
# Find largest rectangle in current histogram
max_area = max(max_area, largest_rectangle_area(heights))
return max_area
# Trapping Rain Water
def trap_rainwater(heights):
"""Calculate trapped rainwater using stack"""
stack = []
water = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
# Calculate trapped water
width = i - stack[-1] - 1
height = min(heights[stack[-1]], h) - heights[bottom]
water += width * height
stack.append(i)
return waterAdvanced Stack Applications:
# Remove K Digits (using stack)
def remove_k_digits(num, k):
"""Remove k digits to form smallest number"""
stack = []
for digit in num:
# Remove larger digits while we can
while stack and stack[-1] > digit and k > 0:
stack.pop()
k -= 1
stack.append(digit)
# Remove remaining digits from end
while k > 0:
stack.pop()
k -= 1
# Build result, handling leading zeros
result = ''.join(stack).lstrip('0')
return result if result else '0'
# Remove Duplicate Letters
def remove_duplicate_letters(s):
"""Remove duplicates to get lexicographically smallest result"""
from collections import Counter
char_count = Counter(s)
in_stack = set()
stack = []
for char in s:
char_count[char] -= 1
if char in in_stack:
continue
# Remove characters that are larger and appear later
while (stack and stack[-1] > char and
char_count[stack[-1]] > 0):
removed = stack.pop()
in_stack.remove(removed)
stack.append(char)
in_stack.add(char)
return ''.join(stack)
# Decode String
def decode_string(s):
"""Decode string with pattern k[encoded_string]"""
stack = []
current_num = 0
current_str = ""
for char in s:
if char.isdigit():
current_num = current_num * 10 + int(char)
elif char == '[':
# Push current state to stack
stack.append((current_str, current_num))
current_str = ""
current_num = 0
elif char == ']':
# Pop and construct string
prev_str, num = stack.pop()
current_str = prev_str + current_str * num
else:
current_str += char
return current_str
# Asteroid Collision
def asteroid_collision(asteroids):
"""Simulate asteroid collisions"""
stack = []
for asteroid in asteroids:
while stack and asteroid < 0 < stack[-1]:
# Collision occurs
if stack[-1] < -asteroid:
stack.pop() # Right asteroid destroys left
continue
elif stack[-1] == -asteroid:
stack.pop() # Both destroyed
break # Left asteroid survives or both destroyed
else:
stack.append(asteroid)
return stack
# Car Fleet
def car_fleet(target, position, speed):
"""Calculate number of car fleets reaching target"""
cars = sorted(zip(position, speed), reverse=True)
stack = []
for pos, spd in cars:
time_to_target = (target - pos) / spd
# If this car is slower than the one in front, it forms a fleet
if not stack or time_to_target > stack[-1]:
stack.append(time_to_target)
return len(stack)
# Sum of Subarray Minimums
def sum_subarray_mins(arr):
"""Sum of minimums of all subarrays"""
MOD = 10**9 + 7
n = len(arr)
# Find previous smaller element for each element
prev_smaller = [-1] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
prev_smaller[i] = stack[-1] if stack else -1
stack.append(i)
# Find next smaller element for each element
next_smaller = [n] * n
stack = []
for i in range(n-1, -1, -1):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
next_smaller[i] = stack[-1] if stack else n
stack.append(i)
# Calculate sum
result = 0
for i in range(n):
left_count = i - prev_smaller[i]
right_count = next_smaller[i] - i
result = (result + arr[i] * left_count * right_count) % MOD
return resultStack Pattern Recognition:
def monotonic_stack_template(arr, find_next_greater=True):
"""
Generic monotonic stack template
Args:
arr: Input array
find_next_greater: True for next greater, False for next smaller
"""
result = [-1] * len(arr)
stack = [] # Store indices
for i in range(len(arr)):
# Pop elements based on what we're looking for
while stack:
if find_next_greater and arr[stack[-1]] < arr[i]:
result[stack.pop()] = arr[i]
elif not find_next_greater and arr[stack[-1]] > arr[i]:
result[stack.pop()] = arr[i]
else:
break
stack.append(i)
return result
# When to use each approach:
# 1. Basic stack: Expression evaluation, parentheses matching
# 2. Monotonic increasing: Next smaller element, trapping water
# 3. Monotonic decreasing: Next greater element, daily temperatures
# 4. Min/Max stack: When you need O(1) min/max operationsPro Tips:
- Use indices in monotonic stack to calculate distances
- Stack problems often involve "nearest" or "next" relationships
- For histogram problems, think about expanding rectangles
- Monotonic stack reduces O(nΒ²) brute force to O(n)
- Consider what you're maintaining in the stack: values or indices
- Stack + recursion can solve complex parsing problems
Concepts:
- Min-heap by default in Python
- Max-heap by pushing negative
- Kth largest/smallest, merge k lists
- Running median, top-k frequent, task scheduler
Advanced Patterns:
import heapq
# Min heap
heap = []
heapq.heappush(heap, 3)
heapq.heappop(heap)
# Max heap using negation
heapq.heappush(heap, -num)
max_val = -heapq.heappop(heap)
# Top-k elements
heapq.nlargest(k, arr)
heapq.nsmallest(k, arr)
# Running median with two heaps
class MedianFinder:
def __init__(self):
self.small = [] # max heap (negate values)
self.large = [] # min heap
def addNum(self, num):
heapq.heappush(self.small, -num)
heapq.heappush(self.large, -heapq.heappop(self.small))
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self):
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2
# Merge k sorted lists
def mergeKLists(lists):
heap = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst.val, i, lst))
dummy = ListNode(0)
cur = dummy
while heap:
val, i, node = heapq.heappop(heap)
cur.next = node
cur = cur.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# Task scheduler (cooling time)
def leastInterval(tasks, n):
count = Counter(tasks)
heap = [-cnt for cnt in count.values()]
heapq.heapify(heap)
time = 0
q = deque() # (count, idle_time)
while heap or q:
time += 1
if heap:
cnt = 1 + heapq.heappop(heap)
if cnt:
q.append([cnt, time + n])
if q and q[0][1] == time:
heapq.heappush(heap, q.popleft()[0])
return time
# Kth largest element in stream
class KthLargest:
def __init__(self, k, nums):
self.k = k
self.heap = nums
heapq.heapify(self.heap)
while len(self.heap) > k:
heapq.heappop(self.heap)
def add(self, val):
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap)
return self.heap[0]Pro Tips:
- Use heap for "top-k" or "streaming" problems
- Two-heap technique for running median
- Always consider if min-heap or max-heap fits better
- For custom objects, use tuples:
(priority, item)
Concepts:
- Pointer manipulation, dummy head
- Two-pointers (slow/fast)
- Cycle detection
- Reverse, merge, split
Advanced Patterns:
# Linked List Node
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Reverse linked list
def reverseList(head):
prev = None
cur = head
while cur:
next_temp = cur.next
cur.next = prev
prev = cur
cur = next_temp
return prev
# Reverse nodes in k-group
def reverseKGroup(head, k):
def reverseGroup(start, end):
prev = None
cur = start
while cur != end:
next_temp = cur.next
cur.next = prev
prev = cur
cur = next_temp
return prev
dummy = ListNode(0)
dummy.next = head
prev_group = dummy
while True:
start = prev_group.next
end = start
for _ in range(k):
if not end:
return dummy.next
end = end.next
next_group = end
new_start = reverseGroup(start, end)
prev_group.next = new_start
start.next = next_group
prev_group = start
return dummy.next
# Merge two sorted lists
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
# Cycle detection (Floyd's Algorithm)
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# Find cycle start
def detectCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None
# Find start of cycle
while head != slow:
head = head.next
slow = slow.next
return head
# Remove nth node from end
def removeNthFromEnd(head, n):
dummy = ListNode(0)
dummy.next = head
first = second = dummy
# Move first n+1 steps ahead
for _ in range(n + 1):
first = first.next
# Move both until first reaches end
while first:
first = first.next
second = second.next
second.next = second.next.next
return dummy.next
# Reorder list (L0 -> L1 -> ... -> Ln-1 -> Ln to L0 -> Ln -> L1 -> Ln-1 -> ...)
def reorderList(head):
if not head or not head.next:
return
# Find middle
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Split and reverse second half
second = slow.next
slow.next = None
second = reverseList(second)
# Merge two halves
first = head
while second:
temp1, temp2 = first.next, second.next
first.next = second
second.next = temp1
first, second = temp1, temp2
# Add two numbers (stored in reverse order)
def addTwoNumbers(l1, l2):
dummy = ListNode(0)
cur = dummy
carry = 0
while l1 or l2 or carry:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
carry = total // 10
cur.next = ListNode(total % 10)
cur = cur.next
if l1: l1 = l1.next
if l2: l2 = l2.next
return dummy.next
# Copy list with random pointer
def copyRandomList(head):
if not head:
return None
# Create new nodes and insert them after original nodes
cur = head
while cur:
new_node = ListNode(cur.val)
new_node.next = cur.next
cur.next = new_node
cur = new_node.next
# Set random pointers for new nodes
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# Extract the new list
dummy = ListNode(0)
cur_new = dummy
cur = head
while cur:
cur_new.next = cur.next
cur.next = cur.next.next
cur = cur.next
cur_new = cur_new.next
return dummy.nextPro Tips:
- Always use dummy head for easier manipulation
- Two-pointer technique for many problems (cycle, middle, nth from end)
- Draw diagrams to visualize pointer movements
- Handle edge cases: empty list, single node
- For complex operations, break into smaller steps
Concepts:
- GCD, LCM, prime checking, modular arithmetic
- Number digit manipulation
- Combinatorics (factorials, nCr)
- Mathematical optimization and number theory
Advanced Mathematical Patterns:
import math
from math import gcd, lcm, comb, factorial
# Prime checking (optimized)
def is_prime(n):
if n < 2: return False
if n == 2: return True
if n % 2 == 0: return False
for i in range(3, int(n**0.5) + 1, 2):
if n % i == 0: return False
return True
# Sieve of Eratosthenes
def sieve_of_eratosthenes(n):
"""Generate all primes up to n"""
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n + 1, i):
is_prime[j] = False
return [i for i in range(n + 1) if is_prime[i]]
# Prime factorization
def prime_factors(n):
"""Get prime factors of n"""
factors = []
d = 2
while d * d <= n:
while n % d == 0:
factors.append(d)
n //= d
d += 1
if n > 1:
factors.append(n)
return factors
# Extended Euclidean Algorithm
def extended_gcd(a, b):
"""Return gcd(a,b) and coefficients x,y such that ax + by = gcd(a,b)"""
if a == 0:
return b, 0, 1
gcd_val, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd_val, x, y
# Modular arithmetic
def mod_inverse(a, m):
"""Find modular inverse of a under modulo m"""
gcd_val, x, _ = extended_gcd(a, m)
if gcd_val != 1:
return None # Inverse doesn't exist
return (x % m + m) % m
def mod_pow(base, exp, mod):
"""Calculate (base^exp) % mod efficiently"""
result = 1
base = base % mod
while exp > 0:
if exp % 2 == 1:
result = (result * base) % mod
exp = exp >> 1
base = (base * base) % mod
return result
# Number manipulation
def reverse_integer(x):
"""Reverse digits of integer"""
sign = -1 if x < 0 else 1
x = abs(x)
reversed_num = 0
while x:
reversed_num = reversed_num * 10 + x % 10
x //= 10
return sign * reversed_num
def count_digits(n):
"""Count number of digits"""
return len(str(abs(n)))
def sum_of_digits(n):
"""Sum of digits"""
total = 0
n = abs(n)
while n:
total += n % 10
n //= 10
return total
# Advanced combinatorics
def nCr_mod(n, r, mod):
"""Calculate nCr % mod using Lucas theorem or precomputed factorials"""
if r > n or r < 0:
return 0
if r == 0 or r == n:
return 1
# Using Pascal's triangle for small values
if n <= 1000:
dp = [[0] * (r + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = 1
for i in range(1, n + 1):
for j in range(1, min(i + 1, r + 1)):
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod
return dp[n][r]
# For larger values, use modular arithmetic
num = 1
den = 1
for i in range(r):
num = (num * (n - i)) % mod
den = (den * (i + 1)) % mod
return (num * mod_inverse(den, mod)) % mod
# Catalan numbers
def catalan_number(n):
"""Calculate nth Catalan number"""
if n <= 1:
return 1
catalan = [0] * (n + 1)
catalan[0] = catalan[1] = 1
for i in range(2, n + 1):
for j in range(i):
catalan[i] += catalan[j] * catalan[i - 1 - j]
return catalan[n]
# Perfect squares and cubes
def is_perfect_square(n):
"""Check if n is a perfect square"""
if n < 0:
return False
root = int(n**0.5)
return root * root == n
def sqrt_integer(x):
"""Integer square root using binary search"""
if x < 2:
return x
left, right = 1, x
while left <= right:
mid = left + (right - left) // 2
square = mid * mid
if square == x:
return mid
elif square < x:
left = mid + 1
else:
right = mid - 1
return right
# Geometry basics
def distance(p1, p2):
"""Euclidean distance between two points"""
return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)**0.5
def area_triangle(p1, p2, p3):
"""Area of triangle using coordinates"""
return abs((p1[0]*(p2[1] - p3[1]) + p2[0]*(p3[1] - p1[1]) + p3[0]*(p1[1] - p2[1])) / 2)
# Number theory applications
def happy_number(n):
"""Check if number is happy (sum of squares of digits eventually reaches 1)"""
def get_sum_of_squares(num):
total = 0
while num:
digit = num % 10
total += digit * digit
num //= 10
return total
seen = set()
while n != 1 and n not in seen:
seen.add(n)
n = get_sum_of_squares(n)
return n == 1
def ugly_number(n):
"""Check if number's only prime factors are 2, 3, 5"""
if n <= 0:
return False
for factor in [2, 3, 5]:
while n % factor == 0:
n //= factor
return n == 1Pro Tips:
- Use built-in
math.gcd()andmath.lcm()for efficiency - For large numbers, always consider modular arithmetic
- Sieve of Eratosthenes for multiple prime queries
- Binary search can solve many mathematical optimization problems
- Handle edge cases: negative numbers, zero, overflow
Concepts:
- Mimic the problem as described
- No special algorithm, just accurate implementation
- Track state changes, position updates, and game mechanics
- Common in game simulations, robot movement, and state machines
Advanced Simulation Patterns:
# Matrix rotation/transformation
def rotate_matrix_90(matrix):
"""Rotate matrix 90 degrees clockwise"""
n = len(matrix)
# Transpose
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Reverse each row
for i in range(n):
matrix[i].reverse()
return matrix
def spiral_matrix(matrix):
"""Traverse matrix in spiral order"""
if not matrix or not matrix[0]:
return []
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
# Right
for col in range(left, right + 1):
result.append(matrix[top][col])
top += 1
# Down
for row in range(top, bottom + 1):
result.append(matrix[row][right])
right -= 1
# Left
if top <= bottom:
for col in range(right, left - 1, -1):
result.append(matrix[bottom][col])
bottom -= 1
# Up
if left <= right:
for row in range(bottom, top - 1, -1):
result.append(matrix[row][left])
left += 1
return result
# Robot/Game simulation
def robot_bounded_circle(instructions):
"""Check if robot moves in a circle"""
x, y = 0, 0
dx, dy = 0, 1 # Initially facing north
for instruction in instructions:
if instruction == 'G':
x, y = x + dx, y + dy
elif instruction == 'L':
dx, dy = -dy, dx
elif instruction == 'R':
dx, dy = dy, -dx
# Robot is bounded if it's at origin OR not facing north
return (x == 0 and y == 0) or (dx != 0 or dy != 1)
# Conway's Game of Life
def game_of_life(board):
"""Simulate one step of Conway's Game of Life"""
m, n = len(board), len(board[0])
def count_neighbors(r, c):
count = 0
for dr in [-1, 0, 1]:
for dc in [-1, 0, 1]:
if dr == 0 and dc == 0:
continue
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and abs(board[nr][nc]) == 1:
count += 1
return count
# Use different values to track state changes
for i in range(m):
for j in range(n):
neighbors = count_neighbors(i, j)
if board[i][j] == 1: # Live cell
if neighbors < 2 or neighbors > 3:
board[i][j] = -1 # Dies
else: # Dead cell
if neighbors == 3:
board[i][j] = 2 # Becomes alive
# Update to final state
for i in range(m):
for j in range(n):
if board[i][j] > 0:
board[i][j] = 1
else:
board[i][j] = 0
# Tic-tac-toe game
class TicTacToe:
def __init__(self, n):
self.n = n
self.rows = [0] * n
self.cols = [0] * n
self.diagonal = 0
self.anti_diagonal = 0
def move(self, row, col, player):
"""Make a move and return winner (0 if no winner yet)"""
add = 1 if player == 1 else -1
self.rows[row] += add
self.cols[col] += add
if row == col:
self.diagonal += add
if row + col == self.n - 1:
self.anti_diagonal += add
# Check for win
if (abs(self.rows[row]) == self.n or
abs(self.cols[col]) == self.n or
abs(self.diagonal) == self.n or
abs(self.anti_diagonal) == self.n):
return player
return 0
# Parking system simulation
class ParkingSystem:
def __init__(self, big, medium, small):
self.spaces = [0, big, medium, small] # Index 0 unused
def addCar(self, carType):
if self.spaces[carType] > 0:
self.spaces[carType] -= 1
return True
return False
# Stock trading simulation
def max_profit_with_cooldown(prices):
"""Stock trading with cooldown period"""
if not prices:
return 0
# held[i]: max profit when holding stock on day i
# sold[i]: max profit when not holding stock on day i (just sold)
# rest[i]: max profit when not holding stock on day i (didn't sell)
held = -prices[0]
sold = 0
rest = 0
for i in range(1, len(prices)):
prev_held, prev_sold, prev_rest = held, sold, rest
held = max(prev_held, prev_rest - prices[i])
sold = prev_held + prices[i]
rest = max(prev_rest, prev_sold)
return max(sold, rest)Pro Tips:
- Break complex simulations into smaller state updates
- Use appropriate data structures (sets for O(1) lookup, deques for queues)
- Track all state variables carefully
- Consider using state machines for complex logic
- Test edge cases thoroughly (boundaries, empty states, etc.)
Concepts:
- Count how many values satisfy a condition
- Usually used with hash maps or prefix sum
- Combinatorial counting and mathematical analysis
- Often combined with other techniques for optimization
Advanced Counting Patterns:
# Subarray sum equals k
def subarray_sum_k(nums, k):
"""Count number of subarrays with sum equal to k"""
count = 0
prefix_sum = 0
prefix_count = {0: 1} # Empty prefix has sum 0
for num in nums:
prefix_sum += num
# Check if (prefix_sum - k) exists
count += prefix_count.get(prefix_sum - k, 0)
prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
return count
# Count number of nice subarrays (exactly k odd numbers)
def number_of_subarrays(nums, k):
"""Count subarrays with exactly k odd numbers"""
# Convert to binary: 1 for odd, 0 for even
binary = [x % 2 for x in nums]
return subarray_sum_k(binary, k)
# Count vowel strings
def count_vowel_strings(n):
"""Count strings of length n using only vowels in lexicographical order"""
# dp[i][j] = number of strings of length i ending with vowel j
vowels = 5 # a, e, i, o, u
dp = [1] * vowels
for i in range(2, n + 1):
for j in range(vowels - 2, -1, -1):
dp[j] += dp[j + 1]
return sum(dp)
# Count binary strings without consecutive 1s
def count_binary_strings(n):
"""Count n-length binary strings with no consecutive 1s"""
if n == 1:
return 2
# dp[i][0] = strings of length i ending with 0
# dp[i][1] = strings of length i ending with 1
prev_0, prev_1 = 1, 1
for i in range(2, n + 1):
curr_0 = prev_0 + prev_1 # Can append 0 to any string
curr_1 = prev_0 # Can only append 1 to strings ending with 0
prev_0, prev_1 = curr_0, curr_1
return prev_0 + prev_1
# Count palindromic subsequences
def count_palindromic_subsequences(s):
"""Count distinct palindromic subsequences"""
n = len(s)
dp = [[0] * n for _ in range(n)]
# Single characters are palindromes
for i in range(n):
dp[i][i] = 1
# Length 2 substrings
for i in range(n - 1):
dp[i][i + 1] = 2 if s[i] != s[i + 1] else 1
# Length 3 and above
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
return dp[0][n - 1]
# Count islands in 2D grid
def count_islands(grid):
"""Count number of islands in binary grid"""
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
count = 0
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
return
grid[i][j] = '0' # Mark as visited
for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
dfs(i + di, j + dj)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
dfs(i, j)
return count
# Count valid parentheses combinations
def generate_parentheses(n):
"""Generate all valid parentheses combinations"""
result = []
def backtrack(current, open_count, close_count):
if len(current) == 2 * n:
result.append(current)
return
if open_count < n:
backtrack(current + '(', open_count + 1, close_count)
if close_count < open_count:
backtrack(current + ')', open_count, close_count + 1)
backtrack('', 0, 0)
return result
def count_valid_parentheses(n):
"""Count valid parentheses (Catalan number)"""
if n == 0:
return 1
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for j in range(i):
dp[i] += dp[j] * dp[i - 1 - j]
return dp[n]
# Count paths in grid
def count_paths(m, n, obstacles=None):
"""Count paths from top-left to bottom-right"""
dp = [[1] * n for _ in range(m)]
# Handle obstacles
if obstacles:
for r, c in obstacles:
dp[r][c] = 0
for i in range(m):
for j in range(n):
if obstacles and (i, j) in obstacles:
dp[i][j] = 0
continue
if i > 0:
dp[i][j] = dp[i-1][j]
if j > 0:
dp[i][j] += dp[i][j-1]
return dp[m-1][n-1]
# Count frequency of elements
def top_k_frequent(nums, k):
"""Find k most frequent elements"""
count = Counter(nums)
# Use bucket sort for O(n) solution
buckets = [[] for _ in range(len(nums) + 1)]
for num, freq in count.items():
buckets[freq].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
for num in buckets[i]:
result.append(num)
if len(result) == k:
return result
return result
# Count inversions in array
def count_inversions(nums):
"""Count number of inversions (i < j but nums[i] > nums[j])"""
def merge_sort_count(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, left_inv = merge_sort_count(arr[:mid])
right, right_inv = merge_sort_count(arr[mid:])
merged = []
i = j = inv_count = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
inv_count += len(left) - i # All remaining elements in left are greater
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged, left_inv + right_inv + inv_count
_, inversions = merge_sort_count(nums)
return inversions
# Count distinct subsequences
def num_distinct(s, t):
"""Count distinct subsequences of s that equal t"""
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Empty string t can be formed in 1 way from any string s
for i in range(m + 1):
dp[i][0] = 1
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = dp[i-1][j] # Don't use s[i-1]
if s[i-1] == t[j-1]:
dp[i][j] += dp[i-1][j-1] # Use s[i-1]
return dp[m][n]Pro Tips:
- Use hash maps for frequency counting and prefix sums
- Dynamic programming often helps with counting problems
- Consider mathematical formulas (Catalan numbers, combinations)
- Bucket sort can be useful for frequency-based counting
- Break complex counting into smaller, manageable parts
| Topic | Time Complexity | Space Complexity | Key Techniques | Must-Know Patterns |
|---|---|---|---|---|
| Sorting | O(n log n) | O(1) - O(n) | Timsort, Custom comparators | Interval merging, 3Sum, Meeting rooms |
| Binary Search | O(log n) | O(1) | Lower/upper bound, Search space | Rotated array, Search answer, Peak finding |
| Greedy | O(n log n) | O(1) - O(n) | Local optimum β Global | Activity selection, Jump game, Gas station |
| Stack/Monotonic | O(n) | O(n) | LIFO, Monotonic property | Next greater, Valid parentheses, Histogram |
| Heap | O(log n) insert/delete | O(n) | Priority queue, K-way merge | Top-K, Running median, Task scheduler |
| Linked List | O(n) traversal | O(1) operations | Two pointers, Dummy head | Reverse, Cycle detection, Merge |
| Math | Varies | O(1) - O(n) | Number theory, Modular arithmetic | GCD/LCM, Prime sieve, Combinatorics |
| Simulation | Problem-dependent | Problem-dependent | State tracking, Game mechanics | Matrix ops, Game of life, Robot movement |
| Counting | O(n) - O(nΒ²) | O(n) | Hash maps, Prefix sums | Subarray sums, Frequency, Palindromes |
π When to Use Each Technique:
- Sorting: When order matters, interval problems, finding duplicates/pairs
- Binary Search: Monotonic functions, "find first/last", optimization problems
- Greedy: Optimization with local choices, scheduling, interval problems
- Stack: Nested structures, nearest greater/smaller, expression parsing
- Heap: Top-K problems, merge sorted data, scheduling with priorities
- Linked List: Pointer manipulation, cycle detection, list operations
- Math: Number properties, modular arithmetic, combinatorial problems
- Simulation: Game mechanics, step-by-step processes, state machines
- Counting: Frequency analysis, subsequences, combinatorial counting
π Pro-Level Optimizations:
- Sorting: Use
keyfunctions creatively, stable sort properties - Binary Search: Template for any monotonic condition, floating-point search
- Greedy: Prove greedy choice property, combine with sorting
- Stack: Monotonic stack for range queries, stack + hash for O(1) operations
- Heap: Two-heap technique, lazy propagation, heapify vs repeated insertion
- Linked List: Sentinel nodes, runner technique, in-place operations
- Math: Sieve for multiple queries, extended Euclidean, fast exponentiation
- Simulation: State machines, efficient data structures, boundary handling
- Counting: Inclusion-exclusion, generating functions, DP + counting
β Avoid These Mistakes:
- Sorting: Forgetting stability requirements, wrong comparator logic
- Binary Search: Off-by-one errors, infinite loops, wrong boundary conditions
- Greedy: Not proving optimality, missing counter-examples
- Stack: Not handling empty stack, wrong monotonic property
- Heap: Confusing min/max heap, not maintaining heap property
- Linked List: Null pointer issues, losing references, cycle in modifications
- Math: Integer overflow, division by zero, negative modulo
- Simulation: Off-by-one in coordinates, missing edge cases
- Counting: Double counting, missing base cases, overflow in large numbers
β You've Mastered Tier 2 When You Can:
- Implement any sorting algorithm and use custom comparators fluently
- Write binary search for any monotonic condition without bugs
- Identify and prove when greedy approach works
- Use monotonic stack to solve range query problems efficiently
- Implement heap-based algorithms (merge K lists, running median)
- Manipulate linked lists with two-pointers and dummy nodes
- Apply number theory concepts (GCD, primes, modular arithmetic)
- Simulate complex state machines and game mechanics accurately
- Count complex combinatorial structures using DP and math
π― Practice Recommendations:
- Easy: 50+ problems per topic
- Medium: 30+ problems per topic
- Hard: 10+ problems per topic
- Focus: Pattern recognition and template application
# Enhanced imports for Tier 2 algorithms
from collections import Counter, defaultdict, deque, OrderedDict
from itertools import *
from functools import reduce, lru_cache, partial, cmp_to_key
from operator import add, mul, or_, and_, xor, itemgetter, attrgetter
import heapq
import bisect
import math
import random
# π₯ SORTING WITH BUILT-IN POWER
def advanced_sorting_techniques():
"""Leveraging Python's sorting capabilities"""
# Multi-key sorting with complex logic
def sort_students(students):
# Sort by: grade (desc), then name (asc), then age (asc)
return sorted(students, key=lambda x: (-x[1], x[0], x[2]))
# Using itemgetter for cleaner multi-field sorting
from operator import itemgetter
def sort_with_itemgetter(data):
# Sort by 2nd field, then 1st field
return sorted(data, key=itemgetter(1, 0))
# Custom comparator using cmp_to_key
def largest_number_comparator(x, y):
# For largest number problem: compare x+y vs y+x
if x + y > y + x:
return -1
elif x + y < y + x:
return 1
return 0
def largest_number(nums):
nums_str = list(map(str, nums))
nums_str.sort(key=cmp_to_key(largest_number_comparator))
result = ''.join(nums_str)
return '0' if result[0] == '0' else result
# Bucket sort using defaultdict
def bucket_sort_optimized(arr, bucket_size=5):
if not arr:
return arr
min_val, max_val = min(arr), max(arr)
bucket_count = (max_val - min_val) // bucket_size + 1
buckets = defaultdict(list)
# Distribute into buckets
for num in arr:
bucket_idx = (num - min_val) // bucket_size
buckets[bucket_idx].append(num)
# Sort each bucket and concatenate
result = []
for i in range(bucket_count):
if i in buckets:
buckets[i].sort()
result.extend(buckets[i])
return result
# Counting sort with Counter
def counting_sort_enhanced(arr):
counter = Counter(arr)
min_val, max_val = min(counter), max(counter)
result = []
for val in range(min_val, max_val + 1):
result.extend([val] * counter[val])
return result
# π₯ BINARY SEARCH ENHANCED
class BinarySearchToolkit:
"""Advanced binary search patterns using bisect"""
@staticmethod
def search_insert_position(arr, target):
"""Find position to insert target to maintain sorted order"""
return bisect.bisect_left(arr, target)
@staticmethod
def find_first_last_position(arr, target):
"""Find first and last position of target"""
left = bisect.bisect_left(arr, target)
if left == len(arr) or arr[left] != target:
return [-1, -1]
right = bisect.bisect_right(arr, target) - 1
return [left, right]
@staticmethod
def search_2d_matrix_optimized(matrix, target):
"""Search in row-wise and column-wise sorted matrix"""
if not matrix or not matrix[0]:
return False
# Flatten conceptually and use binary search
rows, cols = len(matrix), len(matrix[0])
def get_value(idx):
return matrix[idx // cols][idx % cols]
left, right = 0, rows * cols - 1
while left <= right:
mid = (left + right) // 2
mid_val = get_value(mid)
if mid_val == target:
return True
elif mid_val < target:
left = mid + 1
else:
right = mid - 1
return False
@staticmethod
def kth_smallest_in_matrix(matrix, k):
"""Find kth smallest element in sorted matrix using binary search"""
n = len(matrix)
left, right = matrix[0][0], matrix[n-1][n-1]
def count_less_equal(mid):
count = 0
row, col = n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] <= mid:
count += row + 1
col += 1
else:
row -= 1
return count
while left < right:
mid = (left + right) // 2
if count_less_equal(mid) < k:
left = mid + 1
else:
right = mid
return left
# π₯ GREEDY ALGORITHMS ENHANCED
def greedy_with_heapq():
"""Greedy algorithms leveraging heapq for efficiency"""
def meeting_rooms_ii_optimized(intervals):
"""Minimum meeting rooms using heap"""
if not intervals:
return 0
intervals.sort(key=lambda x: x[0]) # Sort by start time
heap = [] # End times of ongoing meetings
for start, end in intervals:
# If earliest ending meeting ends before current starts
if heap and heap[0] <= start:
heapq.heappop(heap)
heapq.heappush(heap, end)
return len(heap)
def task_scheduler_optimized(tasks, n):
"""Task scheduler using Counter and heapq"""
counter = Counter(tasks)
max_heap = [-count for count in counter.values()]
heapq.heapify(max_heap)
time = 0
while max_heap:
temp = []
for _ in range(n + 1):
if max_heap:
temp.append(heapq.heappop(max_heap))
# Add back tasks that still need to be done
for count in temp:
if count < -1: # Still has remaining tasks
heapq.heappush(max_heap, count + 1)
# Add time: either full cycle or remaining tasks
time += (n + 1) if max_heap else len(temp)
return time
def reorganize_string_optimized(s):
"""Reorganize string using Counter and heapq"""
counter = Counter(s)
max_heap = [(-count, char) for char, count in counter.items()]
heapq.heapify(max_heap)
result = []
prev_count, prev_char = 0, ''
while max_heap:
count, char = heapq.heappop(max_heap)
result.append(char)
# Add back previous character if it still has count
if prev_count < 0:
heapq.heappush(max_heap, (prev_count, prev_char))
prev_count, prev_char = count + 1, char
return ''.join(result) if len(result) == len(s) else ""
# π₯ LINKED LIST WITH ENHANCED PATTERNS
def linked_list_advanced():
"""Advanced linked list patterns using built-in optimizations"""
def merge_k_sorted_lists_heap(lists):
"""Merge k sorted lists using heapq"""
import heapq
heap = []
# Add first node of each list to heap
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst.val, i, lst))
dummy = ListNode(0)
current = dummy
while heap:
val, i, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
def remove_duplicates_optimized(head):
"""Remove duplicates using set for O(n) time"""
if not head:
return head
seen = set()
dummy = ListNode(0)
dummy.next = head
prev = dummy
current = head
while current:
if current.val in seen:
prev.next = current.next
else:
seen.add(current.val)
prev = current
current = current.next
return dummy.next
# π₯ NUMBER THEORY ENHANCED
def number_theory_optimized():
"""Number theory using Python's math module and optimizations"""
def gcd_multiple(numbers):
"""GCD of multiple numbers using reduce"""
return reduce(math.gcd, numbers)
def lcm_multiple(numbers):
"""LCM of multiple numbers"""
def lcm(a, b):
return abs(a * b) // math.gcd(a, b)
return reduce(lcm, numbers)
def sieve_of_eratosthenes_optimized(n):
"""Optimized sieve using list comprehension"""
sieve = [True] * (n + 1)
sieve[0] = sieve[1] = False
for i in range(2, int(n**0.5) + 1):
if sieve[i]:
# Mark multiples starting from i*i
for j in range(i*i, n + 1, i):
sieve[j] = False
return [i for i, is_prime in enumerate(sieve) if is_prime]
def prime_factorization_optimized(n):
"""Prime factorization using Counter"""
factors = Counter()
d = 2
while d * d <= n:
while n % d == 0:
factors[d] += 1
n //= d
d += 1
if n > 1:
factors[n] += 1
return factors
def modular_exponentiation(base, exp, mod):
"""Fast modular exponentiation using pow"""
return pow(base, exp, mod)
def chinese_remainder_theorem(remainders, moduli):
"""CRT using math operations"""
total = 0
prod = reduce(mul, moduli)
for r, m in zip(remainders, moduli):
p = prod // m
total += r * pow(p, -1, m) * p
return total % prod
# π₯ COMBINATORICS WITH MATH MODULE
def combinatorics_enhanced():
"""Advanced combinatorics using math.comb and itertools"""
def pascal_triangle_row(n):
"""Generate nth row of Pascal's triangle efficiently"""
return [math.comb(n, k) for k in range(n + 1)]
def catalan_number(n):
"""Calculate nth Catalan number"""
return math.comb(2 * n, n) // (n + 1)
def stirling_second_kind(n, k):
"""Stirling numbers of second kind using dynamic programming"""
if n == 0 and k == 0:
return 1
if n == 0 or k == 0:
return 0
# DP approach with memoization
@lru_cache(maxsize=None)
def dp(n, k):
if k == 1 or k == n:
return 1
return k * dp(n-1, k) + dp(n-1, k-1)
return dp(n, k)
def derangements(n):
"""Count derangements (permutations with no fixed points)"""
if n <= 1:
return 0 if n == 1 else 1
return (n - 1) * (derangements(n - 1) + derangements(n - 2))
def partition_count(n, k):
"""Count ways to partition n into k parts"""
@lru_cache(maxsize=None)
def dp(n, k, min_val=1):
if k == 1:
return 1 if n >= min_val else 0
if n < k * min_val:
return 0
count = 0
for i in range(min_val, n - k + 2):
count += dp(n - i, k - 1, i)
return count
return dp(n, k)
# π₯ SIMULATION WITH RANDOM MODULE
def simulation_techniques():
"""Enhanced simulation using random module"""
def monte_carlo_pi(iterations):
"""Estimate Ο using Monte Carlo method"""
inside_circle = 0
for _ in range(iterations):
x, y = random.random(), random.random()
if x*x + y*y <= 1:
inside_circle += 1
return 4 * inside_circle / iterations
def reservoir_sampling(stream, k):
"""Reservoir sampling for random k elements from stream"""
reservoir = []
for i, item in enumerate(stream):
if i < k:
reservoir.append(item)
else:
# Replace with probability k/(i+1)
j = random.randint(0, i)
if j < k:
reservoir[j] = item
return reservoir
def shuffle_array(arr):
"""Fisher-Yates shuffle"""
result = arr.copy()
for i in range(len(result) - 1, 0, -1):
j = random.randint(0, i)
result[i], result[j] = result[j], result[i]
return result
def weighted_random_selection(weights):
"""Select index with probability proportional to weights"""
total = sum(weights)
r = random.uniform(0, total)
cumulative = 0
for i, weight in enumerate(weights):
cumulative += weight
if r <= cumulative:
return i
return len(weights) - 1 # Fallback
# π₯ GAME THEORY AND STATE MACHINES
def game_theory_enhanced():
"""Game theory problems with optimized state management"""
def nim_game_winning_positions(piles):
"""Determine winning positions in Nim game"""
# XOR all pile sizes (Sprague-Grundy theorem)
nimber = reduce(xor, piles)
return nimber != 0 # Non-zero nimber means winning position
def stone_game_dp(piles):
"""Stone game using memoization"""
@lru_cache(maxsize=None)
def dp(i, j):
if i > j:
return 0
# Current player takes from left or right
take_left = piles[i] - dp(i + 1, j)
take_right = piles[j] - dp(i, j - 1)
return max(take_left, take_right)
return dp(0, len(piles) - 1) > 0
def optimal_strategy_for_game(arr):
"""Optimal strategy using 2D DP with memoization"""
n = len(arr)
@lru_cache(maxsize=None)
def solve(i, j):
if i > j:
return 0
if i == j:
return arr[i]
# Take left: arr[i] + min of opponent's best moves
take_left = arr[i] + min(solve(i+2, j), solve(i+1, j-1))
# Take right: arr[j] + min of opponent's best moves
take_right = arr[j] + min(solve(i+1, j-1), solve(i, j-2))
return max(take_left, take_right)
total = sum(arr)
player1_max = solve(0, n-1)
return player1_max > total - player1_max| Algorithm | Standard Approach | Built-in Enhanced | Performance Gain |
|---|---|---|---|
| Sorting | Manual quicksort O(n log n) | sorted() with key functions |
2-3x faster, more readable |
| Binary Search | Manual implementation | bisect module |
Built-in C optimization |
| Heap Operations | Manual heap maintenance | heapq module |
Optimized C implementation |
| GCD/LCM | Euclidean algorithm | math.gcd(), reduce() |
Faster + handles edge cases |
| Combinatorics | Manual calculation | math.comb(), itertools |
Prevents overflow, optimized |
| Random Operations | Basic random | random module methods |
More distributions available |
# Impress with one-liners
top_k_frequent = lambda arr, k: heapq.nlargest(k, Counter(arr).items(), key=itemgetter(1))
merge_intervals = lambda intervals: reduce(lambda acc, curr: acc[:-1] + [acc[-1][:1] + [max(acc[-1][1], curr[1])]] if acc and acc[-1][1] >= curr[0] else acc + [curr], sorted(intervals))
find_kth_largest = lambda arr, k: heapq.nlargest(k, arr)[-1]
# Show deep understanding
def explain_timsort_advantage():
"""Explain why Python's sort is optimal"""
return "Timsort is hybrid stable sort, optimized for real-world data with existing order"
def demonstrate_bisect_power():
"""Show bisect superiority over manual binary search"""
import bisect
# Handles edge cases, cleaner code, C-optimized
return "bisect handles all edge cases and is implemented in C"