https://www.savethestudent.org/travel/how-to-get-cheap-flights-as-a-student.html

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:


Reference: https://www.themayor.eu/ro/france-could-soon-remove-1-and-2-eurocent-coins

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.

Solution 1:

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


Reference: https://www.sjpl.org/social-work

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 = 3
Output:
73
Explanation: 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…


Reference: https://www.dreamstime.com/definition-alien-fake-dictionary-word-image135385630

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 "".

Solution:

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


Reference: https://www.geeksforgeeks.org/heap-data-structure/

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

Solution:

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.


Reference: https://www.windowworldhouston.com/windows/double-hung/

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"

Solution 1:

Intuition: Use nested while loops to find the minimum sub string that starts from each character and return the smallest one.
  1. 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"

Solution:

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.
  1. For loop iterate through the shift array
  2. Inside the for loop, add if it’s left shift, subtract if it’s right shift.
  3. If the number of total left shifts needed…


Reference: https://www.unite.ai/what-is-k-nearest-neighbors/

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.

Let nums be the input array, k be the targeted pair, and n be 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…


Reference: https://gist.github.com/huang983/71efca0f49ca3bf4fd278f0ab2f6abb9

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

Timothy Huang

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store