Posts published in “Greedy”

花花酱 LeetCode 1962. Remove Stones to Minimize the Total

By zxi on December 31, 2021

You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the i^th pile, and an integer k. You should apply the following operation exactly k times:

Choose any piles[i] and remove floor(piles[i] / 2) stones from it.

Notice that you can apply the operation on the same pile more than once.

Return the minimum possible total number of stones remaining after applying the k operations.

floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).

Example 1:

Input: piles = [5,4,9], k = 2
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [5,4,5].
- Apply the operation on pile 0. The resulting piles are [3,4,5].
The total number of stones in [3,4,5] is 12.

Example 2:

Input: piles = [4,3,6,7], k = 3
Output: 12
Explanation: Steps of a possible scenario are:
- Apply the operation on pile 2. The resulting piles are [4,3,3,7].
- Apply the operation on pile 3. The resulting piles are [4,3,3,4].
- Apply the operation on pile 0. The resulting piles are [2,3,3,4].
The total number of stones in [2,3,3,4] is 12.

Constraints:

1 <= piles.length <= 10⁵
1 <= piles[i] <= 10⁴
1 <= k <= 10⁵

Solution: Greedy / Heap

Always choose the largest pile to remove.

Time complexity: O(n + klogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int minStoneSum(vector<int>& piles, int k) {

int total = accumulate(begin(piles), end(piles), 0);

priority_queue<int> q(begin(piles), end(piles));

while (k--) {

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

int remove = curr / 2;

total -= remove;

q.push(curr - remove);

}

return total;

}

};

花花酱 LeetCode 1946. Largest Number After Mutating Substring

By zxi on December 31, 2021

You are given a string num, which represents a large integer. You are also given a 0-indexed integer array change of length 10 that maps each digit 0-9 to another digit. More formally, digit d maps to digit change[d].

You may choose to mutate a single substring of num. To mutate a substring, replace each digit num[i] with the digit it maps to in change (i.e. replace num[i] with change[num[i]]).

Return a string representing the largest possible integer after mutating (or choosing not to) a single substring of num.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: num = "132", change = [9,8,5,0,3,6,4,2,6,8]
Output: "832"
Explanation: Replace the substring "1":
- 1 maps to change[1] = 8.
Thus, "132" becomes "832".
"832" is the largest number that can be created, so return it.

Example 2:

Input: num = "021", change = [9,4,3,5,7,2,1,9,0,6]
Output: "934"
Explanation: Replace the substring "021":
- 0 maps to change[0] = 9.
- 2 maps to change[2] = 3.
- 1 maps to change[1] = 4.
Thus, "021" becomes "934".
"934" is the largest number that can be created, so return it.

Example 3:

Input: num = "5", change = [1,4,7,5,3,2,5,6,9,4]
Output: "5"
Explanation: "5" is already the largest number that can be created, so return it.

Constraints:

1 <= num.length <= 10⁵
num consists of only digits 0-9.
change.length == 10
0 <= change[d] <= 9

Solution: Greedy

Find the first digit that is less equal to the mutated one as the start of the substring, keep replacing as long as mutated >= current.

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

C++

// Author: Huahua

class Solution {

public:

string maximumNumber(string num, vector<int>& change) {

const int n = num.size();

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

if (num[i] - '0' < change[num[i] - '0']) {

for (int j = i; j < n && num[j] - '0' <= change[num[j] - '0']; ++j)

num[j] = change[num[j] - '0'] + '0';

break;

}

return num;

}

};

花花酱 LeetCode 1921. Eliminate Maximum Number of Monsters

By zxi on December 25, 2021

You are playing a video game where you are defending your city from a group of n monsters. You are given a 0-indexed integer array dist of size n, where dist[i] is the initial distance in kilometers of the i^th monster from the city.

The monsters walk toward the city at a constant speed. The speed of each monster is given to you in an integer array speed of size n, where speed[i] is the speed of the i^th monster in kilometers per minute.

You have a weapon that, once fully charged, can eliminate a single monster. However, the weapon takes one minute to charge.The weapon is fully charged at the very start.

You lose when any monster reaches your city. If a monster reaches the city at the exact moment the weapon is fully charged, it counts as a loss, and the game ends before you can use your weapon.

Return the maximum number of monsters that you can eliminate before you lose, or n if you can eliminate all the monsters before they reach the city.

Example 1:

Input: dist = [1,3,4], speed = [1,1,1]
Output: 3
Explanation:
In the beginning, the distances of the monsters are [1,3,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,2,3]. You eliminate the second monster.
After a minute, the distances of the monsters are [X,X,2]. You eliminate the thrid monster.
All 3 monsters can be eliminated.

Example 2:

Input: dist = [1,1,2,3], speed = [1,1,1,1]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [1,1,2,3]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,1,2], so you lose.
You can only eliminate 1 monster.

Example 3:

Input: dist = [3,2,4], speed = [5,3,2]
Output: 1
Explanation:
In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster.
After a minute, the distances of the monsters are [X,0,2], so you lose.
You can only eliminate 1 monster.

Constraints:

n == dist.length == speed.length
1 <= n <= 10⁵
1 <= dist[i], speed[i] <= 10⁵

Solution: Greedy

Sort by arrival time, and see how many we can eliminate.

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

C++

// Author: Huahua

class Solution {

public:

int eliminateMaximum(vector<int>& dist, vector<int>& speed) {

const int n = dist.size();

vector<int> t(n);

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

t[i] = (dist[i] + speed[i] - 1) / speed[i];

sort(begin(t), end(t));

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

if (t[i] <= i) return i;

return n;

}

};

花花酱 LeetCode 1913. Maximum Product Difference Between Two Pairs

By zxi on December 24, 2021

The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d).

For example, the product difference between (5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16.

Given an integer array nums, choose four distinct indices w, x, y, and z such that the product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized.

Return the maximum such product difference.

Example 1:

Input: nums = [5,6,2,7,4]
Output: 34
Explanation: We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4).
The product difference is (6 * 7) - (2 * 4) = 34.

Example 2:

Input: nums = [4,2,5,9,7,4,8]
Output: 64
Explanation: We can choose indices 3 and 6 for the first pair (9, 8) and indices 1 and 5 for the second pair (2, 4).
The product difference is (9 * 8) - (2 * 4) = 64.

Constraints:

4 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁴

Solution: Greedy

Since all the numbers are positive, we just need to find the largest two numbers as the first pair and smallest two numbers are the second pair.

Time complexity: O(nlogn) / sorting, O(n) / finding min/max elements.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxProductDifference(vector<int>& nums) {

const int n = nums.size();

sort(begin(nums), end(nums));

return nums[n - 1] * nums[n - 2] - nums[0] * nums[1];

}

};

Python3

# Author: Huahua

class Solution:

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

nums.sort()

return nums[-1] * nums[-2] - nums[0] * nums[1]

花花酱 LeetCode 179. Largest Number

By zxi on November 28, 2021

Given a list of non-negative integers nums, arrange them such that they form the largest number.

Note: The result may be very large, so you need to return a string instead of an integer.

Example 1:

Input: nums = [10,2]
Output: "210"

Example 2:

Input: nums = [3,30,34,5,9]
Output: "9534330"

Example 3:

Input: nums = [1]
Output: "1"

Example 4:

Input: nums = [10]
Output: "10"

Constraints:

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

Solution: Greedy

Sort numbers by lexical order.
e.g. 9 > 666

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

C++

// Author: Huahua

class Solution {

public:

string largestNumber(vector<int> &num) {

vector<string> s;

for (int x : num)

s.emplace_back(to_string(x));

sort(begin(s), end(s), [](const auto& s1, const auto& s2) {

return s1 + s2 > s2 + s1;

});

if (s[0] == "0") return "0";

string ans;

for (int i = 0; i < s.size(); ++i)

ans += s[i];

return ans;

}

};