Posts tagged as “hard”

花花酱 LeetCode 1510. Stone Game IV

By zxi on July 17, 2020

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player’s turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

Example 4:

Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0). 
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).

Example 5:

Input: n = 17
Output: false
Explanation: Alice can't win the game if Bob plays optimally.

Constraints:

1 <= n <= 10^5

Solution: Recursion w/ Memoization / DP

Let win(n) denotes whether the current play will win or not.
Try all possible square numbers and see whether the other player will lose or not.
win(n) = any(win(n – i*i) == False) ? True : False
base case: win(0) = False

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

C++

class Solution {

public:

bool winnerSquareGame(int n) {

vector<int> cache(n + 1, 0); // 0:Unknown, 1:Win, -1:Lose

function<int(int)> win = [&](int n) -> int {

if (n == 0) return -1;

if (cache[n]) return cache[n];

for (int i = sqrt(n); i >= 1; --i)

if (win(n - i * i) < 0) return cache[n] = 1;

return cache[n] = -1;

};

return win(n) > 0;

}

};

Java

class Solution {

private int[] cache;

public boolean winnerSquareGame(int n) {

this.cache = new int[n + 1];

return this.win(n) > 0;

}

private int win(int n) {

if (n == 0) return -1;

if (this.cache[n] != 0) return this.cache[n];

for (int i = (int)Math.sqrt(n); i >= 1; --i)

if (win(n - i * i) < 0)

return this.cache[n] = 1;

return this.cache[n] = -1;

}

Python3

class Solution:

def winnerSquareGame(self, n: int) -> bool:

dp = [None] * (n + 1)

dp[0] = False

for i in range(0, n):

if dp[i]: continue

for j in range(1, n + 1):

if i + j * j > n: break

dp[i + j * j] = True

return dp[n]

花花酱 LeetCode 1499. Max Value of Equation

By zxi on June 28, 2020

Given an array points containing the coordinates of points on a 2D plane, sorted by the x-values, where points[i] = [x_i, y_i] such that x_i < x_j for all 1 <= i < j <= points.length. You are also given an integer k.

Example 1:

Input: points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
Output: 4
Explanation: The first two points satisfy the condition |x_i - x_j| <= 1 and if we calculate the equation we get 3 + 0 + |1 - 2| = 4. Third and fourth points also satisfy the condition and give a value of 10 + -10 + |5 - 6| = 1.
No other pairs satisfy the condition, so we return the max of 4 and 1.

Example 2:

Input: points = [[0,0],[3,0],[9,2]], k = 3
Output: 3
Explanation: Only the first two points have an absolute difference of 3 or less in the x-values, and give the value of 0 + 0 + |0 - 3| = 3.

Constraints:

2 <= points.length <= 10^5
points[i].length == 2
-10^8 <= points[i][0], points[i][1] <= 10^8
0 <= k <= 2 * 10^8
points[i][0] < points[j][0] for all 1 <= i < j <= points.length
x_i form a strictly increasing sequence.

Observation

Since xj > xi, so |xi – xj| + yi + yj => xj + yj + (yi – xi)
We want to have yi – xi as large as possible while need to make sure xj – xi <= k.

Solution 1: Priority Queue / Heap

Put all the points processed so far onto the heap as (y-x, x) sorted by y-x in descending order.
Each new point (x_j, y_j), find the largest y-x such that x_j – x <= k.

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

C++

// Author: Huahua

class Solution {

public:

int findMaxValueOfEquation(vector<vector<int>>& points, int k) {

priority_queue<pair<int, int>> q; // {y - x, x}

q.emplace(0, -1e9);

int ans = INT_MIN;

for (const auto& p : points) {

const int x = p[0], y = p[1];

while (!q.empty() && x - q.top().second > k) q.pop();

if (!q.empty())

ans = max(ans, x + y + q.top().first);

q.emplace(y - x, x);

}

return ans;

}

};

Solution 2: Monotonic Queue

Maintain a monotonic queue:
1. The queue is sorted by y – x in descending order.
2. Pop then front element when xj – x_front > k, they can’t be used anymore.
3. Record the max of {xj + yj + (y_front – x_front)}
4. Pop the back element when yj – xj > y_back – x_back, they are smaller and lefter. Won’t be useful anymore.
5. Finally, push the j-th element onto the queue.

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

C++

// Author: Huahua

class Solution {

public:

int findMaxValueOfEquation(vector<vector<int>>& points, int k) {

deque<pair<int, int>> q; // {y - x, x} Sort by y - x.

int ans = INT_MIN;

for (const auto& p : points) {

const int xj = p[0];

const int yj = p[1];

// Remove invalid points, e.g. xj - xi > k

while (!q.empty() && xj - q.front().second > k)

q.pop_front();

if (!q.empty())

ans = max(ans, xj + yj + q.front().first);

while (!q.empty() && yj - xj >= q.back().first)

q.pop_back();

q.emplace_back(yj - xj, xj);

}

return ans;

}

};

Java

class Solution {

public int findMaxValueOfEquation(int[][] points, int k) {

var q = new ArrayDeque<Integer>();

int ans = Integer.MIN_VALUE;

for (int i = 0; i < points.length; ++i) {

int xj = points[i][0];

int yj = points[i][1];

while (!q.isEmpty() && xj - points[q.getFirst()][0] > k) {

q.removeFirst();

}

if (!q.isEmpty()) {

ans = Math.max(ans, xj + yj

+ points[q.getFirst()][1] - points[q.getFirst()][0]);

}

while (!q.isEmpty() && yj - xj

>= points[q.getLast()][1] - points[q.getLast()][0]) {

q.removeLast();

}

q.offer(i);

}

return ans;

}

python3

# Author: Huahua

class Solution:

def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:

ans = float('-inf')

q = deque() # {(y - x, x)}

for x, y in points:

while q and x - q[0][1] > k: q.popleft()

if q: ans = max(ans, x + y + q[0][0])

while q and y - x >= q[-1][0]: q.pop()

q.append((y - x, x))

return ans

花花酱 LeetCode 1494. Parallel Courses II

By zxi on June 27, 2020

Given the integer n representing the number of courses at some university labeled from 1 to n, and the array dependencies where dependencies[i] = [x_i, y_i] represents a prerequisite relationship, that is, the course x_i must be taken before the course y_i. Also, you are given the integer k.

In one semester you can take at most k courses as long as you have taken all the prerequisites for the courses you are taking.

Return the minimum number of semesters to take all courses. It is guaranteed that you can take all courses in some way.

Example 1:

Input: n = 4, dependencies = [[2,1],[3,1],[1,4]], k = 2
Output: 3 
Explanation: The figure above represents the given graph. In this case we can take courses 2 and 3 in the first semester, then take course 1 in the second semester and finally take course 4 in the third semester.

Example 2:

Input: n = 5, dependencies = [[2,1],[3,1],[4,1],[1,5]], k = 2
Output: 4 
Explanation: The figure above represents the given graph. In this case one optimal way to take all courses is: take courses 2 and 3 in the first semester and take course 4 in the second semester, then take course 1 in the third semester and finally take course 5 in the fourth semester.

Example 3:

Input: n = 11, dependencies = [], k = 2
Output: 6

Constraints:

1 <= n <= 15
1 <= k <= n
0 <= dependencies.length <= n * (n-1) / 2
dependencies[i].length == 2
1 <= x_i, y_i <= n
x_i != y_i
All prerequisite relationships are distinct, that is, dependencies[i] != dependencies[j].
The given graph is a directed acyclic graph.

Solution: DP / Bitmask

NOTE: This is a NP problem, any polynomial-time algorithm is incorrect otherwise P = NP.

Variant 1:
dp[m] := whether state m is reachable, where m is the bitmask of courses studied.
For each semester, we enumerate all possible states from 0 to 2^n – 1, if that state is reachable, then we choose c (c <= k) courses from n and check whether we can study those courses.
If we can study those courses, we have a new reachable state, we set dp[m | courses] = true.

Time complexity: O(n*2^n*2^n) = O(n*n^4) <– This will be much smaller in practice.
and can be reduced to O(n*3^n).
Space complexity: O(2^n)

C++

// Author: Huahua, 52 ms, 14.5 MB

class Solution {

public:

int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {

const int S = 1 << n;

vector<int> deps(n); // deps[i] = dependency mask for course i.

for (const auto& d : dependencies)

deps[d[1] - 1] |= 1 << (d[0] - 1);

// dp(i)[s] := reachable(s) at semester i.

vector<int> dp(S);

dp[0] = 1;

for (int d = 1; d <= n; ++d) { // at most n semesters.

vector<int> tmp(S); // start a new semesters.

for (int s = 0; s < S; ++s) {

if (!dp[s]) continue; // not a reachable state.

int mask = 0;

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

if (!(s & (1 << i)) && (s & deps[i]) == deps[i])

mask |= (1 << i);

// Prunning, take all.

if (__builtin_popcount(mask) <= k) {

tmp[s | mask] = 1;

} else {

// Try all subsets.

for (int c = mask; c; c = (c - 1) & mask)

if (__builtin_popcount(c) <= k) {

tmp[s | c] = 1;

}

if (tmp.back()) return d;

}

dp.swap(tmp);

}

return -1;

}

};

Variant 2:
dp[m] := min semesters to reach state m.
dp[m | c] = min{dp[m | c], dp[m] + 1}, if we can reach m | c from m.
This allows us to get rid of enumerate n semesters.
Time complexity: O(2^n*2^n) <– This will be much smaller in practice.
and can be reduced to O(3^n).
Space complexity: O(2^n)

C++

// Author: Huahua, 16 ms, 8.5 MB

class Solution {

public:

int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {

const int kInf = 1e9;

const int S = 1 << n;

vector<int> deps(n); // deps[i] = dependency mask for course i.

for (const auto& d : dependencies)

deps[d[1] - 1] |= 1 << (d[0] - 1);

// dp[m] := min semesters to reach state m.

vector<int> dp(S, kInf);

dp[0] = 0;

for (int s = 0; s < S; ++s) {

if (dp[s] == kInf) continue; // not reachable.

// Generate a mask of courses we can study under state s.

int mask = 0;

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

if (!(s & (1 << i)) && (s & deps[i]) == deps[i])

mask |= (1 << i);

// Prunning, take all.

if (__builtin_popcount(mask) <= k) {

dp[s | mask] = min(dp[s | mask], dp[s] + 1);

} else {

// Try all subsets.

for (int c = mask; c; c = (c - 1) & mask)

if (__builtin_popcount(c) <= k)

dp[s | c] = min(dp[s | c], dp[s] + 1);

}

// Early termination?

if (dp.back() != kInf) return dp.back();

}

return dp.back();

}

};

花花酱 LeetCode 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

By zxi on June 26, 2020

Given a weighted undirected connected graph with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional and weighted edge between nodes from_i and to_i. A minimum spanning tree (MST) is a subset of the edges of the graph that connects all vertices without cycles and with the minimum possible total edge weight.

Find all the critical and pseudo-critical edges in the minimum spanning tree (MST) of the given graph. An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. A pseudo-critical edge, on the other hand, is that which can appear in some MSTs but not all.

Note that you can return the indices of the edges in any order.

Example 1:

Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Output: [[0,1],[2,3,4,5]]
Explanation: The figure above describes the graph.
The following figure shows all the possible MSTs:

Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output.
The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.

Example 2:

Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output: [[],[0,1,2,3]]
Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.

Constraints:

2 <= n <= 100
1 <= edges.length <= min(200, n * (n - 1) / 2)
edges[i].length == 3
0 <= from_i < to_i < n
1 <= weight_i <= 1000
All pairs (from_i, to_i) are distinct.

Solution: Brute Force?

For each edge
1. exclude it and build a MST, cost increased => critical
2. for a non critical edge, force include it and build a MST, cost remains the same => pseudo critical

Proof of 2, if a non critical / non pseudo critical edge was added into the MST, the total cost must be increased. So if the cost remains the same, must be the other case. Since we know the edge is non-critical, so it has to be pseudo critical.

C++

// Author: Huahua

class UnionFind {

public:

explicit UnionFind(int n): p_(n), r_(n) { iota(begin(p_), end(p_), 0); } // e.g. p[i] = i

int Find(int x) { return p_[x] == x ? x : p_[x] = Find(p_[x]); }

bool Union(int x, int y) {

int rx = Find(x);

int ry = Find(y);

if (rx == ry) return false;

if (r_[rx] == r_[ry]) {

p_[rx] = ry;

++r_[ry];

} else if (r_[rx] > r_[ry]) {

p_[ry] = rx;

} else {

p_[rx] = ry;

}

return true;

}

private:

vector<int> p_, r_;

};

class Solution {

public:

vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {

// Record the original id.

for (int i = 0; i < edges.size(); ++i) edges[i].push_back(i);

// Sort edges by weight.

sort(begin(edges), end(edges), [&](const auto& e1, const auto& e2){

if (e1[2] != e2[2]) return e1[2] < e2[2];

return e1 < e2;

});

// Cost of MST, ex: edge to exclude, in: edge to include.

auto MST = [&](int ex = -1, int in = -1) -> int {

UnionFind uf(n);

int cost = 0;

int count = 0;

if (in >= 0) {

cost += edges[in][2];

uf.Union(edges[in][0], edges[in][1]);

count++;

}

for (int i = 0; i < edges.size(); ++i) {

if (i == ex) continue;

if (!uf.Union(edges[i][0], edges[i][1])) continue;

cost += edges[i][2];

++count;

}

return count == n - 1 ? cost : INT_MAX;

};

const int min_cost = MST();

vector<int> criticals;

vector<int> pseudos;

for (int i = 0; i < edges.size(); ++i) {

// Cost increased or can't form a tree.

if (MST(i) > min_cost) {

criticals.push_back(edges[i][3]);

} else if (MST(-1, i) == min_cost) {

pseudos.push_back(edges[i][3]);

}

return {criticals, pseudos};

}

};

花花酱 LeetCode 1483. Kth Ancestor of a Tree Node

By zxi on June 15, 2020

You are given a tree with n nodes numbered from 0 to n-1 in the form of a parent array where parent[i] is the parent of node i. The root of the tree is node 0.

Implement the function getKthAncestor(int node, int k) to return the k-th ancestor of the given node. If there is no such ancestor, return -1.

The k-th ancestor of a tree node is the k-th node in the path from that node to the root.

Example:

Input:
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

Output:

[null,1,0,-1]

Explanation: TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]); treeAncestor.getKthAncestor(3, 1); // returns 1 which is the parent of 3 treeAncestor.getKthAncestor(5, 2); // returns 0 which is the grandparent of 5 treeAncestor.getKthAncestor(6, 3); // returns -1 because there is no such ancestor

Constraints:

1 <= k <= n <= 5*10^4
parent[0] == -1 indicating that 0 is the root node.
0 <= parent[i] < n for all 0 < i < n
0 <= node < n
There will be at most 5*10^4 queries.

Solution: LogN ancestors

Build the tree from parent array
Traverse the tree
For each node stores up to logn ancestros, 2^0-th, 2^1-th, 2^2-th, …

When k comes in, each node take the highest bit h out, and query its 2^h’s ancestors with k <- (k – 2^h). There will be at most logk recursive query. When it ends? k == 0, we found the ancestors which is the current node. Or node == 0 and k > 0, we already at root which doesn’t have any ancestors so return -1.

Time complexity:
Construction: O(nlogn)
Query: O(logk)

Space complexity:
O(nlogn)

C++

// Author: Huahua

class TreeAncestor {

public:

TreeAncestor(int n, vector<int>& parent):

g_(n), a_(n) {

for (int i = 1; i < n; ++i) g_[parent[i]].push_back(i);

vector<int> path;

dfs(0, path);

}

int getKthAncestor(int node, int k) {

if (k == 0) return node;

if (node == 0 && k > 0) return -1;

int l = min(31ul - __builtin_clz(k), a_[node].size() - 1);

return getKthAncestor(a_[node][l], k - (1 << l));

}

private:

vector<vector<int>> g_, a_;

void dfs(int node, vector<int>& path) {

for (int i = 1; i <= path.size(); i *= 2)

a_[node].push_back(path[path.size() - i]);

path.push_back(node);

for (int c : g_[node]) dfs(c, path);

path.pop_back();

}

};

DP method

C++

// Author: Huahua

class TreeAncestor {

public:

TreeAncestor(int n, vector<int>& parent):

max_level_(32 - __builtin_clz(n)),

dp_(max_level_, vector<int>(n)) {

dp_[0] = parent;

for (int i = 1; i < max_level_; ++i)

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

dp_[i][j] = dp_[i - 1][j] == -1 ? -1 : dp_[i - 1][dp_[i - 1][j]];

}

int getKthAncestor(int node, int k) {

for (int i = 0; i < max_level_ && node != -1; ++i)

if (k & (1 << i))

node = dp_[i][node];

return node;

}

private:

const int max_level_;

vector<vector<int>> dp_;

};

Solution 2: Binary Search

credit: Ziwu Zhou

Construction: O(n)

Traverse the tree in post order, for each node record its depth and id (visiting order).
For each depth, store all the nodes and their ids.

Query: O(logn)

Get the depth and id of the node, if k > d, return -1.
Use binary search to find the first node at depth[d – k] that has a id greater than the query’s one That node is the k-th ancestor of the node.

C++

// Author: Huahua

class TreeAncestor {

public:

TreeAncestor(int n, vector<int>& parent): g_(n), nodes_(n), levels_(n) {

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

g_[parent[i]].push_back(i);

int id = 0;

dfs(0, 0, id);

}

int getKthAncestor(int node, int k) {

const auto [d, id] = nodes_[node];

if (k > d) return -1;

const auto& ns = levels_[d - k];

return upper_bound(begin(ns), end(ns), pair{id, -1})->second;

}

private:

void dfs(int node, int depth, int& id) {

for (int c : g_[node]) dfs(c, depth + 1, ++id);

levels_[depth].emplace_back(id, node);

nodes_[node] = {depth, id};

}

vector<vector<int>> g_; // p -> {{child}}

vector<vector<pair<int, int>>> levels_; // depth -> {{id, node}}

vector<pair<int, int>> nodes_; // node -> {depth, id}

};