DOCSEARCHbyAlgolia
Submit Docs

labuladong's Algorithm Notes

website·Indexed 30 days ago

https://labuladong.github.io/algo/

A comprehensive guide to algorithm patterns and data structures, featuring code templates and frameworks for solving LeetCode problems. Topics include Two Pointers, Sliding Window, BFS, Dynamic Programming, Backtracking, Greedy Algorithms, Binary Trees, and Monotonic Stacks, alongside introductions to modern encryption and frontend development.

Tokens
370.3K
Snippets
1.2K
Records
1.9K
Agent score
72%

What's inside labuladong

  1. Overview of Data Structure and Sorting Algorithm Basics

    This foundational module covers the principles, implementations, and application scenarios of essential data structures and sorting algorithms.

    Basic Data Structures: Includes arrays, linked lists, queues, stacks, hash tables, and binary heaps. The focus is on their underlying principles, code implementations, and common variants.

    Advanced Data Structures: Includes graphs, segment trees, Fenwick trees, tries, and union-find structures. The focus is on principles and application scenarios to help developers understand time complexity and feature utilization.

    Sorting Algorithms: The chapter concludes with an explanation of ten different sorting algorithms.

  2. Overview of Graph Data Structures

    A graph is a logical structure consisting of multiple nodes (Vertices) and edges. Unlike N-ary trees, graphs have no restrictions on node connections: nodes can point to each other, forming complex networks without a strict parent-child hierarchy. Graphs are commonly used to model complex problems and serve as the foundation for algorithms such as Bipartite Graph, Topological Sort, Shortest Path (Dijkstra), and Minimum Spanning Tree (Kruskal).

  3. Overview of Priority Queue Application Patterns

    Priority queues (typically implemented via binary heaps) are used for dynamic sorting, where inserted elements automatically maintain a specific order. Common algorithmic problem patterns using priority queues include:

    1. Merging Ordered Sequences: Combining multiple sorted lists or sequences into a single sorted output.
    2. Finding the K-th Largest/Smallest Element: Efficiently tracking the top K elements across one or more sequences without sorting the entire dataset.

  4. Overview of the Monotonic Queue data structure

    A Monotonic Queue is a specialized queue that maintains its elements in a monotonic (increasing or decreasing) order. It is used to solve sliding window problems where you need to track the maximum or minimum value of the window. Unlike a Priority Queue (Binary Heap), which only provides the extreme value and loses the temporal order of insertion, a Monotonic Queue preserves the FIFO order while allowing O(1) access to the window's maximum/minimum value.

  5. Introduction to Huffman Coding

    Huffman coding is a general-purpose lossless compression algorithm that implements an optimal prefix code tree. It achieves high compression rates by assigning shorter binary codes to characters that appear more frequently in the data. To restore the original data, the compressed stream must be accompanied by a code table.

  6. Overview of Union-Find for Dynamic Connectivity

    Union-Find is an algorithm specifically designed to handle 'dynamic connectivity' in a graph. Dynamic connectivity involves managing a set of nodes and performing operations to connect them and query whether specific nodes belong to the same connected component. Connectivity in Union-Find is treated as an equivalence relation, satisfying three properties:

    1. Reflexivity: Node p is connected to itself.
    2. Symmetry: If p is connected to q, then q is connected to p.
    3. Transitivity: If p is connected to q and q is connected to r, then p is connected to r.

  7. Overview of Shell Sort and its relationship to Insertion Sort

    Shell Sort is a direct improvement over Insertion Sort. While Insertion Sort has a time complexity of O(N^2), Shell Sort breaks this limitation by preprocessing the array to increase its local order (making it h-ordered), which significantly reduces the amount of movement required during the final sorting phase.

  8. Overview of Modern Frontend Technology Stack

    Modern frontend development is built on several layers of technology:

    • Foundation: HTML (structure), CSS (style), and JavaScript (behavior).
    • Language Enhancement: TypeScript provides a typed version of JavaScript for better developer experience and safety.
    • Runtime: Node.js allows JavaScript to run on the server for backend development.
    • UI Frameworks: React and Vue manage components and state for complex application building.
    • Full-stack Frameworks: Next.js (for React) and Nuxt.js (for Vue) provide full-stack capabilities, integrating both frontend and backend in a single project.

  9. Overview of Huffman Coding for Data Compression

    Huffman Coding is an optimal encoding algorithm used for lossless data compression. It constructs a binary tree to create variable-length codes for characters. The primary goal is to minimize the Weighted Path Length (WPL) of the tree, which ensures that the total length of the encoded data is as short as possible. By using a binary tree structure, the algorithm ensures that the decoding process for variable-length codes remains unambiguous.

  10. Overview of Graph Data Structure Logic

    A graph is an extension of an N-ary tree structure, logically consisting of vertices (nodes) and edges. Unlike trees, which restrict edges to parent-to-child directions and forbid cycles or sibling links, graphs allow arbitrary connections between nodes, enabling the representation of complex network structures. Graphs are commonly stored using adjacency lists or adjacency matrices.

  11. Overview of Trie (Prefix Tree) data structure

    A Trie (also known as a digital tree or prefix tree) is an extension of the n-ary tree structure specifically optimized for strings. It is used to store keys (always strings) and associated values, providing significant advantages in memory efficiency and prefix-based querying compared to standard HashMaps or TreeMaps.

  12. Overview of Segment Tree data structure

    A Segment Tree is a derivative of the binary tree structure designed to efficiently handle range queries and dynamic modifications of array elements. It allows for querying the aggregate value of any range and performing dynamic updates on any range, both with a time complexity of O(log N), where N is the number of elements in the array.