All notes, in reading order - Page 72

Partition Labels

Partition a string into as many parts as possible so each letter appears in one part, using last-occurrence indices and an expanding window, in O(n) t...

Data Structures

Sort Colors (Dutch National Flag Two Pointer)

Sort an array of 0s, 1s, and 2s in a single pass using the Dutch National Flag three pointer technique, in O(n) time and O(1) space.

Data Structures

Remove Duplicates from Sorted Array II

Remove duplicates from a sorted array so each value appears at most twice, in place using the slow/fast two pointer pattern, in O(n) time.

Data Structures

Linked List Cycle Detection (Fast and Slow Pointers)

Detect a cycle in a linked list using Floyd’s fast and slow pointer algorithm, in O(n) time and O(1) space.

Data Structures

Middle of the Linked List

Find the middle node of a linked list in one pass using fast and slow pointers, in O(n) time and O(1) space.

Data Structures

Palindrome Linked List Check

Check if a linked list is a palindrome by finding the middle with fast/slow pointers, reversing the second half, and comparing, in O(n) time and O(1)...

Data Structures

Boats to Save People

Find the minimum number of boats to carry people within a weight limit using sorting and two pointers, in O(n log n) time.

Data Structures

Valid Triangle Number

Count triplets that can form a triangle using sorting and two pointers, in O(n^2) time.

Data Structures

Minimum Number of Swaps to Make Sequences Increasing

Find the minimum swaps to make two arrays strictly increasing using a linear dynamic-programming scan over paired positions, in O(n) time.

Data Structures

Sentence Similarity Using Two Pointers

Check if two sentences become equal by inserting one contiguous run of words, using two pointers over the common prefix and suffix, in O(n) time.

Data Structures

Shortest Distance to a Character

Compute the shortest distance from each index to a target character using a two-pass left-then-right scan, in O(n) time.

Data Structures

Interleaving String Check

Check if a string is a valid interleaving of two others using dynamic programming (a naive two pointer greedy fails), in O(m*n) time.