Huahua’s Tech Road

花花酱 LeetCode 1569. Number of Ways to Reorder Array to Get Same BST

By zxi on August 30, 2020

Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.

For example, given nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.

Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums.

Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [2,1,3]
Output: 1
Explanation: We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.

Example 2:

Input: nums = [3,4,5,1,2]
Output: 5
Explanation: The following 5 arrays will yield the same BST: 
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: There are no other orderings of nums that will yield the same BST.

Example 4:

Input: nums = [3,1,2,5,4,6]
Output: 19

Example 5:

Input: nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]
Output: 216212978
Explanation: The number of ways to reorder nums to get the same BST is 3216212999. Taking this number modulo 10^9 + 7 gives 216212978.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= nums.length
All integers in nums are distinct.

Solution: Recursion + Combinatorics

For a given root (first element of the array), we can split the array into left children (nums[i] < nums[0]) and right children (nums[i] > nums[0]). Assuming there are l nodes for the left and r nodes for the right. We have C(l + r, l) different ways to insert l elements into a (l + r) sized array. Within node l / r nodes, we have ways(left) / ways(right) different ways to re-arrange those nodes. So the total # of ways is:
C(l + r, l) * ways(l) * ways(r)
Don’t forget to minus one for the final answer.

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

C++

class Solution {

public:

int numOfWays(vector<int>& nums) {

const int n = nums.size();

const int kMod = 1e9 + 7;

vector<vector<int>> cnk(n + 1, vector<int>(n + 1, 1));

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

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

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

function<int(vector<int>)> trees = [&](const vector<int>& nums) {

const int n = nums.size();

if (n <= 2) return 1;

vector<int> left;

vector<int> right;

for (int i = 1; i < nums.size(); ++i)

if (nums[i] < nums[0]) left.push_back(nums[i]);

else right.push_back(nums[i]);

long ans = cnk[n - 1][left.size()];

ans = (ans * trees(left)) % kMod;

ans = (ans * trees(right)) % kMod;

return static_cast<int>(ans);

};

return trees(nums) - 1;

}

};

python3

class Solution:

def numOfWays(self, nums: List[int]) -> int:

def ways(nums):

if len(nums) <= 2: return 1

l = [x for x in nums if x < nums[0]]

r = [x for x in nums if x > nums[0]]

return comb(len(l) + len(r), len(l)) * ways(l) * ways(r)

return (ways(nums) - 1) % (10**9 + 7)

花花酱 LeetCode 1568. Minimum Number of Days to Disconnect Island

By zxi on August 30, 2020

Given a 2D grid consisting of 1s (land) and 0s (water). An island is a maximal 4-directionally (horizontal or vertical) connected group of 1s.

The grid is said to be connected if we have exactly one island, otherwise is said disconnected.

In one day, we are allowed to change any single land cell (1) into a water cell (0).

Return the minimum number of days to disconnect the grid.

Example 1:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
Output: 2
Explanation: We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.

Example 2:

Input: grid = [[1,1]]
Output: 2
Explanation: Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.

Example 3:

Input: grid = [[1,0,1,0]]
Output: 0

Example 4:

Input: grid = [[1,1,0,1,1],
               [1,1,1,1,1],
               [1,1,0,1,1],
               [1,1,0,1,1]]
Output: 1

Example 5:

Input: grid = [[1,1,0,1,1],
               [1,1,1,1,1],
               [1,1,0,1,1],
               [1,1,1,1,1]]
Output: 2

Constraints:

1 <= grid.length, grid[i].length <= 30
grid[i][j] is 0 or 1.

Solution: Brute Force

We need at most two days to disconnect an island.
1. check if we have more than one islands. (0 days)
2. For each 1 cell, change it to 0 and check how many islands do we have. (1 days)
3. Otherwise, 2 days

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

C++

class Solution {

public:

int minDays(vector<vector<int>>& grid) {

const int n = grid.size();

const int m = grid[0].size();

const vector<int> dirs{0, 1, 0, -1, 0};

vector<int> seen(n * m);

function<void(int, int)> dfs = [&](int x, int y) {

if (x < 0 || y < 0 || x >= m || y >= n) return;

if (grid[y][x] == 0) return;

if (seen[y * m + x]++) return;

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

dfs(x + dirs[i], y + dirs[i + 1]);

};

function<bool()> disconnected = [&]() {

int count = 0;

fill(begin(seen), end(seen), 0);

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

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

if (grid[y][x] && !seen[y * m + x]) {

dfs(x, y);

if (++count > 1) return true;

}

return false;

};

if (disconnected()) return 0;

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

for (int x = 0; x < m; ++x) {

if (!grid[y][x]) continue;

grid[y][x] = 0;

if (disconnected()) return 1;

grid[y][x] = 1;

}

return 2;

}

};

花花酱 LeetCode 1567. Maximum Length of Subarray With Positive Product

By zxi on August 29, 2020

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

Example 1:

Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.

Example 2:

Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

Example 3:

Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

Example 4:

Input: nums = [-1,2]
Output: 1

Example 5:

Input: nums = [1,2,3,5,-6,4,0,10]
Output: 4

Constraints:

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Solution: DP

p[i] := max length of positive products ends with arr[i]
n[i] := max length of negtive products ends with arr[i]

if arr[i] > 0: p[i] = p[i – 1] + 1, n[i] = n[i] + 1 if n[i] else 0
if arr[i] < 0: p[i] = n[i – 1] + 1 if n[i – 1] else 0, n[i] = p[i – 1] + 1
if arr[i] == 0: p[i] = n[i] = 0
ans = max(p[i])

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

C++

class Solution {

public:

int getMaxLen(vector<int>& nums) {

int p = 0;

int n = 0;

int ans = 0;

for (int x : nums) {

if (x > 0) {

++p;

if (n) ++n;

} else if (x < 0) {

int tp = p;

p = n ? n + 1 : 0;

n = tp + 1;

} else {

p = n = 0;

}

ans = max(ans, p);

}

return ans;

}

};

花花酱 LeetCode 1566. Detect Pattern of Length M Repeated K or More Times

By zxi on August 29, 2020

Given an array of positive integers arr, find a pattern of length m that is repeated k or more times.

A pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.

Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.

Example 1:

Input: arr = [1,2,4,4,4,4], m = 1, k = 3
Output: true
Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.

Example 2:

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
Output: true
Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.

Example 3:

Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.

Example 4:

Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: Notice that the pattern (1,2) exists twice but not consecutively, so it doesn't count.

Example 5:

Input: arr = [2,2,2,2], m = 2, k = 3
Output: false
Explanation: The only pattern of length 2 is (2,2) however it's repeated only twice. Notice that we do not count overlapping repetitions.

Constraints:

2 <= arr.length <= 100
1 <= arr[i] <= 100
1 <= m <= 100
2 <= k <= 100

Solution 1: Brute Force

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

C++

class Solution {

public:

bool containsPattern(vector<int>& arr, int m, int k) {

const int n = arr.size();

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

bool valid = true;

for (int j = 1; j < k && valid; ++j)

for (int p = 0; p < m && valid; ++p)

if (arr[i + j * m + p] != arr[i + p])

valid = false;

if (valid) return true;

}

return false;

}

};

Solution 2: Shift and count

Since we need k consecutive subarrays, we can compare arr[i] with arr[i + m], if they are the same, increase the counter, otherwise reset the counter. If the counter reaches (k – 1) * m, it means we found k consecutive subarrays of length m.

ex1: arr = [1,2,4,4,4,4], m = 1, k = 3
i arr[i], arr[i + m] counter
0 1. 2. 0
0 2. 4. 0
0 4. 4. 1
0 4. 4. 2. <– found

ex2: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
i arr[i], arr[i + m] counter
0 1. 1. 1
0 2. 2. 2 <– found

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

C++

class Solution {

public:

bool containsPattern(vector<int>& arr, int m, int k) {

const int n = arr.size();

int count = 0;

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

if (arr[i] == arr[i + m]) {

if (++count == (k - 1) * m) return true;

} else {

count = 0;

}

return false;

}

};

花花酱 LeetCode 1563. Stone Game V

By zxi on August 23, 2020

There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

In each round of the game, Alice divides the row into two non-empty rows (i.e. left row and right row), then Bob calculates the value of each row which is the sum of the values of all the stones in this row. Bob throws away the row which has the maximum value, and Alice’s score increases by the value of the remaining row. If the value of the two rows are equal, Bob lets Alice decide which row will be thrown away. The next round starts with the remaining row.

The game ends when there is only one stone remaining. Alice’s is initially zero.

Return the maximum score that Alice can obtain.

Example 1:

Input: stoneValue = [6,2,3,4,5,5]
Output: 18
Explanation: In the first round, Alice divides the row to [6,2,3], [4,5,5]. The left row has the value 11 and the right row has value 14. Bob throws away the right row and Alice's score is now 11.
In the second round Alice divides the row to [6], [2,3]. This time Bob throws away the left row and Alice's score becomes 16 (11 + 5).
The last round Alice has only one choice to divide the row which is [2], [3]. Bob throws away the right row and Alice's score is now 18 (16 + 2). The game ends because only one stone is remaining in the row.

Example 2:

Input: stoneValue = [7,7,7,7,7,7,7]
Output: 28

Example 3:

Input: stoneValue = [4]
Output: 0

Constraints:

1 <= stoneValue.length <= 500
1 <= stoneValue[i] <= 10^6

Solution: Range DP + Prefix Sum

dp[l][r] := max store Alice can get from range [l, r]
sum_l = sum(l, k), sum_r = sum(k + 1, r)
dp[l][r] = max{
dp[l][k] + sum_l if sum_l < sum_r
dp[k+1][r] + sum_r if sum_r < sum_l
max(dp[l][k], dp[k+1][r])) + sum_l if sum_l == sum_r)
} for k in [l, r)

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

C++

class Solution {

public:

int stoneGameV(vector<int>& stoneValue) {

const int n = stoneValue.size();

vector<int> sums(n + 1);

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

sums[i + 1] = sums[i] + stoneValue[i];

vector<vector<int>> cache(n, vector<int>(n, -1));

// max value alice can get from range [l, r]

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

if (l == r) return 0;

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

if (ans != -1) return ans;

for (int k = l; k < r; ++k) {

// left: [l, k], right: [k + 1, r]

int sum_l = sums[k + 1] - sums[l];

int sum_r = sums[r + 1] - sums[k + 1];

if (sum_l > sum_r)

ans = max(ans, sum_r + dp(k + 1, r));

else if (sum_l < sum_r)

ans = max(ans, sum_l + dp(l, k));

else

ans = max(ans, sum_l + max(dp(l, k), dp(k + 1, r)));

}

return ans;

};

return dp(0, n - 1);

}

};

Huahua's Tech Road

花花酱 LeetCode 1569. Number of Ways to Reorder Array to Get Same BST

Solution: Recursion + Combinatorics

C++

python3

花花酱 LeetCode 1568. Minimum Number of Days to Disconnect Island

Solution: Brute Force

C++

花花酱 LeetCode 1567. Maximum Length of Subarray With Positive Product

Solution: DP

C++

花花酱 LeetCode 1566. Detect Pattern of Length M Repeated K or More Times

Solution 1: Brute Force

C++

Solution 2: Shift and count

C++

花花酱 LeetCode 1563. Stone Game V

Solution: Range DP + Prefix Sum

C++