Posts tagged as “hard”

花花酱 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 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;

}

};

花花酱 LeetCode 1659. Maximize Grid Happiness

By zxi on November 22, 2020

You are given four integers, m, n, introvertsCount, and extrovertsCount. You have an m x n grid, and there are two types of people: introverts and extroverts. There are introvertsCount introverts and extrovertsCount extroverts.

You should decide how many people you want to live in the grid and assign each of them one grid cell. Note that you do not have to have all the people living in the grid.

The happiness of each person is calculated as follows:

Introverts start with 120 happiness and lose 30 happiness for each neighbor (introvert or extrovert).
Extroverts start with 40 happiness and gain 20 happiness for each neighbor (introvert or extrovert).

Neighbors live in the directly adjacent cells north, east, south, and west of a person’s cell.

The grid happiness is the sum of each person’s happiness. Return the maximum possible grid happiness.

Example 1:

Input: m = 2, n = 3, introvertsCount = 1, extrovertsCount = 2
Output: 240
Explanation: Assume the grid is 1-indexed with coordinates (row, column).
We can put the introvert in cell (1,1) and put the extroverts in cells (1,3) and (2,3).
- Introvert at (1,1) happiness: 120 (starting happiness) - (0 * 30) (0 neighbors) = 120
- Extrovert at (1,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60
- Extrovert at (2,3) happiness: 40 (starting happiness) + (1 * 20) (1 neighbor) = 60
The grid happiness is 120 + 60 + 60 = 240.
The above figure shows the grid in this example with each person's happiness. The introvert stays in the light green cell while the extroverts live on the light purple cells.

Example 2:

Input: m = 3, n = 1, introvertsCount = 2, extrovertsCount = 1
Output: 260
Explanation: Place the two introverts in (1,1) and (3,1) and the extrovert at (2,1).
- Introvert at (1,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90
- Extrovert at (2,1) happiness: 40 (starting happiness) + (2 * 20) (2 neighbors) = 80
- Introvert at (3,1) happiness: 120 (starting happiness) - (1 * 30) (1 neighbor) = 90
The grid happiness is 90 + 80 + 90 = 260.

Example 3:

Input: m = 2, n = 2, introvertsCount = 4, extrovertsCount = 0
Output: 240

Constraints:

1 <= m, n <= 5
0 <= introvertsCount, extrovertsCount <= min(m * n, 6)

Solution: DP

dp(x, y, in, ex, mask) := max score at (x, y) with in and ex left and the state of previous row is mask.

Mask is ternary, mask(i) = {0, 1, 2} means {empty, in, ex}, there are at most 3^n = 3^5 = 243 different states.

Total states / Space complexity: O(m*n*3^n*in*ex) = 5*5*3^5*6*6
Space complexity: O(m*n*3^n*in*ex)

C++

class Solution {

public:

int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {

constexpr int kMaxStates = 243;

int dp[6][6][7][7][kMaxStates];

memset(dp, -1, sizeof(dp));

auto get = [](int val, int i) { return val / static_cast<int>(pow(3, i)) % 3; };

auto update = [](int val, int s) { return (val * 3 + s) % kMaxStates; };

vector<int> init{0, 120, 40};

vector<int> gain{0, -30, 20};

function<int(int,int,int,int,int)> dfs = [&](int x, int y, int in, int ex, int mask) {

if (in == 0 && ex == 0) return 0; // Nothing left.

if (x == n) { x = 0; ++y; }

if (y == m) return 0; // Done.

int& ans = dp[x][y][in][ex][mask];

if (ans != -1) return ans;

ans = dfs(x + 1, y, in, ex, update(mask, 0)); // Skip current cell.

vector<int> counts{0, in, ex};

int up = get(mask, n - 1);

int left = get(mask, 0);

for (int i = 1; i <= 2; ++i) {

if (counts[i] == 0) continue;

int s = init[i];

if (y - 1 >= 0 && up) s += gain[i] + gain[up];

if (x - 1 >= 0 && left) s += gain[i] + gain[left];

ans = max(ans, s + dfs(x + 1, y, in - (i==1), ex - (i==2), update(mask, i)));

}

return ans;

};

return dfs(0, 0, introvertsCount, extrovertsCount, 0);

}

};

Python3

# Author: Huahua

class Solution:

def getMaxGridHappiness(self, m: int, n: int, I: int, E: int) -> int:

init, gain = [None, 120, 40], [None, -30, 20]

get = lambda val, i: (val // (3 ** i)) % 3

update = lambda val, s: (val * 3 + s) % (3 ** n)

@lru_cache(None)

def dp(x: int, y: int, i: int, e: int, mask: int) -> int:

if x == n: x, y = 0, y + 1

if i + e == 0 or y == m: return 0

ans = dp(x + 1, y, i, e, update(mask, 0))

up, left = get(mask, n - 1), get(mask, 0)

for cur, count in enumerate([i, e], 1):

if count == 0: continue

s = init[cur]

if x - 1 >= 0 and left: s += gain[cur] + gain[left]

if y - 1 >= 0 and up: s += gain[cur] + gain[up]

ans = max(ans, s + dp(x + 1, y,

i - (cur == 1),

e - (cur == 2),

update(mask, cur)))

return ans

return dp(0, 0, I, E, 0)

花花酱 LeetCode 1665. Minimum Initial Energy to Finish Tasks

By zxi on November 22, 2020

You are given an array tasks where tasks[i] = [actual_i, minimum_i]:

actual_i is the actual amount of energy you spend to finish the i^th task.
minimum_i is the minimum amount of energy you require to begin the i^th task.

For example, if the task is [10, 12] and your current energy is 11, you cannot start this task. However, if your current energy is 13, you can complete this task, and your energy will be 3 after finishing it.

You can finish the tasks in any order you like.

Return the minimum initial amount of energy you will need to finish all the tasks.

Example 1:

Input: tasks = [[1,2],[2,4],[4,8]]
Output: 8
Explanation:
Starting with 8 energy, we finish the tasks in the following order:
    - 3rd task. Now energy = 8 - 4 = 4.
    - 2nd task. Now energy = 4 - 2 = 2.
    - 1st task. Now energy = 2 - 1 = 1.
Notice that even though we have leftover energy, starting with 7 energy does not work because we cannot do the 3rd task.

Example 2:

Input: tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
Output: 32
Explanation:
Starting with 32 energy, we finish the tasks in the following order:
    - 1st task. Now energy = 32 - 1 = 31.
    - 2nd task. Now energy = 31 - 2 = 29.
    - 3rd task. Now energy = 29 - 10 = 19.
    - 4th task. Now energy = 19 - 10 = 9.
    - 5th task. Now energy = 9 - 8 = 1.

Example 3:

Input: tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
Output: 27
Explanation:
Starting with 27 energy, we finish the tasks in the following order:
    - 5th task. Now energy = 27 - 5 = 22.
    - 2nd task. Now energy = 22 - 2 = 20.
    - 3rd task. Now energy = 20 - 3 = 17.
    - 1st task. Now energy = 17 - 1 = 16.
    - 4th task. Now energy = 16 - 4 = 12.
    - 6th task. Now energy = 12 - 6 = 6.

Constraints:

1 <= tasks.length <= 10⁵
1 <= actual_i <= minimum_i <= 10⁴

Solution: Greedy + Binary Search

Sort tasks by actual – min in ascending order, this will be the order we finish those tasks. Use binary search to check whether a given initial energy works or not. Note, the binary search part is unnecessary.

Time complexity: O(nlogn + nlogk)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minimumEffort(vector<vector<int>>& tasks) {

sort(begin(tasks), end(tasks), [](const auto& t1, const auto& t2) {

return t1[0] - t1[1] < t2[0] - t2[1];

});

int l = tasks[0][1], r = INT_MAX - 1;

auto check = [&](int cur) {

for (const auto& task : tasks) {

if (task[1] > cur) return false;

cur -= task[0];

}

return true;

};

while (l < r) {

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

check(m) ? r = m : l = m + 1;

}

return l;

}

};

花花酱 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