Problem In this problem, a tree is an undirected graph that is connected and has no cycles. You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph. ...
Problem There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei. You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1. ...
Introduction The Floyd-Warshall algorithm is a classic algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. It’s especially useful for dense graphs and can handle both positive and negative edge weights (though not negative cycles). Algorithm Initialization: Create a distance matrix dist where dist[i][j] is the initial weight of the edge from vertex i to vertex j, or infinity if no edge exists. Set dist[i][i] = 0 for all vertices i. Dynamic Programming Update: For each intermediate vertex k, update the distance matrix to consider paths that pass through vertex k. For each pair of vertices (i, j), compute if a shorter path exists by going through k: if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } Result: After processing all vertices, dist[i][j] will contain the shortest path distance from vertex i to vertex j. Pseudocode function floydWarshall(graph): dist = matrix of size VxV, initially filled with graph weights (or infinity if no edge exists) for each vertex v: dist[v][v] = 0 for each intermediate vertex k: for each source vertex i: for each destination vertex j: if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist ...
Problem Suppose you are given a table of currency exchange rates, represented as a 2D array. Determine whether there is a possible arbitrage: that is, whether there is some sequence of trades you can make, starting with some amount A of any currency, so that you can end up with some amount greater than A of that currency. There are no transaction costs and you can trade fractional quantities. ...
Problem You are given an n x n integer matrix board where the cells are labeled from 1 to n^2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row. You start on square 1 of the board. In each move, starting from square curr, do the following: Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n^2)]. This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board. If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next. The game ends when you reach the square n^2. A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n^2 do not have a snake or ladder. ...
It is similar to Graph Representation - Adjacency List (with isDirected) Code Java public class Graph { private Map<Integer, List<Integer>> adjList = new LinkedHashMap<>(); private int V; private final boolean isDirected; public UnweightedAdjListGraph(int n, boolean isDirected) { V = n; for (int i = 0; i < n; i++) { adjMap.put(i, new LinkedList<>()); } this.isDirected = isDirected; } public boolean addEdge(int i, int j) { adjMap.putIfAbsent(i, new LinkedList<>()); adjMap.get(i).add(j); if (!isDirected) { adjMap.putIfAbsent(j, new LinkedList<>()); adjMap.get(j).add(i); } return true; } } ...
Here we will assume the vertices are from 0 to n-1. Below is the code for adjacency list representation of an undirected graph: import java.util.LinkedList; class Graph { private int V; // No. of vertices private final boolean isDirected; private LinkedList<Integer> adj[]; //Adjacency List array //Constructor Graph(int v) { this(v, false); } Graph(int v, boolean isDirected) { V = v; adj = new LinkedList[v]; for (int i = 0; i<v; ++i) { adj[i] = new LinkedList(); } isDirected = isDirected; } //Function to add an edge into the graph void addEdge(int src, int dest) { adj[src].add(dest); // Since graph is undirected, add an edge from dest // to src also if (!isDirected) { adj[dest].add(src); } } void printGraph() { for (int v = 0; v<V; v++) { System.out.println("Adjacency list of vertex " + v); System.out.print("head"); for (Integer pCrawl: adj[v]) { System.out.print(" -> " + pCrawl); } System.out.println("\n"); } } // Driver method public static void main(String args[]) { // Create a graph given in the above diagram Graph g = new Graph(5); g.addEdge(1, 0); g.addEdge(0, 2); g.addEdge(2, 1); g.addEdge(0, 3); g.addEdge(3, 4); System.out.println("Following are strongly connected components " + "in given graph "); } } public class GFG { // Driver program to test above functions public static void main(String args[]) { // create the graph given in above figure int V = 5; //undirected graph Graph graph = new Graph(V); addEdge(graph, 0, 1); addEdge(graph, 0, 4); addEdge(graph, 1, 2); addEdge(graph, 1, 3); addEdge(graph, 1, 4); addEdge(graph, 2, 3); addEdge(graph, 3, 4); // print the adjacency list representation of // the above graph printGraph(graph); } } ...
Problem There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given the integer distanceThreshold. Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number. ...
Problem There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. You want to determine if there is a valid path that exists from vertex source to vertex destination. ...
Problem There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. You want to determine if there is a valid path that exists from vertex source to vertex destination. ...