4 min read
Clone Graph: Copy Nodes Without Falling Into the Cycle
Undirected graph deep copy with a hash map and BFS — the interview classic that checks whether you treat neighbors as pointers or as values.
Tag
Python
Articles tagged Python on The Augmented Dev.
101 articles
3 min read
Average of Levels: Aggregating Inside the Snapshot
Replace the level list with a running sum — the aggregation variant. Python solution and complexity analysis for the BFS interview pattern.
3 min read
Backspace String Compare Backwards in Constant Space
Compare typed strings with backspaces in O(1) space, scanning backwards. Python solution and complexity analysis for the two pointers interview pattern.
3 min read
Best Time to Buy and Sell Stock as a Window Problem
Max profit in one pass by tracking the running minimum buy price. Python solution and complexity analysis for the sliding window interview pattern.
3 min read
Binary Search Done Correctly: Invariants Over Memorization
The template everyone thinks they know — invariant included. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Level Order Traversal Bottom Up: One Reverse Away
Bottom-up levels — resist cleverness, reverse at the end. Python solution and complexity analysis for the BFS interview pattern.
3 min read
Binary Tree Level Order Traversal: The BFS Template
The level-snapshot queue loop that eight other questions reuse verbatim. Python solution and complexity analysis for the BFS interview pattern.
3 min read
Binary Tree Maximum Path Sum: The Hard Version of Diameter
Any-to-any max path — clamp negative arms to zero and track the bend. Python solution and complexity analysis for the DFS interview pattern.
3 min read
Binary Tree Right Side View: Last Node Standing Per Level
What you see from the right — take each level's final node. Python solution and complexity analysis for the BFS interview pattern.
3 min read
Zigzag Level Order Traversal Without Queue Gymnastics
Alternate level direction with a flag — never touch the queue order. Python solution and complexity analysis for the BFS interview pattern.
3 min read
Capacity to Ship Packages: The Same Search, New Costume
Minimum ship capacity via a greedy day-splitting check. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Car Pooling: Difference Arrays Meet Interval Events
Capacity checking with +passengers/−passengers events on a number line. Python solution and complexity analysis for the merge intervals interview pattern.
4 min read
Circular Array Loop: Cycles With Direction Constraints
Cycle detection with direction rules and path invalidation. Python solution and complexity analysis for the fast and slow pointers interview pattern.
3 min read
Climbing Stairs: Where Dynamic Programming Starts
Fibonacci in costume — the recurrence-first discipline in miniature. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Coin Change: Unbounded Choices, Minimum Count
Fewest coins to a target — and why greedy dies on [1, 3, 4]. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Container With Most Water and the Greedy Pointer Proof
Maximize trapped area and prove the greedy pointer move is safe. Python solution and complexity analysis for the two pointers interview pattern.
3 min read
Cousins in Binary Tree: Same Level, Different Parents
Track depth and parent per node — two facts decide cousinhood. Python solution and complexity analysis for the BFS interview pattern.
3 min read
Delete the Middle Node of a Linked List in One Pass
One-pass middle deletion — track the node before the midpoint. Python solution and complexity analysis for the fast and slow pointers interview pattern.
3 min read
Diameter of a Binary Tree: Answers That Bypass the Root
Return one thing, track another — the two-quantity DFS shape. Python solution and complexity analysis for the DFS interview pattern.
4 min read
Edit Distance: The Capstone Two-String DP
Levenshtein distance — three operations, one table. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Employee Free Time: Gaps in a Merged Union of Schedules
Common free intervals across k schedules — flatten, merge, read the gaps. Python solution and complexity analysis for the merge intervals interview pattern.
3 min read
Find All Anagrams in a String With One Sliding Histogram
Every anagram start index in one pass — the counting version of inclusion. Python solution and complexity analysis for the sliding window interview pattern.
3 min read
Find the Duplicate Number as a Hidden Linked List Cycle
No mutation, O(1) space — the array is secretly a cyclic list. Python solution and complexity analysis for the fast and slow pointers interview pattern.
3 min read
Find First and Last Position With Two Boundary Searches
Range of a duplicated target via lower and upper bound in O(log n). Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Find Median From a Data Stream With Two Heaps
The two-heap balance: max-heap low half, min-heap high half. Python solution and complexity analysis for the heap and top-k interview pattern.
3 min read
Find Minimum in Rotated Sorted Array: Hunting the Seam
Converge on the rotation seam via right-edge comparison. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Find Peak Element: Binary Search Without Sorted Input
Climb the slope — halving works even on unsorted data. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Fruit Into Baskets: At Most Two Distinct, Decoded
Google's storytelling version of longest subarray with two distinct values. Python solution and complexity analysis for the sliding window interview pattern.
3 min read
Happy Number: Cycle Detection Without a Linked List
Floyd's algorithm on an implicit sequence — no nodes required. Python solution and complexity analysis for the fast and slow pointers interview pattern.
3 min read
House Robber: The Take or Skip Recurrence
Non-adjacent maximum sum — the two-variable rolling DP. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Insert Interval Without Re-Sorting Anything
Exploit existing sortedness: before, absorb, after — three phases. Python solution and complexity analysis for the merge intervals interview pattern.
3 min read
Intersection of Two Linked Lists: The Pointer Switching Proof
Find where two lists merge by switching heads at the ends. Python solution and complexity analysis for the fast and slow pointers interview pattern.
3 min read
Interval List Intersections With Two Sorted Pointers
Intersect two sorted interval lists with merge-style pointers. Python solution and complexity analysis for the merge intervals interview pattern.
3 min read
Invert Binary Tree: Swap on the Way Down
The famous swap-children recursion — and its iterative twin. Python solution and complexity analysis for the DFS interview pattern.
3 min read
Jump Game: When Greedy Replaces the DP Table
Track the farthest reachable index — O(n) with one integer of state. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
K Closest Points to Origin Without Square Roots
Bounded max-heap on squared distance — monotone transforms are free. Python solution and complexity analysis for the heap and top-k interview pattern.
3 min read
Find K Pairs With Smallest Sums: Frontier Expansion
Explore an implicit sorted matrix — seed one row, expand neighbors lazily. Python solution and complexity analysis for the heap and top-k interview pattern.
3 min read
Koko Eating Bananas: Minimize a Feasible Rate
Search on eating speed with a ceiling-division check. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Kth Largest Element: Heap Versus Quickselect
The bounded min-heap of size k — and when quickselect beats it. Python solution and complexity analysis for the heap and top-k interview pattern.
3 min read
Kth Largest in a Stream: The Persistent Bounded Heap
Design a class where the size-k min-heap is the entire state. Python solution and complexity analysis for the heap and top-k interview pattern.
3 min read
Last Stone Weight: Simulation on a Max-Heap
Repeatedly smash the two heaviest — negation makes heapq a max-heap. Python solution and complexity analysis for the heap and top-k interview pattern.
3 min read
Linked List Cycle Detection With Floyd's Tortoise and Hare
Detect a cycle in O(1) space and argue why the pointers must meet. Python solution and complexity analysis for the fast and slow pointers interview pattern.
3 min read
Linked List Cycle II: Finding the Cycle Entry Point
Return the node where the cycle starts — and prove the reset trick. Python solution and complexity analysis for the fast and slow pointers interview pattern.
3 min read
Longest Common Subsequence: The Grid That Explains Diffs
Match extends the diagonal, mismatch takes the better drop. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Longest Increasing Subsequence: From n² to n log n
The tails array and patience sorting — binary search inside DP. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Longest Repeating Character Replacement and the Lazy Window
Replace k chars to maximize a repeat run — with a window that never shrinks. Python solution and complexity analysis for the sliding window interview pattern.
3 min read
Longest Substring Without Repeating Characters, Done Right
The most-asked string question: variable window with a last-seen map. Python solution and complexity analysis for the sliding window interview pattern.
3 min read
Lowest Common Ancestor: The Bubble Up Argument
Return what you found — the split node emerges from the recursion. Python solution and complexity analysis for the DFS interview pattern.
3 min read
Max Consecutive Ones III: Budgeted Zeros in the Window
Longest run of ones after flipping at most k zeros — count, never flip. Python solution and complexity analysis for the sliding window interview pattern.
3 min read
Maximum Average Subarray: Fixed Size Sliding Window Basics
The fixed-window template: slide a length-k sum in O(1) per step. Python solution and complexity analysis for the sliding window interview pattern.
3 min read
Maximum Depth of a Binary Tree: DFS in Four Lines
The four-line recursion that teaches the subtree-answer discipline. Python solution and complexity analysis for the DFS interview pattern.
3 min read
Maximum Subarray: Kadane's Algorithm as One Line of DP
Extend or restart — the ending-here state that makes it one pass. Python solution and complexity analysis for the dynamic programming interview pattern.
4 min read
Median of Two Sorted Arrays: The Partition Search
The O(log min(m, n)) partition argument, demystified. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Meeting Rooms: The Interval Warm Up That Still Filters
Can one person attend every meeting? Sort and scan adjacent pairs. Python solution and complexity analysis for the merge intervals interview pattern.
3 min read
Meeting Rooms II: Minimum Rooms via Heap or Sweep
Peak concurrent meetings — the min-heap of end times, plus the sweep line. Python solution and complexity analysis for the merge intervals interview pattern.
3 min read
Merge Intervals: The Canonical Sort and Sweep
Collapse overlapping intervals — the question every FAANG loop reuses. Python solution and complexity analysis for the merge intervals interview pattern.
3 min read
Merge K Sorted Lists: The Heap of Heads
K-way merge in O(n log k) — with the tuple tie-break heapq requires. Python solution and complexity analysis for the heap and top-k interview pattern.
3 min read
Middle of the Linked List in One Pass
Find the midpoint without counting — the half-speed invariant. Python solution and complexity analysis for the fast and slow pointers interview pattern.
3 min read
Minimum Arrows to Burst Balloons: Greedy on Overlaps
Group intervals sharing a common point — activity selection inverted. Python solution and complexity analysis for the merge intervals interview pattern.
3 min read
Minimum Depth of a Binary Tree: Why BFS Beats DFS Here
First leaf wins — early exit that full-tree DFS cannot match. Python solution and complexity analysis for the BFS interview pattern.
3 min read
Minimum Size Subarray Sum: Shrink Greedily, Count Carefully
Shortest window reaching a target sum — shrink while you still can. Python solution and complexity analysis for the sliding window interview pattern.
3 min read
Minimum Window Substring: The Hard Sliding Window Boss
Smallest window covering all of t, with the have-versus-need counter. Python solution and complexity analysis for the sliding window interview pattern.
3 min read
Move Zeroes: In Place Partitioning With a Write Pointer
Push all zeroes to the back in one pass, preserving order. Python solution and complexity analysis for the two pointers interview pattern.
3 min read
My Calendar I: Booking Without Double Booking
Design a booking class — the two-sided overlap predicate under test. Python solution and complexity analysis for the merge intervals interview pattern.
3 min read
Non-overlapping Intervals and the End Time Greedy
Minimum removals to make intervals disjoint — sort by end, keep greedily. Python solution and complexity analysis for the merge intervals interview pattern.
3 min read
Number of Islands: Flood Fill as Component Counting
The most-asked grid question — sink each island as you count it. Python solution and complexity analysis for the DFS interview pattern.
3 min read
Palindrome Linked List in O(1) Space: Split, Reverse, Compare
Palindrome check via midpoint split and half reversal. Python solution and complexity analysis for the fast and slow pointers interview pattern.
3 min read
Partition Equal Subset Sum: 0/1 Knapsack in Disguise
Equal-halves split — subset-sum with the backward loop. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Path Sum II: Backtracking With a Shared Path Buffer
Collect all matching root-to-leaf paths — append, recurse, pop. Python solution and complexity analysis for the DFS interview pattern.
3 min read
Path Sum: Threading State Down the Recursion
Root-to-leaf target sums — subtract as you descend, decide at leaves. Python solution and complexity analysis for the DFS interview pattern.
3 min read
Permutation in String: Fixed Window Frequency Matching
Detect an anagram window in O(n) with an incremental match counter. Python solution and complexity analysis for the sliding window interview pattern.
3 min read
Populating Next Right Pointers in O(1) Space
Wire each node to its right neighbor using the wires you just installed. Python solution and complexity analysis for the BFS interview pattern.
3 min read
Remove Duplicates In Place: The Reader Writer Pointer Trick
Dedupe a sorted array in place with a reader and a writer index. Python solution and complexity analysis for the two pointers interview pattern.
3 min read
Remove Nth Node From End With a Fixed Gap Walk
Delete the n-th from the end in one pass with a dummy head. Python solution and complexity analysis for the fast and slow pointers interview pattern.
3 min read
Reorder List: Three Linked List Primitives in One Question
L0-Ln-L1-Ln-1 interleaving via split, reverse, and merge. Python solution and complexity analysis for the fast and slow pointers interview pattern.
3 min read
Reorganize String: Adjacent Duplicates and Greedy Pairing
No two equal neighbors — alternate the two most frequent letters. Python solution and complexity analysis for the heap and top-k interview pattern.
3 min read
Rotting Oranges: Multi-Source BFS on a Grid
Seed the queue with every rotten orange — simultaneous spread, counted in rounds. Python solution and complexity analysis for the BFS interview pattern.
3 min read
Same Tree: Structural Equality by Parallel DFS
Walk two trees in lockstep — the base-case ordering does the work. Python solution and complexity analysis for the DFS interview pattern.
3 min read
Search a 2D Matrix as One Flattened Sorted Array
One binary search over rows*cols with divmod index mapping. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Search Insert Position and the Lower Bound Idiom
The lower_bound boundary template every variant builds on. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Search in Rotated Sorted Array: One Half Is Always Sorted
The rotated classic — decide which half is sorted, then range-check. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Shortest Path in a Binary Matrix With Eight Directions
Unweighted shortest path — BFS by definition, eight neighbors, mark early. Python solution and complexity analysis for the BFS interview pattern.
3 min read
Sliding Window Maximum With a Monotonic Deque
Window max in O(n) — the monotonic deque, explained properly. Python solution and complexity analysis for the sliding window interview pattern.
3 min read
Sort Characters by Frequency: Heap or Buckets
Rebuild a string most-frequent-first — full ordering, so no bounded trick. Python solution and complexity analysis for the heap and top-k interview pattern.
3 min read
Sort Colors: The Dutch National Flag in One Pass
Three-way partition of 0s, 1s and 2s in one pass, no counting. Python solution and complexity analysis for the two pointers interview pattern.
3 min read
Integer Square Root: Search the Answer Space
First search-on-the-answer: largest k with k*k at most x. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Squares of a Sorted Array Without Sorting Again
Square a sorted array with negatives and stay O(n), no re-sort. Python solution and complexity analysis for the two pointers interview pattern.
3 min read
Summary Ranges: Collapsing Runs Into Interval Strings
Turn a sorted array into a->b range strings — clean run detection. Python solution and complexity analysis for the merge intervals interview pattern.
3 min read
Symmetric Tree: Mirrored Recursion on One Tree
Check mirror symmetry by walking outer-outer and inner-inner pairs. Python solution and complexity analysis for the DFS interview pattern.
3 min read
Task Scheduler: Greedy Frequency Math With a Heap Proof
CPU cooldown scheduling — the frame formula and when idle time vanishes. Python solution and complexity analysis for the heap and top-k interview pattern.
3 min read
3Sum Closest: Tracking the Best Miss With Two Pointers
Nearest triplet sum to a target, converging on the smallest gap. Python solution and complexity analysis for the two pointers interview pattern.
3 min read
3Sum: Sorting Plus Two Pointers, With Duplicate Handling
All unique triplets summing to zero — dedupe without a set of tuples. Python solution and complexity analysis for the two pointers interview pattern.
3 min read
Top K Frequent Elements: Count, Then Choose Your Weapon
Counter plus bounded heap — and the bucket-sort answer that beats it. Python solution and complexity analysis for the heap and top-k interview pattern.
3 min read
Trapping Rain Water With Converging Boundary Maxima
The classic hard: O(1)-space water trapping via boundary maxima. Python solution and complexity analysis for the two pointers interview pattern.
3 min read
Two Sum on a Sorted Array: The Two Pointers Opener
Find a pair summing to target in one pass and O(1) space. Python solution and complexity analysis for the two pointers interview pattern.
3 min read
Unique Paths: Grid DP and the Rolling Row
Paths through a lattice — 2D recurrence, 1D memory. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Valid Palindrome II: One Deletion, Two Branches
Palindrome check with one allowed deletion — branch only on mismatch. Python solution and complexity analysis for the two pointers interview pattern.
3 min read
Valid Palindrome: Clean Two Pointer String Scanning
Check a messy string is a palindrome without building a filtered copy. Python solution and complexity analysis for the two pointers interview pattern.
3 min read
Validate Binary Search Tree With Shrinking Bounds
The local-check trap, defeated by passing (low, high) down the tree. Python solution and complexity analysis for the DFS interview pattern.
3 min read
Word Break: Segmentation as Reachability DP
Can the string be segmented? Prefix reachability with a set lookup. Python solution and complexity analysis for the dynamic programming interview pattern.
3 min read
Word Ladder: BFS Over an Implicit Word Graph
Shortest transformation via wildcard buckets, not pairwise comparison. Python solution and complexity analysis for the BFS interview pattern.