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.

Identify the upper bound of an algorithm's running time with big o notation, focusing on the dominant term and ignoring constants and lower-order terms.

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.

Learn two-dimensional arrays defined by rows and columns, access elements by row and column indices, and initialize a 3x4 grid in C++, Java, and Python, including vector of vectors.

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.

Learn to find the kth node from the end in a singly linked list using two pointers to maintain a gap and return the node or -1 if too short.

Use the two-pointer approach with slow and fast pointers to find the middle node of a linked list, handling odd and even lengths.

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.

Use Floyd's cycle detection to find a loop in a linked list; reset to head and move both until they meet at the loop's start.

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 various binary tree types by distinguishing full, complete, and perfect structures, and examine how balance and height influence efficiency, including degenerate and red-black variants.

Insert a new node into a binary tree using level-order insertion with a queue, filling the leftmost available position at each level.

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.

Compute the range sum in a binary search tree by traversing nodes and adding values within the inclusive range low to high. Use any traversal and accumulate the final sum.

Learn to determine if a root-to-leaf path in a binary tree sums to a target using a recursive traversal, handling leaf cases, subtracting node values, and returning true on success.

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.

Explore the queue data structure, a first-in, first-out structure similar to a line of people, with operations enqueue, dequeue, front access, and empty checks.

Explore the queue container adapter in the C++ STL, a first-in, first-out structure with push and pop, front and back access, and is used in graph search.

Learn how to perform in-order traversal of a binary tree without recursion by using an explicit stack and a current pointer to iteratively visit left, root, and right nodes.

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.

Detect cycles in undirected graphs using depth-first search with a parent tracker and visited checks. Learn how adjacency lists reveal cycles and adapt depth-first search for undirected graphs.

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 the binary heap data structure as a complete binary tree, explaining max heap and min heap properties where a parent's key exceeds or is less than its children.

Merge k sorted linked lists efficiently by using a min-heap priority queue to continually extract the smallest head and push its next node, building a single sorted list.

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.

Understand how a hash table uses a hash function to map keys to bucket ids for insertion and search, reusing the same function to retrieve data and manage collisions.

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.