Advanced Graphs

You are given a network of `n` directed nodes, labeled from `1` to `n`. You are also given `times`, a list of directed edges where `times[i] = (ui, vi, ti)`. * `ui` is the source node (an integer from `1` to `n`) * `vi` is the target node (an integer from `1` to `n`) * `ti` is the time it takes for a signal to travel from the source to the target node (an integer greater than or equal to `0`). You are also given an integer `k`, representing the node that we will send a signal from. Return the **minimum** time it takes for all of the `n` nodes to receive the signal. If it is impossible for all the nodes to receive the signal, return `-1` instead. **Example 1:**  ```java Input: times = [[1,2,1],[2,3,1],[1,4,4],[3,4,1]], n = 4, k = 1 Output: 3 ``` **Example 2:** ```java Input: times = [[1,2,1],[2,3,1]], n = 3, k = 2 Output: -1 ``` **Constraints:** * `1 <= k <= n <= 100` * `1 <= times.length <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(ElogV)</code> time and <code>O(V + E)</code> space, where <code>E</code> is the number of edges and <code>V</code> is the number of vertices (nodes). </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> As we are given the source node and we need to find the minimum time to reach all nodes, this represents the shortest path from the source node to all nodes. Can you think of a standard algorithm to find the shortest path from a source to a destination? Maybe a heap-based algorithm is helpful. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use Dijkstra's algorithm to find the shortest path from a source to destination. We end up finding the shortest paths from the source to the nodes that we encounter in finding the destination. So, to find shortest path for all nodes from the source, we need to perform Dijkstra's algorithm until the heap in this algorithm becomes empty. How would you implement this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We use a Min-Heap as we need to find the minimum time. We create an adjacency list for the given times (weighted edges). We also initialize an array <code>dist[]</code> of size <code>n</code> (number of nodes) which represents the distance from the source to all nodes, initialized with infinity. We put <code>dist[source] = 0</code>. Then we continue the algorithm. After the heap becomes empty, if we don't visit any node, we return <code>-1</code>; otherwise, we return the time. </p> </details>

You are given a list of flight tickets `tickets` where `tickets[i] = [from_i, to_i]` represent the source airport and the destination airport. Each `from_i` and `to_i` consists of three uppercase English letters. Reconstruct the itinerary in order and return it. All of the tickets belong to someone who originally departed from `"JFK"`. Your objective is to reconstruct the flight path that this person took, assuming each ticket was used exactly once. If there are multiple valid flight paths, return the lexicographically smallest one. * For example, the itinerary `["JFK", "SEA"]` has a smaller lexical order than `["JFK", "SFO"]`. You may assume all the tickets form at least one valid flight path. **Example 1:**  ```java Input: tickets = [["BUF","HOU"],["HOU","SEA"],["JFK","BUF"]] Output: ["JFK","BUF","HOU","SEA"] ``` **Example 2:**  ```java Input: tickets = [["HOU","JFK"],["SEA","JFK"],["JFK","SEA"],["JFK","HOU"]] Output: ["JFK","HOU","JFK","SEA","JFK"] ``` Explanation: Another possible reconstruction is `["JFK","SEA","JFK","HOU","JFK"]` but it is lexicographically larger. **Constraints:** * `1 <= tickets.length <= 300` * `from_i != to_i` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(ElogE)</code> time and <code>O(E)</code> space, where <code>E</code> is the number of tickets (edges). </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Consider this problem as a graph where airports are the nodes and tickets are the edges. Since we need to utilize all the tickets exactly once, can you think of an algorithm that visits every edge exactly once? Additionally, how do you ensure the smallest lexical order is maintained? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We build an adjacency list from the given tickets, which represent directed edges. We perform a DFS to construct the result, but we first sort the neighbors' list of each node to ensure the smallest lexical order. Why? Sorting guarantees that during DFS, we visit the node with the smallest lexical order first. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> DFS would be a naive solution, as it takes <code>O(E * V)</code> time, where <code>E</code> is the number of tickets (edges) and <code>V</code> is the number of airports (nodes). In this approach, we traverse from the given source airport <code>JFK</code>, perform DFS by removing the neighbor, traversing it, and then reinserting it back. Can you think of a better way? Perhaps an advanced algorithm that incorporates DFS might be helpful? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> We can use Hierholzer's algorithm, a modified DFS approach. Instead of appending the node to the result list immediately, we first visit all its neighbors. This results in a post-order traversal. After completing all the DFS calls, we reverse the path to obtain the final path, which is also called Euler's path. </p> </details>

You are given a 2-D integer array `points`, where `points[i] = [xi, yi]`. Each `points[i]` represents a distinct point on a 2-D plane. The cost of connecting two points `[xi, yi]` and `[xj, yj]` is the **manhattan distance** between the two points, i.e. `|xi - xj| + |yi - yj|`. Return the minimum cost to connect all points together, such that there exists exactly one path between each pair of points. **Example 1:**  ```java Input: points = [[0,0],[2,2],[3,3],[2,4],[4,2]] Output: 10 ``` **Constraints:** * `1 <= points.length <= 1000` * `-1000 <= xi, yi <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O((n^2)logn)</code> time and <code>O(n^2)</code> space, where <code>n</code> is the number of points. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Think of this problem as a graph, where the given points represent nodes. We need to connect these nodes into a single component by creating edges. Can you think of an advanced graph algorithm that can be used to connect all points into one component? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We use Kruskal's algorithm along with Union-Find (DSU) to connect nodes into components. The final component forms the minimum spanning tree (MST), where the edges between nodes are weighted by the Manhattan distance, and the total weight of the tree is minimized. How would you implement this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We create the possible edges by iterating through every pair of points and calculating the weights as the Manhattan distance between them. Next, we sort the edges in ascending order based on their weights, as we aim to minimize the cost. Then, we traverse through these edges, connecting the nodes and adding the weight of the edge to the total cost if the edge is successfully added. The final result will be the minimum cost. </p> </details>

You are given a square 2-D matrix of distinct integers `grid` where each integer `grid[i][j]` represents the elevation at position `(i, j)`. Rain starts to fall at time = `0`, which causes the water level to rise. At time `t`, the water level across the entire grid is `t`. You may swim either horizontally or vertically in the grid between two adjacent squares if the original elevation of both squares is less than or equal to the water level at time `t`. Starting from the top left square `(0, 0)`, return the minimum amount of time it will take until it is possible to reach the bottom right square `(n - 1, n - 1)`. **Example 1:**  ```java Input: grid = [[0,1],[2,3]] Output: 3 ``` Explanation: For a path to exist to the bottom right square `grid[1][1]` the water elevation must be at least `3`. At time `t = 3`, the water level is `3`. **Example 2:**  ```java Input: grid = [ [0,1,2,10], [9,14,4,13], [12,3,8,15], [11,5,7,6] ] Output: 8 ``` Explanation: The water level must be at least `8` to reach the bottom right square. The path is `[0, 1, 2, 4, 8, 7, 6]`. **Constraints:** * `grid.length == grid[i].length` * `1 <= grid.length <= 50` * `0 <= grid[i][j] < n^2` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O((n^2)logn)</code> time and <code>O(n^2)</code> space, where <code>n</code> is the number of rows or columns of the square matrix. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Think of this problem as a graph where each cell represents a node. You can move from one cell to its adjacent cell if the time is greater than or equal to the adjacent cell's elevation. Note that swimming does not cost time, but you may need to wait at a cell for the time to reach the required elevation. What do you notice about the path from <code>(0, 0)</code> to <code>(n - 1, n - 1)</code>? Perhaps a greedy approach would be useful here. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can observe that the maximum elevation value along the path determines the time taken for that path. Therefore, we need to find the path where the maximum elevation is minimized. Can you think of an algorithm to find such a path from the source <code>(0, 0)</code> to the destination <code>(n - 1, n - 1)</code>? Perhaps a shortest path algorithm could be useful here. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use Dijkstra's algorithm. We initialize a Min-heap and a matrix with infinity. We run the algorithm starting from the source <code>(0, 0)</code>, and we track the maximum elevation encountered along the paths. This maximum elevation is used as the key for comparison in Dijkstra's algorithm. If we encounter the destination <code>(n - 1, n - 1)</code>, we return the maximum elevation of the path that reached the destination. </p> </details>

Give any solution out of multiple solutions There is a foreign language which uses the latin alphabet, but the order among letters is *not* "a", "b", "c" ... "z" as in English. You receive a list of *non-empty* strings `words` from the dictionary, where the words are **sorted lexicographically** based on the rules of this new language. Derive the order of letters in this language. If the order is invalid, return an empty string. If there are multiple valid order of letters, return **any** of them. A string `a` is lexicographically smaller than a string `b` if either of the following is true: * The first letter where they differ is smaller in `a` than in `b`. * `a` is a prefix of `b` *and* `a.length < b.length`. **Example 1:** ```java Input: ["z","o"] Output: "zo" ``` Explanation: From "z" and "o", we know 'z' < 'o', so return "zo". **Example 2:** ```java Input: ["hrn","hrf","er","enn","rfnn"] Output: "hernf" ``` Explanation: * from "hrn" and "hrf", we know 'n' < 'f' * from "hrf" and "er", we know 'h' < 'e' * from "er" and "enn", we know get 'r' < 'n' * from "enn" and "rfnn" we know 'e'<'r' * so one possibile solution is "hernf" **Constraints:** * The input `words` will contain characters only from lowercase `'a'` to `'z'`. * `1 <= words.length <= 100` * `1 <= words[i].length <= 100` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(N + V + E)</code> time and <code>O(V + E)</code> space, where <code>N</code> is the sum of the lengths of all the strings, <code>V</code> is the number of unique characters (vertices), and <code>E</code> is the number of edges. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Can you think of this as a graph problem? Characters from <code>a</code> through <code>z</code> are nodes. What could the edges represent here? How can you create edges from the given words? Perhaps you should try comparing two adjacent words. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> The relative ordering of the characters can be treated as edges. For example, consider the words ordered as <code>["ape", "apple"]</code>. <code>"ape"</code> comes before <code>"apple"</code>, which indicates that <code>'e'</code> is a predecessor of <code>'p'</code>. Therefore, there is a directed edge <code>e -> p</code>, and this dependency should be valid across all the words. In this way, we can build an adjacency list by comparing adjacent words. Can you think of an algorithm that is suitable to find a valid ordering? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We can use Topological Sort to ensure every node appears after its predecessor. Using DFS, we traverse the graph built from the adjacency list. A visited map tracks nodes in the current DFS path: <code>False</code> means not in the path, and <code>True</code> means in the path. If any DFS call returns <code>True</code>, it indicates a cycle and we return immediately. How do we extract the ordering from this DFS? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> When we visit a node and its children and don't find a cycle, we mark the node as <code>False</code> in the map and append it to the result, treating this as a post-order traversal. If we find a cycle, we return an empty string; otherwise, we return the result list. </p> </details>

There are `n` airports, labeled from `0` to `n - 1`, which are connected by some flights. You are given an array `flights` where `flights[i] = [from_i, to_i, price_i]` represents a one-way flight from airport `from_i` to airport `to_i` with cost `price_i`. You may assume there are no duplicate flights and no flights from an airport to itself. You are also given three integers `src`, `dst`, and `k` where: * `src` is the starting airport * `dst` is the destination airport * `src != dst` * `k` is the maximum number of stops you can make (not including `src` and `dst`) Return **the cheapest price** from `src` to `dst` with at most `k` stops, or return `-1` if it is impossible. **Example 1:**  ```java Input: n = 4, flights = [[0,1,200],[1,2,100],[1,3,300],[2,3,100]], src = 0, dst = 3, k = 1 Output: 500 ``` Explanation: The optimal path with at most 1 stop from airport 0 to 3 is shown in red, with total cost `200 + 300 = 500`. Note that the path `[0 -> 1 -> 2 -> 3]` costs only 400, and thus is cheaper, but it requires 2 stops, which is more than k. **Example 2:**  ```java Input: n = 3, flights = [[1,0,100],[1,2,200],[0,2,100]], src = 1, dst = 2, k = 1 Output: 200 ``` Explanation: The optimal path with at most 1 stop from airport 1 to 2 is shown in red and has cost `200`. **Constraints:** * `1 <= n <= 100` * `fromi != toi` * `1 <= pricei <= 1000` * `0 <= src, dst, k < n` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(n + (m * k))</code> time and <code>O(n)</code> space, where <code>n</code> is the number of cities, <code>m</code> is the number of flights, and <code>k</code> is the number of stops. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> Consider this as a graph problem where the cities are nodes and the flights are edges connecting two cities, with the ticket cost as the edge weight. Can you think of a shortest path algorithm to solve the problem? Perhaps a better algorithm than Dijkstra's that can intuitively handle the <code>k</code> stops condition. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use the Bellman-Ford algorithm. Initialize a <code>prices</code> array of size <code>n</code> with <code>Infinity</code>, setting <code>prices[source] = 0</code>. These values describe the cost to reach a city from the source city. Iterate <code>(k + 1)</code> times (stops are 0-indexed), updating the cost to each city by extending paths from cities with valid costs. We only update the cost for a city if it is less than the previous cost. How would you implement this? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> At each level of iteration, we go through the given flights and use them to update the price array with the minimum costs compared to the previous level. We use a temporary prices array at each level to store the updated costs. After completing all levels, we return the result stored in <code>prices[dst]</code>. If that value is <code>Infinity</code>, we return <code>-1</code> instead. </p> </details>