Graph

Introduction to Graph Data Structures, including nodes, edges, and the course overview.

Overview of various types of graphs: Directed vs Undirected, Weighted vs Unweighted.

Theoretical breakdown of Adjacency Matrix and Adjacency List.

Practical coding implementation of Adjacency Matrix and Adjacency List.

Building the intuition behind graph traversal techniques (DFS and BFS).

Given a directed graph, return the Breadth First Traversal of this graph starting from node 0.

Given a connected undirected graph, return the Depth First Traversal of this graph starting from node 0.

There are n cities. Return the total number of provinces (connected components).

Perform a flood fill on the image starting from the given pixel. (Note: Outputting modified grid to allow exact array validation against testcases).

Return the ordering of courses you should take to finish all courses. If there are multiple valid answers, return any of them.

Given a square chessboard of size N x N, the initial position of a Knight and the position of a target. Find out the minimum steps a Knight will take to reach the target position.

There are n cities numbered from 0 to n - 1 and n - 1 roads. You need to reorient some roads such that each city can visit the city 0. Return the minimum number of edges changed.

Detect whether there is a cycle in an undirected graph. (Introductory concept)

Detect whether there is a cycle in an undirected graph using Depth First Search (DFS).

Detect whether there is a cycle in an undirected graph using Breadth First Search (BFS).

Given a Directed Graph with V vertices and E edges, check whether it contains any cycle or not.

Introduction to identifying safe nodes in a graph. A node is safe if every possible path from it leads to a terminal node (or another safe node) without entering a cycle.

Return an array containing all the safe nodes of a directed graph. The answer should be sorted in ascending order.

You are given a directed graph of n nodes, where each node has at most one outgoing edge. Return the length of the longest cycle. If no cycle exists, return -1.

Introduction to Topological Sort in Directed Acyclic Graphs (DAG). Linear ordering of vertices such that for every directed edge u -> v, vertex u comes before v.

Conceptual explanation of Kahn's Algorithm to efficiently perform topological sorting by tracking the in-degrees of nodes in a Directed Acyclic Graph.

Given a Directed Acyclic Graph (DAG) with V vertices and E edges, find any Topological Sorting of that Graph using Breadth-First Search (Kahn's Algorithm).

Given a Directed Acyclic Graph (DAG), return the topological sort of the graph using Depth First Search (DFS).

Introduction to solving the Course Schedule II problem using Topological Sort.

Return the ordering of courses you should take to finish all courses. If it is impossible to finish all courses (cycle exists), return an empty array.

Conceptual breakdown of finding the largest color value of any valid path in a directed graph. A color value is the max frequency of any color on the path.

Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.

Introduction to visualizing and traversing 2D matrices / grids as graphs using DFS and BFS.

Introduction to the Flood Fill algorithm. Used widely in applications like the 'paint bucket' tool in drawing software.

Perform a flood fill on an image starting from a given pixel modifying it to the specified color. Returns the modified image grid.

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Introduction to the Rotten Oranges problem. Explains the concept of using Multi-source Breadth First Search (BFS) to track the simultaneous spread of rot from multiple starting points.

Implement the multi-source BFS algorithm. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If impossible, return -1.

Conceptual video discussing the logic of finding minimum distance from every house to the nearest well using a 2D matrix.

Return a 2D integer matrix of size n*m detailing the shortest path distance to fetch water from the nearest well (back and forth). Cells with 'N', 'W', and '.' have answer 0. Unreachable 'H' should be -1.

Conceptual video discussing how to find the minimum number of operations required to make all computers in a network connected.

You are given an initial computer network connections. Return the minimum number of times you need to extract and place cables to make all computers connected. If it's not possible, return -1.

An introduction to shortest path algorithms in graphs, establishing the foundation before diving into Dijkstra's Algorithm.

Conceptual explanation of modeling the classic Snakes and Ladders board game as a Graph traversal problem.

Return the least number of moves required to reach the square n^2 on a snakes and ladders board. If it is not possible, return -1.

Conceptual introduction to Dijkstra's Algorithm for finding single-source shortest paths in weighted graphs with non-negative edge weights.

Conceptual video focused on analyzing how Dijkstra's Algorithm works on examples and why it is correct for non-negative weighted graphs.

Given a weighted graph with non-negative weights and a source vertex, return the shortest distance from the source to all vertices.

Conceptual introduction to solving the Path With Minimum Effort problem on a grid, where path cost is defined by the maximum absolute height difference along the path.

Given a grid of heights, return the minimum effort required to travel from the top-left cell to the bottom-right cell. The effort of a path is the maximum absolute difference between consecutive cells on that path.

Conceptual explanation for finding the cheapest flight path from a source to a destination with at most K stops.

Given n cities and flight prices, find the cheapest price from src to dst with up to k stops. Return -1 if no such route exists.

Introduction to the Bellman-Ford Algorithm, detailing why it is necessary to handle graphs with negative weights where Dijkstra's algorithm fails.

Extends the Bellman-Ford algorithm concept to detect negative weight cycles within a directed graph.

Implementation of the Bellman-Ford algorithm to compute shortest paths from a source node, and return [-1] if a negative weight cycle is detected.

Conceptual introduction to the Floyd-Warshall Algorithm for finding all-pairs shortest paths in a directed weighted graph. Discusses how it handles negative weights but no negative cycles.

Implement the Floyd-Warshall algorithm to solve the all-pairs shortest path problem. Update the input adjacency matrix with shortest path distances.

Quick intro to the Disjoint Set Union (DSU) data structure, vital for dynamic connectivity, minimum spanning trees, and group relationships.

Detailed exploration of the naive Union and Find operations to merge graph components and resolve group parents.

Introduction to crucial optimizations for Disjoint Set Union: Path Compression and Union by Rank/Size, bringing time complexity to near constant time.