# Posts tagged as “medium”

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

Now given all the cities and fights, 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.

Note:

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

# Solution 1: DFS

w/o prunning TLE

w/ prunning Accepted

# Solution 3: Bellman-Ford algorithm

dp[k][i]: min cost from src to i taken up to k flights (k-1 stops)

init: dp[0:k+2][src] = 0

transition: dp[k][i] = min(dp[k-1][j] + price[j][i])

ans: dp[K+1][dst]

Time complexity: O(k * |flights|) / O(k*n^2)

Space complexity: O(k*n) -> O(n)

w/o space compression O(k*n)

## Python3

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

# Solution 1: Binary Search

Find the smallest x, such that there are k elements that are smaller or equal to x.

Time complexity: O(nlogn*log(max – min))

Space complexity: O(1)

C++

Problem:

We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After V units of water fall at index K, how much water is at each index?

Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:

• If the droplet would eventually fall by moving left, then move left.
• Otherwise, if the droplet would eventually fall by moving right, then move right.
• Otherwise, rise at it’s current position.

Here, “eventually fall” means that the droplet will eventually be at a lower level if it moves in that direction. Also, “level” means the height of the terrain plus any water in that column.

We can assume there’s infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block – each unit of water has to be in exactly one block.

Idea:

# Solution 1: Simulation

Time complexity: O(V*n)

Space complexity: O(1)

## Python3

Problem:

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Idea:

DP /knapsack

Search

Solution1:

C++ / DP

Time complexity: O(n*amount^2)

Space complexity: O(amount)

Solution2:

C++ / DP

Time complexity: O(n*amount)

Space complexity: O(amount)

Python3

Solution3:

C++ / DFS

Time complexity: O(amount^n/(coin_0*coin_1*…*coin_n))

Space complexity: O(n)

Python3

652. Find Duplicate SubtreesMedium730151FavoriteShare

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

Example 1:

The following are two duplicate subtrees:

        1
/ \
2   3
/   / \
4   2   4
/
4

2
/
4

and

4

Therefore, you need to return above trees’ root in the form of a list.

## Solution 1: Serialization

Time complexity: O(n^2)
Space complexity: O(n^2)

## C++

Solution 2: int id for each unique subtree

Time complexity: O(n)
Space complexity: O(n)