16 Essential Problem-Solving Patterns

The page presents 16 data structures and algorithms patterns as a way to solve problems efficiently. It groups them with use cases and short Java examples, covering arrays, strings, linked lists, trees, heaps, dynamic programming, and graph traversal.

Reading notes

#

• Sliding window is used to track a subset of data that shifts over time, with maximum subarray sum as the example.
• Two pointers move from different ends of an array to find pairs, such as two numbers that sum to a target.
• Fast and slow pointers are used to detect cycles in sequences, especially in linked lists.
• Merge intervals combines overlapping intervals and is presented with meeting scheduling as a use case.
• Cyclic sort is used when numbers fall within a fixed range, and the example is finding a missing number from 1 to N.
• In-place reversal of a linked list is shown as a way to reverse a list without extra storage.
• Breadth-first search in a tree explores nodes level by level and is used for level-order traversal.
• Depth-first search explores a branch as deep as possible before backtracking and is used to find root-to-leaf paths.
• The two-heap pattern maintains a dynamic dataset and is used to find the median of a stream.
• The subsets pattern generates all possible subsets and is linked to combination and permutation problems.
• Modified binary search is used in rotated or partially sorted arrays to find a target element.
• Bitwise XOR solves pair-based problems and is used to find a single number in an array.
• The top K elements pattern uses heaps to find the most frequent elements in a dataset.
• K-way merge combines multiple sorted arrays efficiently and is used for merging K sorted linked lists.
• The 0/1 knapsack dynamic programming pattern optimizes selection under constraints and is used for resource allocation.
• Topological sort finds a valid task order in DAGs and is used for course scheduling.