Huahua’s Tech Road

花花酱 LeetCode 1655. Distribute Repeating Integers

By zxi on November 14, 2020

You are given an array of n integers, nums, where there are at most 50 unique values in the array. You are also given an array of m customer order quantities, quantity, where quantity[i] is the amount of integers the i^th customer ordered. Determine if it is possible to distribute nums such that:

The i^th customer gets exactly quantity[i] integers,
The integers the i^th customer gets are all equal, and
Every customer is satisfied.

Return true if it is possible to distribute nums according to the above conditions.

Example 1:

Input: nums = [1,2,3,4], quantity = [2]
Output: false
Explanation: The 0th customer cannot be given two different integers.

Example 2:

Input: nums = [1,2,3,3], quantity = [2]
Output: true
Explanation: The 0th customer is given [3,3]. The integers [1,2] are not used.

Example 3:

Input: nums = [1,1,2,2], quantity = [2,2]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [2,2].

Example 4:

Input: nums = [1,1,2,3], quantity = [2,2]
Output: false
Explanation: Although the 0th customer could be given [1,1], the 1st customer cannot be satisfied.

Example 5:

Input: nums = [1,1,1,1,1], quantity = [2,3]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [1,1,1].

Constraints:

n == nums.length
1 <= n <= 10⁵
1 <= nums[i] <= 1000
m == quantity.length
1 <= m <= 10
1 <= quantity[i] <= 10⁵
There are at most 50 unique values in nums.

Solution1: Backtracking

Time complexity: O(|vals|^m)
Space complexity: O(|vals| + m)

C++

// Author: Huahua

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

unordered_map<int, int> m;

for (int x : nums) ++m[x];

vector<int> cnt;

for (const auto& [x, c] : m) cnt.push_back(c);

const int q = quantity.size();

const int n = cnt.size();

function<bool(int)> dfs = [&](int d) {

if (d == q) return true;

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

if (cnt[i] >= quantity[d]) {

cnt[i] -= quantity[d];

if (dfs(d + 1)) return true;

cnt[i] += quantity[d];

}

return false;

};

sort(rbegin(cnt), rend(cnt));

sort(rbegin(quantity), rend(quantity));

return dfs(0);

}

};

Solution 2: Bitmask + all subsets

dp(mask, i) := whether we can distribute to a subset of customers represented as a bit mask, using the i-th to (n-1)-th numbers.

Time complexity: O(2^m * m * |vals|) = O(2^10 * 10 * 50)
Space complexity: O(2^m * |vals|)

C++

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

vector<int> cnt;

unordered_map<int, int> freq;

for (int x : nums) ++freq[x];

for (const auto& [x, f] : freq) cnt.push_back(f);

const int n = cnt.size();

const int m = quantity.size();

vector<vector<optional<bool>>> cache(1 << m, vector<optional<bool>>(n));

vector<int> sums(1 << m);

for (int mask = 0; mask < 1 << m; ++mask)

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

if (mask & (1 << i))

sums[mask] += quantity[i];

function<bool(int, int)> dp = [&](int mask, int i) -> bool {

if (mask == 0) return true;

if (i == n) return false;

auto& ans = cache[mask][i];

if (ans.has_value()) return ans.value();

int cur = mask;

while (cur) {

if (sums[cur] <= cnt[i] && dp(mask ^ cur, i + 1)) {

ans = true;

return true;

}

cur = (cur - 1) & mask;

}

ans = dp(mask, i + 1);

return ans.value();

};

return dp((1 << m) - 1, 0);

}

};

Python3

# Author: Huahua

class Solution:

def canDistribute(self, nums: List[int],

quantity: List[int]) -> bool:

cnts = list(Counter(nums).values())

m = len(quantity)

n = len(cnts)

sums = [0] * (1 << m)

for mask in range(1 << m):

for i in range(m):

if mask & (1 << i): sums[mask] += quantity[i]

@lru_cache(None)

def dp(mask: int, i: int) -> bool:

if not mask: return True

if i < 0: return False

cur = mask

while cur:

if sums[cur] <= cnts[i] and dp(mask ^ cur, i - 1):

return True

cur = (cur - 1) & mask

return dp(mask, i - 1)

return dp((1 << m) - 1, n - 1)

Bottom up:

C++

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

vector<int> cnt;

unordered_map<int, int> freq;

for (int x : nums) ++freq[x];

for (const auto& [x, f] : freq) cnt.push_back(f);

const int n = cnt.size();

const int m = quantity.size();

vector<int> sums(1 << m);

for (int mask = 0; mask < 1 << m; ++mask)

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

if (mask & (1 << i))

sums[mask] += quantity[i];

// dp[mask][i] := use first i types to satisfy mask customers.

vector<vector<int>> dp(1 << m, vector<int>(n + 1));

dp[0][0] = 1;

for (int mask = 0; mask < 1 << m; ++mask)

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

dp[mask][i + 1] |= dp[mask][i];

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

if (sums[cur] <= cnt[i] && dp[mask ^ cur][i])

dp[mask][i + 1] = 1;

}

return dp[(1 << m) - 1][n];

}

};

花花酱 LeetCode 1654. Minimum Jumps to Reach Home

By zxi on November 14, 2020

A certain bug’s home is on the x-axis at position x. Help them get there from position 0.

The bug jumps according to the following rules:

It can jump exactly a positions forward (to the right).
It can jump exactly b positions backward (to the left).
It cannot jump backward twice in a row.
It cannot jump to any forbidden positions.

The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

Example 1:

Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output: 3
Explanation: 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.

Example 2:

Input: forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
Output: -1

Example 3:

Input: forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
Output: 2
Explanation: One jump forward (0 -> 16) then one jump backward (16 -> 7) will get the bug home.

Constraints:

1 <= forbidden.length <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000
All the elements in forbidden are distinct.
Position x is not forbidden.

Solution: BFS

Normal BFS with two tricks:
1. For each position, we need to track whether it’s reached via a forward jump or backward jump
2. How far should we go? If we don’t limit, it can go forever which leads to TLE/MLE. We can limit the distance to 2*max_jump, e.g. 4000, that’s maximum distance we can jump back to home in one shot.

Time complexity: O(max_distance * 2)
Space complexity: O(max_distance * 2)

C++

// Author: Huahua

class Solution {

public:

int minimumJumps(vector<int>& forbidden, int a, int b, int x) {

constexpr int kMaxPosition = 4000;

if (x == 0) return 0;

queue<pair<int, bool>> q{{{0, true}}};

unordered_set<int> seen1, seen2;

for (int f : forbidden) seen1.insert(f), seen2.insert(f);

seen1.insert(0);

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

auto [cur, forward] = q.front(); q.pop();

if (cur == x) return steps;

if (cur > kMaxPosition) continue; // no way to go back

if (seen1.insert(cur + a).second)

q.emplace(cur + a, true);

if (cur - b >= 0 && forward && seen2.insert(cur - b).second)

q.emplace(cur - b, false);

}

++steps;

}

return -1;

}

};

花花酱 LeetCode 1653. Minimum Deletions to Make String Balanced

By zxi on November 14, 2020

You are given a string s consisting only of characters 'a' and 'b'.

You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.

Return the minimum number of deletions needed to make s balanced.

Example 1:

Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").

Example 2:

Input: s = "bbaaaaabb"
Output: 2
Explanation: The only solution is to delete the first two characters.

Constraints:

1 <= s.length <= 10⁵
s[i] is 'a' or 'b'.

Solution: DP

dp[i][0] := min # of dels to make s[0:i] all ‘a’s;
dp[i][1] := min # of dels to make s[0:i] ends with 0 or mode ‘b’s

if s[i-1] == ‘a’:
dp[i + 1][0] = dp[i][0], dp[i + 1][1] = min(dp[i + 1][0], dp[i][1] + 1)
else:
dp[i + 1][0] = dp[i][0] + 1, dp[i + 1][1] = dp[i][1]

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

C++

// Author: Huahua

class Solution {

public:

int minimumDeletions(string s) {

// const int n = s.length();

// dp[i][0] := min # of dels to make s[0:i] all 'a's;

// dp[i][1] := min # of dels to make s[0:i] ends with 0+ 'b's

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

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

// if (s[i] == 'a') {

// dp[i + 1][0] = dp[i][0];

// dp[i + 1][1] = min(dp[i + 1][0], dp[i][1] + 1);

// } else {

// dp[i + 1][0] = dp[i][0] + 1;

// dp[i + 1][1] = dp[i][1];

// }

// return min(dp[n][0], dp[n][1]);

int a = 0, b = 0;

for (char c : s) {

if (c == 'a') b = min(a, b + 1);

else ++a;

}

return min(a, b);

}

};

花花酱 LeetCode 1652. Defuse the Bomb

By zxi on November 14, 2020

You have a bomb to defuse, and your time is running out! Your informer will provide you with a circular array code of length of n and a key k.

To decrypt the code, you must replace every number. All the numbers are replaced simultaneously.

If k > 0, replace the i^th number with the sum of the next k numbers.
If k < 0, replace the i^th number with the sum of the previous k numbers.
If k == 0, replace the i^th number with 0.

As code is circular, the next element of code[n-1] is code[0], and the previous element of code[0] is code[n-1].

Given the circular array code and an integer key k, return the decrypted code to defuse the bomb!

Example 1:

Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Each number is replaced by the sum of the next 3 numbers. The decrypted code is [7+1+4, 1+4+5, 4+5+7, 5+7+1]. Notice that the numbers wrap around.

Example 2:

Input: code = [1,2,3,4], k = 0
Output: [0,0,0,0]
Explanation: When k is zero, the numbers are replaced by 0.

Example 3:

Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: The decrypted code is [3+9, 2+3, 4+2, 9+4]. Notice that the numbers wrap around again. If k is negative, the sum is of the previous numbers.

Constraints:

n == code.length
1 <= n <= 100
1 <= code[i] <= 100
-(n - 1) <= k <= n - 1

Solution 1: Simulation

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

C++

class Solution {

public:

vector<int> decrypt(vector<int>& code, int k) {

const int n = code.size();

vector<int> ans(n);

int sign = k > 0 ? 1 : -1;

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

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

ans[i] += code[(i + j * sign + n) % n];

return ans;

}

};

花花酱 1095. Find in Mountain Array – EP369

By zxi on November 13, 2020

(This problem is an interactive problem.)

You may recall that an array A is a mountain array if and only if:

A.length >= 3
There exists some i with 0 < i < A.length - 1 such that:
- A[0] < A[1] < ... A[i-1] < A[i]
- A[i] > A[i+1] > ... > A[A.length - 1]

Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index doesn’t exist, return -1.

You can’t access the mountain array directly. You may only access the array using a MountainArray interface:

MountainArray.get(k) returns the element of the array at index k (0-indexed).
MountainArray.length() returns the length of the array.

Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example 1:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

Example 2:

Input: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.

Constraints:

3 <= mountain_arr.length() <= 10000
0 <= target <= 10^9
0 <= mountain_arr.get(index) <= 10^9

Solution: Binary Search

Find the peak index of the mountain array using binary search.
Perform two binary searches in two sorted subarrays (ascending one and descending one)

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

C++

class Solution {

public:

int findInMountainArray(int target, MountainArray &mountainArr) {

const int n = mountainArr.length();

auto binary_search = [&](int l, int r, function<bool(int)> cond) {

while (l < r) {

int m = l + (r - l) / 2;

if (cond(m)) r = m;

else l = m + 1;

}

return l;

};

int p = binary_search(0, n - 1, [&](int i) -> bool {

return mountainArr.get(i) > mountainArr.get(i + 1);

});

// if (target > mountainArr.get(p)) return -1;

// if (target == mountainArr.get(p)) return p;

int l = binary_search(0, p, [&](int i) -> bool {

return mountainArr.get(i) >= target;

});

if (mountainArr.get(l) == target) return l;

int r = binary_search(p, n - 1, [&](int i) -> bool {

return mountainArr.get(i) <= target;

});

if (mountainArr.get(r) == target) return r;

return -1;

}

};

python3

class Solution:

def findInMountainArray(self, target: int, arr: 'MountainArray') -> int:

def binary_search(l, r, cond):

while l < r:

m = l + (r - l) // 2

if cond(m): r = m

else: l = m + 1

return l

n = arr.length()

p = binary_search(0, n - 1, lambda i: arr.get(i) > arr.get(i + 1))

l = binary_search(0, p, lambda i: arr.get(i) >= target)

if arr.get(l) == target: return l

r = binary_search(p, n - 1, lambda i: arr.get(i) <= target)

if arr.get(r) == target: return r

return -1

Huahua's Tech Road

花花酱 LeetCode 1655. Distribute Repeating Integers

Solution1: Backtracking

C++

Solution 2: Bitmask + all subsets

C++

Python3

C++

花花酱 LeetCode 1654. Minimum Jumps to Reach Home

Solution: BFS

C++

花花酱 LeetCode 1653. Minimum Deletions to Make String Balanced

Solution: DP

C++

花花酱 LeetCode 1652. Defuse the Bomb

Solution 1: Simulation

C++

花花酱 1095. Find in Mountain Array – EP369

Solution: Binary Search

C++

python3