Data Structures and Algorithms - Complete Course

Explore how to analyze an algorithm's running time using best, worst, and average cases, and learn asymptotic notation and input-size effects with practical examples like quicksort.

Learn how big theta notation provides a tight bound for running time by bounding f(n) between c1 g(n) and c2 g(n), and apply this to time and space analysis.

Learn to build an array from a permutation by computing output[i] = nums[nums[i]] for a zero-based permutation, with time and space complexity insights.

Explore the differences between static and dynamic arrays, compare time complexity of operations, and learn how dynamic arrays resize by doubling capacity in C++, with insert and update.

Explore the linked list as a data structure of nodes with data and a next pointer, a non-contiguous chain whose traversal starts at the head and proceeds node by node.

Explore the advantages of linked lists, including dynamic growth and easy insertion and deletion via next pointers. Contrast this with arrays by noting linear access time and non-contiguous memory storage.

Represent and traverse a linked list across C++, Java, and Python by defining a node with data and a next pointer, creating a three-node list, and traversing to print values.

Explore linked list insertion in three cases: beginning, end, and middle, illustrating pointer updates, time complexity, and corresponding code in C++.

Learn how to delete nodes in a linked list, including deleting the head, deleting the tail, and removing a node by value, with pointer updates.

Detect a loop in a linked list using a two-pointer method with slow and fast pointers, which meet inside the cycle, and contrast with a map-based approach that uses space.

This lecture shows building a simple binary tree in C++, creating nodes with left and right pointers, initializing values via constructor and initialization list, and printing the tree structure.

Explore tree traversals including inorder, preorder, postorder, and level order traversal. Compare recursive and brute-force approaches to visiting left and right subtrees and root nodes.

Explore the stack data structure through a real-life plate analogy, showing last in, first out behavior, push and pop operations, top queries, empty checks, and array-based implementation concepts.

Introduce graphs as a foundational data structure of nodes and edges. Explore directed and undirected types, regular and complete graphs, connectivity, bipartite and planar cases, and common representations.

Explore breadth-first search, a graph traversal that uses a queue to visit each vertex level by level. Start from a source, mark visited, and enqueue unvisited neighbors.

Explore iterative depth-first search using a stack to traverse a graph, compare it to recursion, visit unvisited neighbors, backtrack, and cover all components.

Use a dfs-based cycle detection in directed graphs by tracking discovery and finish times and the recursion stack to spot back edges that form cycles across components.

Explore the disjoint set (union-find) data structure and its two core operations, union and find. See how representatives and a parent array organize non overlapping sets, from naive to optimized.

Explore hash tables as data structures that support insertion and search, and learn how hash sets store unique values while hash maps store key-value pairs with unique keys.

Design a hash table by selecting a hash function that distributes keys across buckets and implementing collision resolution to handle multiple keys per bucket and manage load factor.

Design a hash map as an associative data type, map keys to indices, resolve collisions with chaining, and implement get, put, and remove in C++, Python, and Java.

Analyze hash tables by evaluating space complexity with M keys and buckets, and discuss trade-offs between insert and search, comparing linear storage to a balanced search tree with O(log n).

Master recursion basics for programming interviews, including base cases and recursive relationships. Practice breaking problems into smaller subproblems with examples like factorial, fibonacci, grid problems, and memorisation.

Traverse from the root to sum left leaves in a binary tree, using a left child flag to add only leaves that are left children.