LeetCode: 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:

LeetCode: https://leetcode.com/problems/coin-change-2/

Given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount, assuming that you have infinite number of each kind of coin.

**Input:** amount = 5, coins = [1, 2, 5]

**Output:** 4

**Explanation:** there are four ways to make up the amount:

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

This is another classic dynamic programming problem where it can be solved with a more straightforward recursive approach and then optimized with iterative approach.

**State: 1**. Parameters: total - current amount, start - index of the input…

Given an array of integers and integer K, each integer in the array represents the cost to reach the corresponding index and K represents the maximum jump one can take. The goal is to find the minimum cost to reach the last index in the array starting from the beginning.

Input:

arr = [20, 30, 40, 25, 15, 20, 28], K = 3Output:

73Explanation: Since K = 3, we can start from 30, and then take 3 jumps to 15, and lastly 28 (30 + 15 + 28). Alternatively, start from 20, take 3 jumps to 25, and…

LeetCode: https://leetcode.com/problems/alien-dictionary/

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of **non-empty** words from the dictionary, where **words are sorted lexicographically by the rules of this new language**. Derive the order of letters in this language.

Input:

[

"wrt",

"wrf",

"er",

"ett",

"rftt"

]Output:"wertf"Input:

[

"z",

"x"

]Output:"zx"Input:

[

"z",

"x",

"z"

]Output:""Explanation:The order is invalid, so return "".

`Intuition: Build a graph w each character as a vertex and dependency as an edge…`

LeetCode: https://leetcode.com/problems/merge-k-sorted-lists/

Merge *k* sorted linked lists and return it as one sorted list.

Input:

[

1 -> 4 -> 5,

1 -> 3 -> 4,

2 -> 6

]Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Intuition: Having the head node of each sorted linked lists, we can implement a min heap that first push all the head nodes onto the min heap. Then pop the smallest one and push its next node onto the min heap in each iteration. The loop will terminate when the heap queue is empty.…

LeetCode: https://leetcode.com/problems/minimum-window-substring/submissions/

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"Input: s = "ABCDEFGF", t = "HIJKL"

Output: ""Input: s = "ABCDEFGF", t = "DEFF"

Output: "DEFGF"Input: s = "b", t = "bb"

Output: ""Input: s = "abc, t = "b"

Output: "b"

`Intuition: Use nested while loops to find the minimum sub string that starts from each character and return the smallest one.`

- Use the collections library’s counter to create…

LeetCode: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3299/

You are given a string `s`

containing lowercase English letters, and a matrix `shift`

, where `shift[i] = [direction, amount]`

0 means left shift, and 1 means right shift.

`Input: s = "abc", shift = [[0, 1], [1, 2]]`

Output: "cab"

`Shifting the string as we traverse through the shift array would be too expensive. Instead, we can just count the total left shift times and shift the string once.`

- For loop iterate through the shift array
- Inside the for loop, add if it’s left shift, subtract if it’s right shift.
- If the number of total left shifts needed…

LeetCode: https://leetcode.com/problems/find-k-th-smallest-pair-distance/

Given an integer array, return the k-th smallest **distance** among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

Letnumsbe the input array,kbe the targeted pair, andnbe the size of the input arraynums = [1, 3, 1], k = 2 -> d = 2

Explanation: (1, 1), (1, 3), (1, 3) or (3, 1)nums = [0, 0, 0, 0, 1, 1, 1, 2, 2, 2], k = 5 -> d = 0 Explanation: Of all the 45 pairs, know…

LeetCode: https://leetcode.com/problems/number-of-islands-ii/

Given a water 2D matrix and an array of positions that need to be turned to lands, find the number of islands after each operation

positions = [[0, 0]. [1, 1], [2, 2], [0, 2], [2, 0]]

water matrix:

0 0 0

0 0 0

0 0 0[0, 0]: 1 0 0

0 0 0

0 0 0 1 island[1, 1]: 1 0 0

0 1 0

0 0 0 2 islands[2, 2]: 1 0 0

0 1 0

0 0 1 3 islands[0, 2]: 1 0 1

0 1 0

0 0 1 …