O(n^3) Archives - Huahua's Tech Road

花花酱 LeetCode 375. Guess Number Higher or Lower II

By zxi on March 13, 2020

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

Solution: DP

Use dp[l][r] to denote the min money to win the game if the current guessing range is [l, r], to guarantee a win, we need to try all possible numbers in [l, r]. Let say we guess K, we need to pay K and the game might continue if we were wrong. cost will be K + max(dp(l, K-1), dp(K+1, r)), we need max to cover all possible cases. Among all Ks, we picked the cheapest one.

dp[l][r] = min(k + max(dp[l][k – 1], dp[k+1][r]), for l <= k <= r.

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

C++

// Author: Huahua

class Solution {

public:

int getMoneyAmount(int n) {

constexpr int kInf = 1e9;

vector<vector<int>> cache(n + 2, vector<int>(n + 2, kInf));

function<int(int, int)> dp = [&](int l, int r) {

int& ans = cache[l][r];

if (l >= r) return 0;

if (ans != kInf) return ans;

for (int x = l; x <= r; ++x)

ans = min(ans, x + max(dp(l, x - 1), dp(x + 1, r)));

return ans;

};

return dp(1, n);

}

};

Python3

# Author: Huahua

class Solution:

def getMoneyAmount(self, n: int) -> int:

@lru_cache(maxsize=None)

def dp(l, r):

return min([k + max(dp(l, k - 1), dp(k + 1, r))

for k in range(l, r + 1)]) if l < r else 0

return dp(1, n)

花花酱 LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

By zxi on January 26, 2020

There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional and weighted edge between cities from_i and to_i, and given the integer distanceThreshold.

Return the city with the smallest numberof cities that are reachable through some path and whose distance is at most distanceThreshold, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities i and j is equal to the sum of the edges’ weights along that path.

Example 1:

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> [City 1, City 2] 
City 1 -> [City 0, City 2, City 3] 
City 2 -> [City 0, City 1, City 3] 
City 3 -> [City 1, City 2] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

Example 2:

Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
Output: 0
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 2 for each city are:
City 0 -> [City 1] 
City 1 -> [City 0, City 4] 
City 2 -> [City 3, City 4] 
City 3 -> [City 2, City 4]
City 4 -> [City 1, City 2, City 3] 
The city 0 has 1 neighboring city at a distanceThreshold = 2.

Constraints:

2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= from_i < to_i < n
1 <= weight_i, distanceThreshold <= 10^4
All pairs (from_i, to_i) are distinct.

Solution1: Floyd-Warshall

All pair shortest path

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

C++

// Author: Huahua

class Solution {

public:

int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {

vector<vector<int>> dp(n, vector<int>(n, INT_MAX / 2));

for (const auto& e : edges)

dp[e[0]][e[1]] = dp[e[1]][e[0]] = e[2];

for (int k = 0; k < n; ++k)

for (int u = 0; u < n; ++u)

for (int v = 0; v < n; ++v)

dp[u][v] = min(dp[u][v], dp[u][k] + dp[k][v]);

int ans = -1;

int min_nb = INT_MAX;

for (int u = 0; u < n; ++u) {

int nb = 0;

for (int v = 0; v < n; ++v)

if (v != u && dp[u][v] <= distanceThreshold)

++nb;

if (nb <= min_nb) {

min_nb = nb;

ans = u;

}

return ans;

}

};

Solution 2: Dijkstra’s Algorithm

Time complexity: O(V * ElogV) / worst O(n^3*logn), best O(n^2*logn)
Space complexity: O(V + E)

C++

// Author: Huahua

class Solution {

public:

int findTheCity(int n, vector<vector<int>>& edges, int t) {

vector<vector<pair<int, int>>> g(n);

for (const auto& e : edges) {

g[e[0]].emplace_back(e[1], e[2]);

g[e[1]].emplace_back(e[0], e[2]);

}

// Returns the number of nodes within t from s.

auto dijkstra = [&](int s) {

vector<int> dist(n, INT_MAX / 2);

set<pair<int, int>> q; // <dist, node>

vector<set<pair<int, int>>::const_iterator> its(n);

dist[s] = 0;

for (int i = 0; i < n; ++i)

its[i] = q.emplace(dist[i], i).first;

while (!q.empty()) {

auto it = cbegin(q);

int d = it->first;

int u = it->second;

q.erase(it);

if (d > t) break; // pruning

for (const auto& p : g[u]) {

int v = p.first;

int w = p.second;

if (dist[v] <= d + w) continue;

// Decrease key

q.erase(its[v]);

its[v] = q.emplace(dist[v] = d + w, v).first;

}

return count_if(begin(dist), end(dist), [t](int d) { return d <= t; });

};

int ans = -1;

int min_nb = INT_MAX;

for (int i = 0; i < n; ++i) {

int nb = dijkstra(i);

if (nb <= min_nb) {

min_nb = nb;

ans = i;

}

return ans;

}

};

花花酱 LeetCode 664. Strange Printer

By zxi on September 20, 2017

Problem:

There is a strange printer with the following two special requirements:

The printer can only print a sequence of the same character each time.
At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.

Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

Example 1:

Input: "aaabbb"

Output: 2

Explanation: Print "aaa" first and then print "bbb".

Example 2:

Input: "aba"

Output: 2

Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.

Hint: Length of the given string will not exceed 100.

Idea:

Dynamic programming

Time Complexity:

O(n^3)

Space Complexity:

O(n^2)

Solution:

C++

// Author: Huahua

// Time Complexity: O(n^3)

// Space Complexity: O(n^2)

// Running Time: 22 ms

class Solution {

public:

int strangePrinter(const string& s) {

int l = s.length();

t_ = vector<vector<int>>(l, vector<int>(l, 0));

return turn(s, 0, s.length() - 1);

}

private:

// Minimal turns to print s[i] to s[j]

int turn(const string& s, int i, int j) {

// Empty string

if (i > j) return 0;

// Solved

if (t_[i][j] > 0) return t_[i][j];

// Default behavior, print s[i] to s[j-1] and print s[j]

int ans = turn(s, i, j-1) + 1;

for (int k = i; k < j; ++k)

if (s[k] == s[j])

ans = min(ans, turn(s, i, k) + turn(s, k + 1, j - 1));

return t_[i][j] = ans;

}

vector<vector<int>> t_;

};

Java

// Author: Huahua

// Time Complexity: O(n^3)

// Space Complexity: O(n^2)

// Running Time: 31 ms (beat 99.25%) 9/2017

class Solution {

public int strangePrinter(String s) {

int l = s.length();

t_ = new int[l][l];

return turn(s.toCharArray(), 0, l - 1);

}

// Minimal turns to print s[i] to s[j]

private int turn(char[] s, int i, int j) {

// Empty string

if (i > j) return 0;

// Solved

if (t_[i][j] > 0) return t_[i][j];

// Default behavior, print s[i] to s[j-1] and print s[j]

int ans = turn(s, i, j-1) + 1;

for (int k = i; k < j; ++k)

if (s[k] == s[j])

ans = Math.min(ans, turn(s, i, k) + turn(s, k + 1, j - 1));

return t_[i][j] = ans;

}

private int[][] t_;

}

Python3

"""

Author: Huahua

Time Complexity: O(n^3)

Space Complexity: O(n^2)

Running Time: 895 ms (beat 66%) 9/2017

"""

class Solution(object):

def strangePrinter(self, s):

"""

:type s: str

:rtype: int

"""

l = len(s)

self._t = [[0 for _ in xrange(l)] for _ in xrange(l)]

return self._turns(s, 0, l - 1)

def _turns(self, s, i, j):

if i > j: return 0

if self._t[i][j] > 0: return self._t[i][j]

ans = self._turns(s, i, j - 1) + 1

for k in xrange(i, j):

if s[k] == s[j]:

ans = min(ans, self._turns(s, i, k)

+ self._turns(s, k + 1, j-1))

self._t[i][j] = ans

return self._t[i][j]

Posts tagged as “O(n^3)”

花花酱 LeetCode 375. Guess Number Higher or Lower II

Solution: DP

C++

Python3

花花酱 LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

Solution1: Floyd-Warshall

C++

C++

花花酱 LeetCode 664. Strange Printer

C++

Java

Python3