0

2

4

7

-2

Single source shorted path from vetex 0 exist? yes

1 | //O(V*E) |

0

2

4

7

-2

Single source shorted path from vetex 0 exist? yes

1 | //O(V*E) |

https://leetcode.com/problems/cheapest-flights-within-k-stops/

There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w.

Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

Example 1:

Input:

n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]

src = 0, dst = 2, k = 1

Output: 200

Explanation:

The graph looks like this:

The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

Example 2:

Input:

n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]

src = 0, dst = 2, k = 0

Output: 500

Explanation:

The graph looks like this:

The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Constraints:

The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 1.

The size of flights will be in range [0, n * (n - 1) / 2].

The format of each flight will be (src, dst, price).

The price of each flight will be in the range [1, 10000].

k is in the range of [0, n - 1].

There will not be any duplicated flights or self cycles.

1 | class Solution { |

https://leetcode.com/problems/network-delay-time/

https://leetcode.com/problems/network-delay-time/discuss/283711/Python-Bellman-Ford-SPFA-Dijkstra-Floyd-clean-and-easy-to-understand

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

Output: 2

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1

Output: 1

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2

Output: -1

Constraints:

1 <= k <= n <= 100

1 <= times.length <= 6000

times[i].length == 3

1 <= ui, vi <= n

ui != vi

0 <= wi <= 100

All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

1 | //Dijikstra: O(ElogE), priority queue |

https://leetcode.com/problems/path-with-maximum-probability/

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2

Output: 0.25000

Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

Example 2:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2

Output: 0.30000

Example 3:

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2

Output: 0.00000

Explanation: There is no path between 0 and 2.

Constraints:

2 <= n <= 10^4

0 <= start, end < n

start != end

0 <= a, b < n

a != b

0 <= succProb.length == edges.length <= 2*10^4

0 <= succProb[i] <= 1

There is at most one edge between every two nodes.

1 | //Dijikstra, timeout |

https://leetcode.com/problems/form-array-by-concatenating-subarrays-of-another-array/

You are given a 2D integer array groups of length n. You are also given an integer array nums.

You are asked if you can choose n disjoint subarrays from the array nums such that the ith subarray is equal to groups[i] (0-indexed), and if i > 0, the (i-1)th subarray appears before the ith subarray in nums (i.e. the subarrays must be in the same order as groups).

Return true if you can do this task, and false otherwise.

Note that the subarrays are disjoint if and only if there is no index k such that nums[k] belongs to more than one subarray. A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]

Output: true

Explanation: You can choose the 0th subarray as [1,-1,0,1,-1,-1,3,-2,0] and the 1st one as [1,-1,0,1,-1,-1,3,-2,0].

These subarrays are disjoint as they share no common nums[k] element.

Example 2:

Input: groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]

Output: false

Explanation: Note that choosing the subarrays [1,2,3,4,10,-2] and [1,2,3,4,10,-2] is incorrect because they are not in the same order as in groups.

[10,-2] must come before [1,2,3,4].

Example 3:

Input: groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]

Output: false

Explanation: Note that choosing the subarrays [7,7,1,2,3,4,7,7] and [7,7,1,2,3,4,7,7] is invalid because they are not disjoint.

They share a common elements nums[4] (0-indexed).

Constraints:

groups.length == n

1 <= n <= 10^3

1 <= groups[i].length, sum(groups[i].length) <= 10^3

1 <= nums.length <= 10^3

-10^7 <= groups[i][j], nums[k] <= 10^7

1 | class Solution { |

https://leetcode.com/problems/check-array-formation-through-concatenation/

You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i].

Return true if it is possible to form the array arr from pieces. Otherwise, return false.

Example 1:

Input: arr = [85], pieces = [[85]]

Output: true

Example 2:

Input: arr = [15,88], pieces = [[88],[15]]

Output: true

Explanation: Concatenate [15] then [88]

Example 3:

Input: arr = [49,18,16], pieces = [[16,18,49]]

Output: false

Explanation: Even though the numbers match, we cannot reorder pieces[0].

Example 4:

Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]

Output: true

Explanation: Concatenate [91] then [4,64] then [78]

Example 5:

Input: arr = [1,3,5,7], pieces = [[2,4,6,8]]

Output: false

Constraints:

1 <= pieces.length <= arr.length <= 100

sum(pieces[i].length) == arr.length

1 <= pieces[i].length <= arr.length

1 <= arr[i], pieces[i][j] <= 100

The integers in arr are distinct.

The integers in pieces are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).

1 | class Solution { |

https://leetcode.com/problems/path-with-minimum-effort/

https://leetcode.com/problems/path-with-minimum-effort/discuss/909200/C%2B%2B-Concise-Dijikstra-algorithm-350ms

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Example 1:

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]

Output: 2

Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.

This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.

Example 2:

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]

Output: 1

Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].

Example 3:

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]

Output: 0

Explanation: This route does not require any effort.

Constraints:

rows == heights.length

columns == heights[i].length

1 <= rows, columns <= 100

1 <= heights[i][j] <= 10^6

1 | class Solution { |

Single source shortest path

0 -> 0 = 0

0 -> 1 = 8

0 -> 2 = 9

0 -> 3 = 5

0 -> 4 = 7

1 | vector<int> shortest_path(int n, vector<vector<int>> &edges) { |

https://leetcode.com/problems/map-of-highest-peak/

You are given an integer matrix isWater of size m x n that represents a map of land and water cells.

If isWater[i][j] == 0, cell (i, j) is a land cell.

If isWater[i][j] == 1, cell (i, j) is a water cell.

You must assign each cell a height in a way that follows these rules:

The height of each cell must be non-negative.

If the cell is a water cell, its height must be 0.

Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).

Find an assignment of heights such that the maximum height in the matrix is maximized.

Return an integer matrix height of size m x n where height[i][j] is cell (i, j)’s height. If there are multiple solutions, return any of them.

Example 1:

Input: isWater = [[0,1],[0,0]]

Output: [[1,0],[2,1]]

Explanation: The image shows the assigned heights of each cell.

The blue cell is the water cell, and the green cells are the land cells.

Example 2:

Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]

Output: [[1,1,0],[0,1,1],[1,2,2]]

Explanation: A height of 2 is the maximum possible height of any assignment.

Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.

Constraints:

m == isWater.length

n == isWater[i].length

1 <= m, n <= 1000

isWater[i][j] is 0 or 1.

There is at least one water cell.

1 | class Solution { |

https://leetcode.com/problems/longest-nice-substring/

https://leetcode.com/problems/longest-nice-substring/discuss/1075320/C%2B%2B-Divide-and-Conquer-O(N)-Time

https://leetcode.com/problems/longest-nice-substring/discuss/1074856/C%2B%2B-O(n)

A string s is nice if, for every letter of the alphabet that s contains, it appears both in uppercase and lowercase. For example, “abABB” is nice because ‘A’ and ‘a’ appear, and ‘B’ and ‘b’ appear. However, “abA” is not because ‘b’ appears, but ‘B’ does not.

Given a string s, return the longest substring of s that is nice. If there are multiple, return the substring of the earliest occurrence. If there are none, return an empty string.

Example 1:

Input: s = “YazaAay”

Output: “aAa”

Explanation: “aAa” is a nice string because ‘A/a’ is the only letter of the alphabet in s, and both ‘A’ and ‘a’ appear.

“aAa” is the longest nice substring.

Example 2:

Input: s = “Bb”

Output: “Bb”

Explanation: “Bb” is a nice string because both ‘B’ and ‘b’ appear. The whole string is a substring.

Example 3:

Input: s = “c”

Output: “”

Explanation: There are no nice substrings.

Example 4:

Input: s = “dDzeE”

Output: “dD”

Explanation: Both “dD” and “eE” are the longest nice substrings.

As there are multiple longest nice substrings, return “dD” since it occurs earlier.

Constraints:

1 <= s.length <= 100

s consists of uppercase and lowercase English letters.

1 | //O(N^2) |