Data structures and algorithms, by pattern

How to use this

• How this course works4 min
• The solving loop4 min
• Complexity by counting4 min

One pass

• One pass with state6 min
• The scrap copper spreadeasy3 min
• Reaching the last swap stationmedium3 min
• Glasshouse spreadeasy3 min
• The rotunda shiftmedium3 min
• Empty pockets to the taileasy3 min

Prefix and suffix

• Prefix and suffix arrays6 min
• Bypassing a gear stagemedium3 min
• Reservoir ledgereasy3 min
• The bracket under the shelfeasy3 min

The predicate

• The predicate, not the array6 min
• Getting the boundaries right7 min
• High watereasy3 min
• First bag on the beltmedium3 min
• Reading the balloon backhard3 min
• Dialling in the data capmedium3 min
• The autoclave loadmedium3 min
• Finding the accessioneasy3 min
• Seed tray footprinthard3 min
• First red buildeasy3 min

Search space design

• Searching the answer, not the array7 min
• Overnight restockmedium4 min
• Toll plaza minutemedium3 min
• Wrapped flight recordermedium3 min
• Kiln shelf sizemedium3 min
• Sprinkler squarehard3 min
• Bindery day quotamedium4 min
• Staircase price boardmedium3 min

Two pointers

• Two pointers6 min
• Micron drifteasy4 min
• Crate diggingeasy4 min
• Hull trimmedium4 min
• Shortest soakmedium3 min
• No repeats on airmedium3 min
• Cones on the loommedium3 min
• Glaze runmedium3 min

Sliding windows

• The sliding window6 min
• At most k, and exactly k7 min
• Shared sightingseasy3 min
• Ribbon pairseasy3 min
• Bracelet from the beltmedium3 min
• Exactly k stopshard3 min
• Two-ink runmedium3 min
• Sprint intervalsmedium3 min
• Two cuts on the cone rodhard4 min

Order as a key

• Order as a key7 min
• Booth changeover runeasy3 min
• Festival jury ballotsmedium3 min
• Rehearsal room clashesmedium3 min
• Roadworks calendarmedium4 min
• Timber stack tippingmedium3 min
• Spectrum licence ledgerhard4 min

Intervals

• Sweeping intervals6 min
• Letterpress trayeasy4 min
• Trailhead campsiteseasy4 min
• Telescope nighteasy4 min
• Consecutive van runsmedium4 min
• Village hall chargershard4 min

Counting sorts

• Sorting without comparisons7 min
• Fairground scoreboardmedium3 min
• Irrigation windowsmedium4 min
• Kiln slotsmedium4 min
• Mosaic diagonalseasy3 min
• Lane bookingshard4 min
• Sorting office binseasy4 min

Hash maps

• What a hash map buys you7 min
• Beam through the swarmhard3 min
• Settlement blocksmedium4 min
• Greenhouse ventsmedium3 min
• Bracket through the archivemedium3 min
• The badge scanned onceeasy3 min
• Matched pledgeseasy3 min

Ordered structures

• When you need order too7 min
• Rain tank swingsmedium3 min
• Clock drift readouthard3 min
• Reserve turnstilemedium3 min
• Wristband tallymedium3 min
• Stamp album runmedium3 min
• Interfering channelseasy3 min

Linked lists

• Pointer surgery7 min
• Turning the rope teameasy4 min
• Sluice gate loopmedium4 min
• One shelving runeasy4 min
• Trimming the playoutmedium4 min

Stacks and queues

• Stacks and monotonic stacks6 min
• Queues and amortised cost6 min
• Two dead-end sidingsmedium3 min
• The next lot to beat itmedium4 min
• Banner across the siloshard4 min
• Waiting for a stronger gustmedium3 min

Data-structure design

• Designing a data structure6 min
• Even dye lotshard3 min
• Lightest bag in the towereasy3 min
• Rollout rewindmedium3 min
• The seed swap drummedium3 min
• The callsign registermedium3 min
• The front displaymedium3 min

The framework

• The recursion framework7 min
• Tasting flighteasy3 min
• Rooftop sweepmedium3 min
• Pipette dosesmedium3 min
• Mirror panelsmedium3 min
• Resurfacing the rinkhard3 min
• Recall maskhard3 min
• Greenhouse rotationhard4 min
• Gallery sweepmedium4 min
• Dig site tileshard4 min
• Drill rostereasy4 min

Backtracking

• Backtracking5 min
• Pruning7 min
• Donation hampersmedium3 min
• Carillon pealsmedium3 min
• Spending the vouchermedium3 min
• Tracing the mosaicmedium4 min
• Bead kit braceletseasy3 min
• Matching the moisture loghard4 min
• Whole-turn gearingmedium4 min
• Glare-free floodlightshard4 min
• The festival ledgermedium4 min

Heaps

• The heap invariant7 min
• Top-k and two heaps7 min
• The k lightest crateseasy3 min
• Stitching the station logsmedium3 min
• The board shows the medianhard4 min
• The card catalogue mergehard3 min
• The nth bell in the pattern bookmedium3 min
• The nearest drill bits in the cataloguemedium4 min
• Screen-print rotationmedium3 min
• Tug-of-war laddereasy3 min
• Back-to-back on airmedium3 min

Traversal

• Traversal families6 min
• Break-even on the market runmedium4 min
• Bringing the grid backeasy4 min
• Two pedigree cardseasy4 min
• The permit linehard4 min
• Walking the housemedium3 min
• Sealing the wind chestmedium4 min
• Kth wheel to ripenmedium4 min

Structure and paths

• Structure and paths5 min
• The bracket, first round firsteasy4 min
• Parterre mirroreasy4 min
• The best repeater runhard4 min
• Counting clearance chartsmedium4 min
• A run with exactly the verticaleasy4 min
• The same unit, already theremedium4 min
• Upstream of botheasy4 min

BSTs

• The BST invariant7 min
• Canopy walkway checkmedium4 min
• Rehanging the mobileeasy4 min
• The shared startermedium4 min
• The pasted slipseasy4 min
• Call-out roundseasy4 min
• Refiling the drawer cabinetmedium4 min

Tries

• Tries7 min
• Filling the gridmedium4 min
• The shade charthard4 min
• The dispatch consolehard4 min

String algorithms

• Palindromes6 min
• KMP and the failure function5 min
• One tray per formulamedium3 min
• The marquee swapeasy3 min
• Fly-rail cue sheeteasy3 min
• The sundial mottoeasy3 min
• The leaded stripmedium3 min
• Mirrored fillsmedium3 min
• One wire, many labelsmedium3 min
• Tremor signaturemedium4 min
• Mirrored avenuehard4 min
• Motif on the rollmedium4 min
• Turnstile audithard3 min
• The permissions deskmedium3 min

Linear DP

• What DP actually is6 min
• Linear DP6 min
• The roofline runhard3 min
• The hive scaleeasy3 min
• Teeth on the wheelsmedium3 min
• Zigzag bordermedium3 min
• Crossing the pontoonseasy3 min
• The clean round bonusmedium3 min
• Starting the ridge relayhard4 min
• Loudest run on the boardmedium3 min
• Posts on an even gradeeasy3 min
• The fly cue sheetmedium3 min
• Terrace climbseasy3 min
• One struck readingmedium4 min
• Tints in the stair windowmedium3 min
• Booking the soundstageseasy3 min
• Pitches round the market ringmedium3 min
• The jukebox slipmedium4 min
• The blurred count cardhard4 min
• Copper at the weighbridgemedium4 min
• The clearing daymedium3 min

Subsequences and strings

• Two sequences5 min
• The rising traversemedium3 min
• The period in a sighting ledgermedium3 min
• Two hydrophonesmedium3 min
• Blends off the blottermedium3 min
• The seed tray laddermedium3 min
• Reading the punch tapemedium4 min
• Marquee changeoverhard4 min
• The bead strand mirrormedium4 min
• Motif in the weavehard4 min
• Readings of the friezehard4 min

Knapsack

• The knapsack family5 min
• Counterweight rigmedium3 min
• The jackpot signhard4 min
• Chop on the river gaugeeasy4 min
• Burns and ventsmedium3 min
• Sluice dosesmedium4 min

Interval and matrix

• Intervals and matrices6 min
• Two trips through the stackshard4 min
• Quilt of squareshard3 min
• Splitting the ripening shelfmedium3 min
• Head of the chutehard3 min
• Two crews, one sidingmedium4 min
• Paying by the traymedium4 min
• The lantern wirehard4 min
• Joints in the kiln lininghard3 min
• Down the lock gridmedium4 min
• Squares in the mosaicmedium4 min
• Height off the winchhard4 min

Tree, digit and bitmask

• Tree, digit and bitmask DP7 min
• Wax pourshard4 min
• Setting the folioshard4 min
• The searchable sectionhard4 min
• The pier tickerhard4 min
• Stamping the key blanksmedium4 min
• The espalier weavemedium4 min
• Loading the glaze shedhard3 min
• Cutting the parcel spurmedium4 min
• The storm-drain surveymedium3 min
• Standing the pipe rankhard4 min
• The broken dialhard4 min
• Bays the reader flagshard4 min

Greedy

• The exchange argument6 min
• Part-loads of loose teamedium3 min
• Rosettes on the benchmedium3 min
• The single enlargereasy3 min
• The wind tunnel diaryhard3 min
• Gritting the passhard3 min
• Water for the whole ringmedium4 min

Traversal and connectivity

• Representing a graph5 min
• BFS and DFS5 min
• What is left of the sheeteasy3 min
• Air pockets in the castingmedium3 min
• Lichen on the north wallmedium3 min
• Shunting to an exiteasy3 min
• Paper by the reammedium3 min
• Handing out the allotmentshard3 min
• The cold store keyringeasy4 min
• Two cabinetsmedium3 min
• Sheep that cannot straymedium3 min
• Repainting the lido mosaiceasy3 min

Cycles and ordering

• Cycles and topological order6 min
• The slipway job cardsmedium3 min
• Reassembling the tower clockmedium3 min
• Tracks that come to restmedium3 min
• Dye house shade indexhard3 min
• The tunnel to sealmedium3 min
• The branch van rotahard3 min
• Conservation precedencemedium4 min
• One call line too manyhard4 min
• Winters on the cutmedium3 min

Shortest paths

• Shortest paths6 min
• The nearest standpipemedium3 min
• The longest swimmedium3 min
• Word from the fire towersmedium3 min
• Recutting the master keyhard3 min
• Opening the head sluicemedium4 min
• Every shortest call-sign runhard3 min
• Crossing the mudflatsmedium3 min
• The backload ledgermedium3 min
• Blue mould on the benchmedium3 min
• Turning the alleys roundmedium3 min
• The transfer ticketmedium3 min
• The quietest refugemedium3 min
• Routing the containermedium3 min

Union-find and components

• Union-find5 min
• Merging the choir rostermedium3 min
• Wings of the one-way househard3 min
• Repatching the rigmedium3 min
• The pneumatic posthard3 min
• The mill floor loadmedium3 min
• The largest slab in the quarrymedium3 min
• The trunk line surveyeasy3 min
• The cask ledgermedium3 min
• Striking the scaffold tiesmedium3 min