Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer

This section lays the foundation by defining what data structures are: methods for organizing data efficiently for quick access, querying, and updating. It highlights their importance in creating fast algorithms, managing data, and producing cleaner code. The concept of Abstract Data Types (ADTs) is introduced as an abstraction of data structures, defining an interface without specifying implementation details. Examples include lists, queues, and maps, which can have various underlying data structure implementations.

This part delves into computational complexity, focusing on Big O notation. It explains how Big O is used to standardize the discussion of time and space requirements for algorithms, particularly in worst-case scenarios and for arbitrarily large inputs. Various common Big O complexities are introduced (constant, logarithmic, linear, quadratic, cubic, exponential, factorial) along with their properties, such as ignoring constants and multiplicative factors.

The discussion shifts to arrays, emphasizing their fundamental role as building blocks for other data structures. Static arrays are defined as fixed-length, indexable, contiguous memory blocks. Their ubiquitous use in programming is highlighted, including for temporary storage, buffers, lookup tables, and dynamic programming. The concept of dynamic arrays, which can grow and shrink, is introduced, along with their implementation using static arrays and the associated time complexities for operations like access, searching, insertion, and deletion.

This segment introduces linked lists as sequential lists of nodes, where each node holds data and points to the next. The distinction between singly linked lists (pointer to next node only) and doubly linked lists (pointers to both next and previous nodes) is explained. Common uses include implementing abstract data types like lists, stacks, and queues, as well as modeling real-world objects. The pros and cons of each type (memory usage, traversal ease) are discussed, along with detailed examples of insertion and removal operations.

Stacks are introduced as a one-ended linear data structure following the Last-In, First-Out (LIFO) principle, with primary operations being push (add to top) and pop (remove from top). Their widespread use is illustrated with examples like text editors, browser navigation, compiler brace checking, and recursion support in programming. Complexity analysis shows constant time for push, pop, and peek, while searching is linear. A practical problem of checking bracket sequences is solved using a stack, and its relation to the Tower of Hanoi puzzle is explored.

Queues are presented as a linear data structure modeling real-world queues, following the First-In, First-Out (FIFO) principle. Key operations include enqueue (add to back) and dequeue (remove from front). Various terms for these operations are clarified. Practical applications range from modeling waiting lines to server management and graph breadth-first search (BFS) traversal. Enqueue and dequeue are constant time operations, while searching and internal element removal are linear.

This section introduces priority queues as abstract data types where elements have priorities, and higher-priority elements are dequeued first. The video clarifies that priority queues require comparable elements. The concept of a heap is introduced as the canonical underlying data structure for priority queues, satisfying the heap invariant (parent node value is ordered relative to children). Min-heaps and Max-heaps are explained, along with their array representation for efficient access to parent/child nodes. Common applications in algorithms like Dijkstra's and Prim's are highlighted, and the time complexities for various operations on a binary heap (construction, pull, peek, add, remove, containment) are analyzed, including optimization using hash tables.

The Union-Find (or Disjoint Set) data structure is introduced as a mechanism for tracking elements partitioned into disjoint sets. Its two primary operations are 'find' (determining an element's group) and 'union' (merging two groups). The magnet analogy is used to illustrate these concepts. Applications include Kruskal's minimum spanning tree algorithm, grid percolation, network connectivity, and other advanced problems. The excellent amortized constant time complexity of its operations (find, union, get component) is emphasized.

This part provides a crash course on trees, defining them as connected and acyclic undirected graphs with specific properties (N nodes, N-1 edges; single path between any two vertices). Key terminology like rooted tree, child/parent nodes, leaf nodes, and subtrees are explained. Binary trees are defined as trees where every node has at most two children. Binary Search Trees (BSTs) are introduced as binary trees that satisfy the BST invariant: left subtrees have smaller elements, and right subtrees have larger elements. Their uses in sets, maps, heaps, and syntax trees are discussed. The average-case logarithmic time complexity of BSTs is highlighted, along with the worst-case linear degradation for unbalanced trees.

Hash tables are presented as a fundamental data structure for mapping keys to values using hashing. The concept of a hash function (mapping keys to integers within a fixed range) is explained, emphasizing important properties like determinism and uniformity. Collision resolution techniques are introduced, specifically focusing on separate chaining (using auxiliary data structures like linked lists to handle collisions) and open addressing (probing for other slots within the main array). The typically constant-time average complexity of hash table operations (insertion, removal, search) is stressed, along with the potential for linear time with poor hash functions.

The Fenwick tree, also known as the Binary Indexed Tree, is introduced as a powerful and efficient data structure for range queries and point updates on arrays. Its motivation is explained by contrasting it with naive array summing and prefix sum arrays, highlighting Fenwick tree's logarithmic time for both updates and queries while maintaining linear construction. The core concept of 'least significant bit' determining a cell's responsibility range is detailed, along with the cascading up/down mechanism for prefix sums and point updates using bit manipulation for efficiency. The linear time construction algorithm is also covered.

This section introduces suffix arrays as an efficient data structure for string processing, storing the sorted indices of all suffixes of a string. It's presented as a space-efficient alternative to suffix trees. The Longest Common Prefix (LCP) array is then detailed as a companion to the suffix array, storing the number of shared characters between adjacent sorted suffixes. Examples illustrate LCP array construction. An application of these data structures in finding and counting unique substrings is demonstrated, connecting the sum of LCP values to duplicate substrings.

The K-common substring problem (finding the longest common substring shared by at least K strings) is explored using suffix arrays and LCP arrays. The approach involves concatenating strings with unique sentinel values, constructing a suffix array for the combined text, and then employing a sliding window technique. This window identifies a range of suffixes containing at least K distinct string colors. The minimum LCP value within this valid window is then queried to find potential longest common substrings. The linear amount of windows to consider makes this approach efficient.

The longest repeated substring problem is tackled using suffix arrays and LCP arrays. The solution relies on finding the maximum value in the LCP array, as this indicates the longest common prefix between two adjacent sorted suffixes, which implies a repeated substring. Examples illustrate how to identify such substrings, noting that multiple longest repeated substrings can exist if there are ties in LCP values.

Balanced Binary Search Trees (BSTs) are introduced as self-adjusting trees that maintain a logarithmic height, ensuring all operations (insertion, deletion, search) remain fast in the worst case, unlike regular BSTs that can degrade to linear performance. The core concept of tree rotations (right and left rotations) is detailed as the mechanism for rebalancing, explaining how they preserve the BST invariant while changing structural balance. The AVL tree, as the first discovered balanced BST, is highlighted, focusing on its balance factor invariant (height difference of subtrees being -1, 0, or +1).

The indexed priority queue is introduced as a powerful variant of the traditional priority queue, supporting quick updates and deletions of key-value pairs. Its utility is illustrated with a hospital patient prioritization example where priorities dynamically change. The concept of mapping keys to unique integer indices for efficient heap-based implementation is central. The internal structure of an indexed priority queue is detailed, including the use of a position map (key index to heap node index) and an inverse map (heap node index to key index) to enable constant-time lookups for key positions. Insertion, polling (removing the root), and specific key removal operations are explained, emphasizing how these maps facilitate logarithmic time complexity by avoiding linear scans.