Check if an array represents a min-heap or not
Given an integer array, check if it represents min-heap or not. For example, the first array represents a min-heap, but the second array doesn’t violate the heap property.
Tag: Medium
Heap Sort Algorithm – Overview & C, C++, Java, and Python Implementation
Heapsort is an in-place, comparison-based sorting algorithm and can be thought of as an improved selection sort as it divides the input into a sorted and an unsorted region.
Job Sequencing Problem with Deadlines
Given a set of tasks with deadlines and total profit earned on completing a task, find maximum profit earned by executing the tasks within the specified deadlines. Assume that a task takes one unit of time to execute, and it can’t execute beyond its deadline. Also, only a single task will be executed at a time.
Graph Coloring Problem
Graph coloring (also called vertex coloring) is a way of coloring a graph’s vertices such that no two adjacent vertices share the same color. This post will discuss a greedy algorithm for graph coloring and minimize the total number of colors used.
Single-Source Shortest Paths – Bellman–Ford Algorithm
Given a source vertex s from a set of vertices V in a weighted graph where its edge weights w(u, v) can be negative, find the shortest path weights d(s, v) from source s for all vertices v present in the graph. If the graph contains a negative-weight cycle, report it.
Single-Source Shortest Paths – Dijkstra’s Algorithm
Given a source vertex s from a set of vertices V in a weighted graph where all its edge weights w(u, v) are non-negative, find the shortest path weights d(s, v) from source s for all vertices v present in the graph.
Union–Find Algorithm for cycle detection in a graph
Given an undirected connected graph, check if it contains any cycle or not using the union–find algorithm.
Disjoint–Set Data Structure (Union–Find Algorithm)
This post explains the working of disjoint-set data structure (also called union find data structure). A disjoint-set is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
Check if a digraph is a DAG (Directed Acyclic Graph) or not
Given a directed graph, check if it is a DAG (Directed Acyclic Graph) or not. A DAG is a digraph (directed graph) that contains no cycles.
Determine whether an undirected graph is a tree (Acyclic Connected Graph)
Given an undirected graph, check if it is a tree or not. In other words, check if a given undirected graph is an Acyclic Connected Graph or not.
Total paths in a digraph from a given source to a destination having exactly `m` edges
Given a digraph (directed graph), find the total number of routes to reach the destination from a given source with exactly m edges.
Check if an undirected graph contains a cycle or not
Given a connected undirected graph, find if it contains any cycle or not. For example, the following graph contains a cycle 2–5–10–6–2.