Huahua’s Tech Road

花花酱 LeetCode 1675. Minimize Deviation in Array

By zxi on November 29, 2020

You are given an array nums of n positive integers.

You can perform two types of operations on any element of the array any number of times:

If the element is even, divide it by 2.
- For example, if the array is [1,2,3,4], then you can do this operation on the last element, and the array will be [1,2,3,2].
If the element is odd, multiply it by 2.
- For example, if the array is [1,2,3,4], then you can do this operation on the first element, and the array will be [2,2,3,4].

The deviation of the array is the maximum difference between any two elements in the array.

Return the minimum deviation the array can have after performing some number of operations.

Example 1:

Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

Example 2:

Input: nums = [4,1,5,20,3]
Output: 3
Explanation: You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3.

Example 3:

Input: nums = [2,10,8]
Output: 3

Constraints:

n == nums.length
2 <= n <= 10⁵
1 <= nums[i] <= 10⁹

Solution: Priority Queue

If we double an odd number it becomes an even number, then we can only divide it by two which gives us back the original number. So we can pre-double all the odd numbers and only do division in the following process.

We push all numbers including pre-doubled odd ones onto a priority queue, and track the difference between the largest and smallest number.

Each time, we pop the largest number out and divide it by two then put it back to the priority queue, until the largest number becomes odd. We can not discard it and divide any other smaller numbers by two will only increase the max difference, so we can stop here.

ex1: [3, 5, 8] => [6, 8, 10] (pre-double) => [5, 6, 8] => [4, 5, 6] => [3, 4, 5] max diff is 5 – 3 = 2
ex2: [4,1,5,20,3] => [2, 4, 6, 10, 20] (pre-double) => [2, 4, 6, 10] => [2, 4, 5, 6] => [2,3,4,5] max diff = 5-2 = 3

Time complexity: O(n*logm*logn)
Space complexity: O(n)

C++/Set

class Solution {

public:

int minimumDeviation(vector<int>& nums) {

set<int> s;

for (int x : nums)

s.insert(x & 1 ? x * 2 : x);

int ans = *rbegin(s) - *begin(s);

while (*rbegin(s) % 2 == 0) {

s.insert(*rbegin(s) / 2);

s.erase(*rbegin(s));

ans = min(ans, *rbegin(s) - *begin(s));

}

return ans;

}

};

C++/PQ

class Solution {

public:

int minimumDeviation(vector<int>& nums) {

priority_queue<int> q;

int lo = INT_MAX;

for (int x : nums) {

x = x & 1 ? x * 2 : x;

q.push(x);

lo = min(lo, x);

}

int ans = q.top() - lo;

while (q.top() % 2 == 0) {

int x = q.top(); q.pop();

q.push(x / 2);

lo = min(lo, x / 2);

ans = min(ans, q.top() - lo);

}

return ans;

}

};

花花酱 LeetCode 1674. Minimum Moves to Make Array Complementary

By zxi on November 29, 2020

You are given an integer array nums of even length n and an integer limit. In one move, you can replace any integer from nums with another integer between 1 and limit, inclusive.

The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n - 1 - i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n - 1 - i] = 5.

Return the minimum number of moves required to make nums complementary.

Example 1:

Input: nums = [1,2,4,3], limit = 4
Output: 1
Explanation: In 1 move, you can change nums to [1,2,2,3] (underlined elements are changed).
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.

Example 2:

Input: nums = [1,2,2,1], limit = 2
Output: 2
Explanation: In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit.

Example 3:

Input: nums = [1,2,1,2], limit = 2
Output: 0
Explanation: nums is already complementary.

Constraints:

n == nums.length
2 <= n <= 10⁵
1 <= nums[i] <= limit <= 10⁵
n is even.

Solution: Sweep Line / Prefix Sum

Let a = min(nums[i], nums[n-i-1]), b = max(nums[i], nums[n-i-1])
The key to this problem is how many moves do we need to make a + b == T.

if 2 <= T < a + 1, two moves, lower both a and b.
if a +1 <= T < a + b, one move, lower b
if a + b == T, zero move
if a + b + 1 <= T < b + limit + 1, one move, increase a
if b + limit + 1 <= T <= 2*limit, two moves, increase both a and b.

Time complexity: O(n + limit) or O(nlogn) if limit >>n
Space complexity: O(limit) or O(n)

C++

// Author: Huahua

class Solution {

public:

int minMoves(vector<int>& nums, int limit) {

const int n = nums.size();

vector<int> delta(limit * 2 + 2);

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

const int a = min(nums[i], nums[n - i - 1]);

const int b = max(nums[i], nums[n - i - 1]);

delta[2] += 2; // dec a, dec b

--delta[a + 1]; // dec a

--delta[a + b]; // no op

++delta[a + b + 1]; // inc a

++delta[b + limit + 1]; // inc a, inc b

}

int ans = n;

for (int t = 2, cur = 0; t <= limit * 2; ++t) {

cur += delta[t];

ans = min(ans, cur);

}

return ans;

}

};

花花酱 LeetCode 1673. Find the Most Competitive Subsequence

By zxi on November 29, 2020

Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k.

An array’s subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array.

We define that a subsequence a is more competitive than a subsequence b (of the same length) if in the first position where a and b differ, subsequence a has a number less than the corresponding number in b. For example, [1,3,4] is more competitive than [1,3,5] because the first position they differ is at the final number, and 4 is less than 5.

Example 1:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

Example 2:

Input: nums = [2,4,3,3,5,4,9,6], k = 4
Output: [2,3,3,4]

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹
1 <= k <= nums.length

Solution: Stack

Use a stack to track the best solution so far, pop if the current number is less than the top of the stack and there are sufficient numbers left. Then push the current number to the stack if not full.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> mostCompetitive(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> ans(k);

int c = 0;

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

while (c && ans[c - 1] > nums[i] && c + n - i - 1 >= k)

--c;

if (c < k) ans[c++] = nums[i];

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

public int[] mostCompetitive(int[] nums, int k) {

int n = nums.length;

int[] ans = new int[k];

int c = 0;

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

while (c > 0 && ans[c - 1] > nums[i] && c + n - i - 1 >= k)

--c;

if (c < k) ans[c++] = nums[i];

}

return ans;

}

Python3

# Author: Huahua

class Solution:

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

ans = [None] * k

n = len(nums)

c = 0

for i, x in enumerate(nums):

while c and ans[c - 1] > x and c + n - i - 1 >= k:

c -= 1

if c < k:

ans[c] = x

c += 1

return ans

花花酱 LeetCode 1672. Richest Customer Wealth

By zxi on November 29, 2020

You are given an m x n integer grid accounts where accounts[i][j] is the amount of money the i^th customer has in the j^th bank. Return the wealth that the richest customer has.

A customer’s wealth is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum wealth.

Example 1:

Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.

Example 2:

Input: accounts = [[1,5],[7,3],[3,5]]
Output: 10
Explanation: 
1st customer has wealth = 6
2nd customer has wealth = 10 
3rd customer has wealth = 8
The 2nd customer is the richest with a wealth of 10.

Example 3:

Input: accounts = [[2,8,7],[7,1,3],[1,9,5]]
Output: 17

Constraints:

m == accounts.length
n == accounts[i].length
1 <= m, n <= 50
1 <= accounts[i][j] <= 100

Solution: Sum each row up

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

C++

// Author: Huahua

class Solution {

public:

int maximumWealth(vector<vector<int>>& accounts) {

int ans = 0;

for (const vector<int>& row : accounts)

ans = max(ans, accumulate(begin(row), end(row), 0));

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def maximumWealth(self, accounts: List[List[int]]) -> int:

return max(sum(account) for account in accounts)

花花酱 LeetCode 1671. Minimum Number of Removals to Make Mountain Array

By zxi on November 28, 2020

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

arr.length >= 3
There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array nums, return the minimum number of elements to remove to make numsa mountain array.

Example 1:

Input: nums = [1,3,1]
Output: 0
Explanation: The array itself is a mountain array so we do not need to remove any elements.

Example 2:

Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].

Example 3:

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

Example 4:

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

Constraints:

3 <= nums.length <= 1000
1 <= nums[i] <= 10⁹
It is guaranteed that you can make a mountain array out of nums.

Solution: DP / LIS

LIS[i] := longest increasing subsequence ends with nums[i]
LDS[i] := longest decreasing subsequence starts with nums[i]
Let nums[i] be the peak, the length of the mountain array is LIS[i] + LDS[i] – 1
Note: LIS[i] and LDS[i] must be > 1 to form a valid mountain array.
ans = min(n – (LIS[i] + LDS[i] – 1)) 0 <= i < n

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

C++

// Author: Huahua

class Solution {

public:

int minimumMountainRemovals(vector<int>& nums) {

const int n = nums.size();

vector<int> LIS(n, 1); // LIS[i] := Longest increasing subseq ends with nums[i]

vector<int> LDS(n, 1); // LDS[i] := Longest decreasing subseq starts with nums[i]

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

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

if (nums[i] > nums[j]) LIS[i] = max(LIS[i], LIS[j] + 1);

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

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

if (nums[i] > nums[j]) LDS[i] = max(LDS[i], LDS[j] + 1);

int ans = INT_MAX;

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

if (LIS[i] < 2 || LDS[i] < 2) continue;

ans = min(ans, n - (LIS[i] + LDS[i] - 1));

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1675. Minimize Deviation in Array

Solution: Priority Queue

C++/Set

C++/PQ

花花酱 LeetCode 1674. Minimum Moves to Make Array Complementary

Solution: Sweep Line / Prefix Sum

C++

花花酱 LeetCode 1673. Find the Most Competitive Subsequence

Solution: Stack

C++

Java

Python3

花花酱 LeetCode 1672. Richest Customer Wealth

Solution: Sum each row up

C++

Python3

花花酱 LeetCode 1671. Minimum Number of Removals to Make Mountain Array

Solution: DP / LIS

C++