Data Structures and Algorithms
67 of my solutions to LeetCode problems and graph algorithm exercises, from my GitHub repository. Each one runs here, as written, on an example, and you can step through what it reads and changes as it goes.
Graphs9
Graph Algorithms
Connected Components Count
Counts the separate pieces of an undirected graph, exploring each piece once from the first node of it not yet seen.
Graph Algorithms
Depth-First and Breadth-First Print
Prints every node reachable from a source, three ways: depth first with a stack, depth first by recursion, and breadth first with a queue.
Graph Algorithms
Has Path (Directed Acyclic Graph)
Whether one node can reach another along a directed graph's edges, searched depth first by recursion or breadth first with a queue.
Graph Algorithms
Largest Component
The number of nodes in an undirected graph's biggest connected piece, sizing each piece as it's explored.
Graph Algorithms
Shortest Path
The fewest edges between two nodes of an undirected graph given as a list of edges, found breadth first.
Graph Algorithms
Undirected Path
Whether two nodes of an undirected graph, given as a list of edges, are connected, keeping track of visited nodes so cycles can't loop forever.
LeetCode 797
All Paths From Source to Target
Every path from the first node to the last of a directed acyclic graph, grown breadth first from a queue of partial paths.
LeetCode 1791
Find Center of Star Graph
The node a star graph's edges all share: whichever of the first edge's ends is also in the second, then checked against the rest.
LeetCode 997
Find the Town Judge
The one person everyone else trusts and who trusts no one, by scoring each trust: one down for who gives it, one up for who gets it.
Grids7
Graph Algorithms
Island Count
How many islands of land a grid of land and water holds, sinking each into a visited set as it's explored up, down, left and right.
Graph Algorithms
Minimum Island
The size of a grid's smallest island, measuring each as it's explored and keeping the least.
LeetCode 994
Rotting Oranges
How many minutes until every orange's rotten, as rot spreads each minute to fresh neighbours, or -1 if some never rot.
LeetCode 79
Word Search
Whether a word can be spelled along a path of neighbouring letters, searched depth first, each letter blanked while it's in use and put back after.
LeetCode 36
Valid Sudoku
Whether a partly filled sudoku breaks no rule so far: no digit twice in a row, then in a column, then in a 3 × 3 box.
LeetCode 48
Rotate Image
Turns a square matrix a quarter turn clockwise in place: flipped across its diagonal, then each row reversed.
LeetCode 1672
Richest Customer Wealth
The largest total of any customer's bank accounts, each row a customer.
Trees13
LeetCode 100
Same Tree
Whether two binary trees match in shape and values, compared node by node, recursively.
LeetCode 101
Symmetric Tree
Whether a binary tree is its own mirror image, comparing each left node with its mirror on the right.
LeetCode 104
Maximum Depth of Binary Tree
How many levels a binary tree has: one more than the deeper of its two subtrees.
LeetCode 108
Convert Sorted Array to Binary Search Tree
Builds a height-balanced binary search tree from a sorted array, rooting each subtree at the middle of its range.
LeetCode 235
Lowest Common Ancestor of a Binary Search Tree
The deepest node with both of two nodes beneath it: in a search tree, the first where they fall on different sides.
LeetCode 257
Binary Tree Paths
Every path from the root down to a leaf, written out as values joined by arrows.
LeetCode 501
Find Mode in Binary Search Tree
The most frequent values in a binary search tree, counted in a dictionary as the tree's walked.
LeetCode 559
Maximum Depth of N-ary Tree
How many levels a tree with any number of children has, keeping the deepest level reached as it's walked.
LeetCode 617
Merge Two Binary Trees
Overlays one binary tree on another, summing the values where both have a node and keeping whichever node's there where only one does.
LeetCode 637
Average of Levels in Binary Tree
The average value on each level of a binary tree, a level at a time, breadth first.
LeetCode 654
Maximum Binary Tree
Builds a tree rooted at an array's largest value, its left subtree built the same way from what's before it and its right from what's after.
LeetCode 701
Insert into a Binary Search Tree
Adds a value to a binary search tree as a new leaf, going left or right at each node until there's a gap.
LeetCode 938
Range Sum of BST
The sum of a binary search tree's values that fall between a low and a high, carried through the recursion.
Linked lists4
LeetCode 83
Remove Duplicates from Sorted List
Drops repeated values from a sorted linked list by linking each node past any next node with the same value.
LeetCode 141
Linked List Cycle
Whether a linked list loops back on itself, found with a slow pointer and a fast one that catches it up only if it does.
LeetCode 206
Reverse Linked List
Reverses a linked list in one pass, turning each node's link back to the node before it.
LeetCode 237
Delete Node in a Linked List
Removes a node given only that node: it takes on the next node's value, then links past it.
Arrays16
LeetCode 1
Two Sum
The positions of the two numbers that add up to a target, in one pass, remembering each number seen and looking up its complement.
Blind 75 · LeetCode 1
Two Sum (Blind 75)
Two Sum again, written fresh for the Blind 75 list: the same one-pass lookup of each number's complement.
LeetCode 11
Container With Most Water
The most water two lines can hold, closing in from both ends and always moving the shorter line.
LeetCode 27
Remove Element
Removes every copy of a value from an array in place, splicing each out, and returns how many are left.
LeetCode 66
Plus One
Adds one to a number stored as an array of digits, carrying from the last digit as far as it needs to.
LeetCode 136
Single Number
The one number without a pair, found by XOR-ing them all together, as each pair cancels itself out.
LeetCode 198
House Robber
The most that can be taken from a row of houses without taking from two side by side, built up house by house (dynamic programming).
LeetCode 581
Shortest Unsorted Continuous Subarray
The length of the shortest stretch that, sorted, sorts the whole array: bounded by the smallest and largest values out of order.
LeetCode 674
Longest Continuous Increasing Subsequence
The longest run of strictly increasing numbers, starting a new run wherever one stops rising.
LeetCode 908
Smallest Range I
The least gap between largest and smallest after moving each number by up to k: the range less 2k, or none.
LeetCode 1089
Duplicate Zeros
Doubles every zero in place, shifting the rest right and dropping whatever falls off the end.
LeetCode 1200
Minimum Absolute Difference
Every pair of numbers with the smallest difference between them, found side by side once the array's sorted.
LeetCode 1207
Unique Number of Occurrences
Whether every value turns up a different number of times, its counts dropped into a set to see if any repeat.
LeetCode 1480
Running Sum of 1d Array
Each number replaced, in place, by the total of it and everything before it.
LeetCode 1920
Build Array from Permutation
A new array where each place i holds nums[nums[i]].
LeetCode 1929
Concatenation of Array
The array twice over, both copies filled in the same pass.
Strings11
LeetCode 5
Longest Palindromic Substring
The longest stretch that reads the same both ways, expanding out from every letter and every gap between letters.
LeetCode 8
String to Integer (atoi)
Reads a whole number from the start of a string, as C's atoi does: spaces skipped, an optional sign, digits until anything else, clamped to 32 bits.
LeetCode 13
Roman to Integer
A Roman numeral's value, adding each letter and, where a smaller letter came before a bigger one, taking it back off twice.
LeetCode 14
Longest Common Prefix
The longest start every word shares, trimming the first word's letters until each word begins with it.
LeetCode 20
Valid Parentheses
Whether every bracket closes in the right order, pushing openers onto a stack and popping one for each matching closer.
LeetCode 58
Length of Last Word
How long the last word is, once trailing spaces are trimmed and the rest split into words.
LeetCode 242
Valid Anagram
Whether two words use exactly the same letters: counted up through the first, back down through the second.
LeetCode 720
Longest Word in Dictionary
The longest word that can be built a letter at a time from other words in the list, checked in sorted order.
LeetCode 771
Jewels and Stones
How many stones are jewels, with the jewel types in a dictionary for quick lookups.
LeetCode 1108
Defanging an IP Address
Swaps every "." in an address for "[.]", two ways: split and join, or a character at a time from scratch.
LeetCode 1189
Maximum Number of Balloons
How many times "balloon" can be spelled from a text's letters, by the scarcest letter, l and o counting half.
Numbers5
LeetCode 7
Reverse Integer
A number's digits in reverse, sign kept, or 0 if that won't fit in 32 bits.
LeetCode 9
Palindrome Number
Whether a number reads the same both ways, its digits compared from both ends inward.
LeetCode 12
Integer to Roman
A number as a Roman numeral, taking as many of each numeral as fit, largest first, subtractive pairs like CM included.
LeetCode 367
Valid Perfect Square
Whether a number is some whole number squared, without a square root: halving a guess until it's low enough, then counting up.
LeetCode 1103
Distribute Candies to People
Hands out candies one more each time, round and round a line of people, the last getting what's left.