Posts tagged as “hard”

花花酱 LeetCode 1879. Minimum XOR Sum of Two Arrays

By zxi on August 7, 2021

You are given two integer arrays nums1 and nums2 of length n.

The XOR sum of the two integer arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) (0-indexed).

For example, the XOR sum of [1,2,3] and [3,2,1] is equal to (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4.

Rearrange the elements of nums2 such that the resulting XOR sum is minimized.

Return the XOR sum after the rearrangement.

Example 1:

Input: nums1 = [1,2], nums2 = [2,3]
Output: 2
Explanation: Rearrange nums2 so that it becomes [3,2].
The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.

Example 2:

Input: nums1 = [1,0,3], nums2 = [5,3,4]
Output: 8
Explanation: Rearrange nums2 so that it becomes [5,4,3]. 
The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.

Constraints:

n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 10⁷

Solution: DP / Permutation to combination

dp[s] := min xor sum by using a subset of nums2 (presented by a binary string s) xor with nums1[0:|s|].

Time complexity: O(n*2ⁿ)
Space complexity: O(2ⁿ)

C++

// Author: Huahua

class Solution {

public:

int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {

const int n = nums1.size();

vector<int> dp(1 << n, INT_MAX);

dp[0] = 0;

for (int s = 0; s < 1 << n; ++s) {

int index = __builtin_popcount(s);

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

if (s & (1 << i)) continue;

dp[s | (1 << i)] = min(dp[s | (1 << i)],

dp[s] + (nums1[index] ^ nums2[i]));

}

return dp.back();

}

};

花花酱 LeetCode 1872. Stone Game VIII

By zxi on August 5, 2021

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

There are n stones arranged in a row. On each player’s turn, while the number of stones is more than one, they will do the following:

Choose an integer x > 1, and remove the leftmost x stones from the row.
Add the sum of the removed stones’ values to the player’s score.
Place a new stone, whose value is equal to that sum, on the left side of the row.

The game stops when only one stone is left in the row.

The score difference between Alice and Bob is (Alice's score - Bob's score). Alice’s goal is to maximize the score difference, and Bob’s goal is the minimize the score difference.

Given an integer array stones of length n where stones[i] represents the value of the i^th stone from the left, return the score difference between Alice and Bob if they both play optimally.

Example 1:

Input: stones = [-1,2,-3,4,-5]
Output: 5
Explanation:
- Alice removes the first 4 stones, adds (-1) + 2 + (-3) + 4 = 2 to her score, and places a stone of
  value 2 on the left. stones = [2,-5].
- Bob removes the first 2 stones, adds 2 + (-5) = -3 to his score, and places a stone of value -3 on
  the left. stones = [-3].
The difference between their scores is 2 - (-3) = 5.

Example 2:

Input: stones = [7,-6,5,10,5,-2,-6]
Output: 13
Explanation:
- Alice removes all stones, adds 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 to her score, and places a
  stone of value 13 on the left. stones = [13].
The difference between their scores is 13 - 0 = 13.

Example 3:

Input: stones = [-10,-12]
Output: -22
Explanation:
- Alice can only make one move, which is to remove both stones. She adds (-10) + (-12) = -22 to her
  score and places a stone of value -22 on the left. stones = [-22].
The difference between their scores is (-22) - 0 = -22.

Constraints:

n == stones.length
2 <= n <= 10⁵
-10⁴ <= stones[i] <= 10⁴

Solution: Prefix Sum + DP

Note: Naive DP (min-max) takes O(n²) which leads to TLE. The key of this problem is that each player takes k stones, but put their sum back as a new stone, so you can assume all the original stones are still there, but opponent has to start from the k+1 th stone.

Let dp[i] denote the max score diff that current player can achieve by taking stones[0~i] (or equivalent)

dp[n-1] = sum(A[0~n-1]) // Alice takes all the stones.
dp[n-2] = sum(A[0~n-2]) – (A[n-1] + sum(A[0~n-2])) = sum(A[0~n-2]) – dp[n-1] // Alice takes n-1 stones, Bob take the last one (A[n-1]) + put-back-stone.
dp[n-3] = sum(A[0~n-3]) – max(dp[n-2], dp[n-1]) // Alice takes n-2 stones, Bob has two options (takes n-1 stones or takes n stones)
…
dp[0] = A[0] – max(dp[n-1], dp[n-1], …, dp[1]) // Alice takes the first stone, Bob has n-1 options.

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

C++

// Author: Huahua

class Solution {

public:

int stoneGameVIII(vector<int>& stones) {

const int n = stones.size();

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

stones[i] += stones[i - 1];

int ans = stones.back(); // take all the stones.

for (int i = n - 2; i > 0; --i)

ans = max(ans, stones[i] - ans);

return ans;

}

};

花花酱 LeetCode 1866. Number of Ways to Rearrange Sticks With K Sticks Visible

By zxi on August 4, 2021

There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.

For example, if the sticks are arranged [1,3,2,5,4], then the sticks with lengths 1, 3, and 5 are visible from the left.

Given n and k, return the number of such arrangements. Since the answer may be large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 3, k = 2
Output: 3
Explanation: [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible.
The visible sticks are underlined.

Example 2:

Input: n = 5, k = 5
Output: 1
Explanation: [1,2,3,4,5] is the only arrangement such that all 5 sticks are visible.
The visible sticks are underlined.

Example 3:

Input: n = 20, k = 11
Output: 647427950
Explanation: There are 647427950 (mod 10⁹+ 7) ways to rearrange the sticks such that exactly 11 sticks are visible.

Constraints:

1 <= n <= 1000
1 <= k <= n

Solution: DP

dp(n, k) = dp(n – 1, k – 1) + (n-1) * dp(n-1, k)

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

C++

// Author: Huahua

class Solution {

public:

int rearrangeSticks(int n, int k) {

constexpr int kMod = 1e9 + 7;

vector<vector<long>> dp(n + 1, vector<long>(k + 1));

for (int j = 1; j <= k; ++j) {

dp[j][j] = 1;

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

dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1)) % kMod;

}

return dp[n][k];

}

};

Python3

# Author: Huahua

class Solution:

@lru_cache(maxsize=None)

def rearrangeSticks(self, n: int, k: int) -> int:

if k == 0: return 0

if k == n or n <= 2: return 1

return (self.rearrangeSticks(n - 1, k - 1) +

(n - 1) * self.rearrangeSticks(n - 1, k)) % (10**9 + 7)

花花酱 LeetCode 1857. Largest Color Value in a Directed Graph

By zxi on May 29, 2021

There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n - 1.

You are given a string colors where colors[i] is a lowercase English letter representing the color of the i^th node in this graph (0-indexed). You are also given a 2D array edges where edges[j] = [a_j, b_j] indicates that there is a directed edge from node a_j to node b_j.

A valid path in the graph is a sequence of nodes x₁ -> x₂ -> x₃ -> ... -> x_k such that there is a directed edge from x_i to x_i+1 for every 1 <= i < k. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path.

Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.

Example 1:

Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
Explanation: The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a" (red in the above image).

Example 2:

Input: colors = "a", edges = [[0,0]]
Output: -1
Explanation: There is a cycle from 0 to 0.

Constraints:

n == colors.length
m == edges.length
1 <= n <= 10⁵
0 <= m <= 10⁵
colors consists of lowercase English letters.
0 <= a_j, b_j < n

Solution: Topological Sorting

freq[n][c] := max freq of color c after visiting node n.

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

python

class Solution:

def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:

INF = 1e9

n = len(colors)

g = [[] for _ in range(n)]

for u, v in edges:

g[u].append(v)

visited = [0] * n

freq = [[0] * 26 for _ in range(n)]

def dfs(u: int) -> int:

idx = ord(colors[u]) - ord('a')

if not visited[u]:

visited[u] = 1 # visiting

for v in g[u]:

if (dfs(v) == INF):

return INF

for c in range(26):

freq[u][c] = max(freq[u][c], freq[v][c])

freq[u][idx] += 1

visited[u] = 2 # done

return freq[u][idx] if visited[u] == 2 else INF

ans = 0

for u in range(n):

ans = max(ans, dfs(u))

if ans == INF: break

return -1 if ans == INF else ans

花花酱 LeetCode 1851. Minimum Interval to Include Each Query

By zxi on May 8, 2021

You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] describes the i^th interval starting at left_i and ending at right_i (inclusive). The size of an interval is defined as the number of integers it contains, or more formally right_i - left_i + 1.

You are also given an integer array queries. The answer to the j^th query is the size of the smallest interval i such that left_i <= queries[j] <= right_i. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

Example 1:

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.

Example 2:

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
- Query = 19: None of the intervals contain 19. The answer is -1.
- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.

Constraints:

1 <= intervals.length <= 10⁵
1 <= queries.length <= 10⁵
intervals[i].length == 2
1 <= left_i <= right_i <= 10⁷
1 <= queries[j] <= 10⁷

Solution: Offline Processing + Priority Queue

Sort intervals by right in descending order, sort queries in descending. Add valid intervals into the priority queue (or treeset) ordered by size in ascending order. Erase invalid ones. The first one (if any) will be the one with the smallest size that contains the current query.

Time complexity: O(nlogn + mlogm + mlogn)
Space complexity: O(m + n)

C++

// Author: Huahua

class Solution {

public:

vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {

const int n = intervals.size();

const int m = queries.size();

sort(begin(intervals), end(intervals), [](const auto& a, const auto& b){

return a[1] > b[1];

});

vector<pair<int, int>> qs(m); // {query, i}

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

qs[i] = {queries[i], i};

sort(rbegin(qs), rend(qs));

vector<int> ans(m);

int j = 0;

priority_queue<pair<int, int>> pq; // {-size, left}

for (const auto& [query, i] : qs) {

while (j < n && intervals[j][1] >= query) {

pq.emplace(-(intervals[j][1] - intervals[j][0] + 1),

intervals[j][0]);

++j;

}

while (!pq.empty() && pq.top().second > query)

pq.pop();

ans[i] = pq.empty() ? -1 : -pq.top().first;

}

return ans;

}

};