Posts published in “Greedy”

花花酱 LeetCode 1899. Merge Triplets to Form Target Triplet

By zxi on August 11, 2021

A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [a_i, b_i, c_i] describes the i^th triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain.

To obtain target, you may apply the following operation on triplets any number of times (possibly zero):

Choose two indices (0-indexed) i and j (i != j) and update triplets[j] to become [max(a_i, a_j), max(b_i, b_j), max(c_i, c_j)].
- For example, if triplets[i] = [2, 5, 3] and triplets[j] = [1, 7, 5], triplets[j] will be updated to [max(2, 1), max(5, 7), max(3, 5)] = [2, 7, 5].

Return true if it is possible to obtain the target triplet [x, y, z] as an element of triplets, or false otherwise.

Example 1:

Input: triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and last triplets [[2,5,3],[1,8,4],[1,7,5]]. Update the last triplet to be [max(2,1), max(5,7), max(3,5)] = [2,7,5]. triplets = [[2,5,3],[1,8,4],[2,7,5]]
The target triplet [2,7,5] is now an element of triplets.

Example 2:

Input: triplets = [[1,3,4],[2,5,8]], target = [2,5,8]
Output: true
Explanation: The target triplet [2,5,8] is already an element of triplets.

Example 3:

Input: triplets = [[2,5,3],[2,3,4],[1,2,5],[5,2,3]], target = [5,5,5]
Output: true
Explanation: Perform the following operations:
- Choose the first and third triplets [[2,5,3],[2,3,4],[1,2,5],[5,2,3]]. Update the third triplet to be [max(2,1), max(5,2), max(3,5)] = [2,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,2,3]].
- Choose the third and fourth triplets [[2,5,3],[2,3,4],[2,5,5],[5,2,3]]. Update the fourth triplet to be [max(2,5), max(5,2), max(5,3)] = [5,5,5]. triplets = [[2,5,3],[2,3,4],[2,5,5],[5,5,5]].
The target triplet [5,5,5] is now an element of triplets.

Example 4:

Input: triplets = [[3,4,5],[4,5,6]], target = [3,2,5]
Output: false
Explanation: It is impossible to have [3,2,5] as an element because there is no 2 in any of the triplets.

Constraints:

1 <= triplets.length <= 10⁵
triplets[i].length == target.length == 3
1 <= a_i, b_i, c_i, x, y, z <= 1000

Solution: Greedy

Exclude those bad ones (whose values are greater than x, y, z), check the max value for each dimension or whether there is x, y, z for each dimension.

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

C++

// Author: Huahua

class Solution {

public:

bool mergeTriplets(vector<vector<int>>& triplets, vector<int>& t) {

vector<int> ans(3);

for (const auto& c : triplets)

if (c[0] <= t[0] && c[1] <= t[1] && c[2] <= t[2])

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

ans[i] |= c[i] == t[i];

return ans[0] && ans[1] && ans[2];

}

};

花花酱 LeetCode 1881. Maximum Value after Insertion

By zxi on August 8, 2021

You are given a very large integer n, represented as a string, and an integer digit x. The digits in n and the digit x are in the inclusive range [1, 9], and n may represent a negative number.

You want to maximize n‘s numerical value by inserting x anywhere in the decimal representation of n. You cannot insert x to the left of the negative sign.

For example, if n = 73 and x = 6, it would be best to insert it between 7 and 3, making n = 763.
If n = -55 and x = 2, it would be best to insert it before the first 5, making n = -255.

Return a string representing the maximum value of n after the insertion.

Example 1:

Input: n = "99", x = 9
Output: "999"
Explanation: The result is the same regardless of where you insert 9.

Example 2:

Input: n = "-13", x = 2
Output: "-123"
Explanation: You can make n one of {-213, -123, -132}, and the largest of those three is -123.

Constraints:

1 <= n.length <= 10⁵
1 <= x <= 9
The digits in n are in the range [1, 9].
n is a valid representation of an integer.
In the case of a negative n, it will begin with '-'.

Solution: Greedy

Find the best position to insert x. For positive numbers, insert x to the first position i such that s[i] < x or s[i] > x for negatives.

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

C++

// Author: Huahua

class Solution {

public:

string maxValue(string n, int x) {

const int l = n.length();

if (n[0] == '-') {

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

if (i == l || n[i] - '0' > x)

return n.substr(0, i) + static_cast<char>('0' + x) + n.substr(i);

} else {

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

if (i == l || x > n[i] - '0')

return n.substr(0, i) + static_cast<char>('0' + x) + n.substr(i);

}

return "";

}

};

花花酱 LeetCode 1877. Minimize Maximum Pair Sum in Array

By zxi on August 6, 2021

The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs.

For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8.

Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that:

Each element of nums is in exactly one pair, and
The maximum pair sum is minimized.

Return the minimized maximum pair sum after optimally pairing up the elements.

Example 1:

Input: nums = [3,5,2,3]
Output: 7
Explanation: The elements can be paired up into pairs (3,3) and (5,2).
The maximum pair sum is max(3+3, 5+2) = max(6, 7) = 7.

Example 2:

Input: nums = [3,5,4,2,4,6]
Output: 8
Explanation: The elements can be paired up into pairs (3,5), (4,4), and (6,2).
The maximum pair sum is max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8.

Constraints:

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

Solution: Greedy

Sort the elements, pair nums[i] with nums[n – i – 1] and find the max pair.

Time complexity: O(nlogn) -> O(n) counting sort.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minPairSum(vector<int>& nums) {

const int n = nums.size();

int ans = 0;

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

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

ans = max(ans, nums[i] + nums[n - i - 1]);

return ans;

}

};

花花酱 LeetCode 1864. Minimum Number of Swaps to Make the Binary String Alternating

By zxi on August 4, 2021

Given a binary string s, return the minimum number of character swaps to make it alternating, or -1 if it is impossible.

The string is called alternating if no two adjacent characters are equal. For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

Any two characters may be swapped, even if they are not adjacent.

Example 1:

Input: s = "111000"
Output: 1
Explanation: Swap positions 1 and 4: "111000" -> "101010"
The string is now alternating.

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating, no swaps are needed.

Example 3:

Input: s = "1110"
Output: -1

Constraints:

1 <= s.length <= 1000
s[i] is either '0' or '1'.

Solution: Greedy

Two passes, make the string starts with ‘0’ or ‘1’, count how many 0/1 swaps needed. 0/1 swaps must equal otherwise it’s impossible to swap.

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

C++

// Author: Huahua

class Solution {

public:

int minSwaps(string s) {

auto count = [&](int m) {

vector<int> swaps(2);

for (int i = 0; i < s.length(); ++i, m ^= 1)

if (s[i] - '0' != m)

++swaps[s[i] - '0'];

return swaps[0] == swaps[1] ? swaps[0] : INT_MAX;

};

int ans = min(count(0), count(1));

return ans != INT_MAX ? ans : -1;

}

};

花花酱 LeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

By zxi on May 8, 2021

You are given a string num, representing a large integer, and an integer k.

We call some integer wonderful if it is a permutation of the digits in num and is greater in value than num. There can be many wonderful integers. However, we only care about the smallest-valued ones.

For example, when num = "5489355142":
- The 1^st smallest wonderful integer is "5489355214".
- The 2^nd smallest wonderful integer is "5489355241".
- The 3^rd smallest wonderful integer is "5489355412".
- The 4^th smallest wonderful integer is "5489355421".

Return the minimum number of adjacent digit swaps that needs to be applied to num to reach the k^th smallest wonderful integer.

The tests are generated in such a way that k^th smallest wonderful integer exists.

Example 1:

Input: num = "5489355142", k = 4
Output: 2
Explanation: The 4^th smallest wonderful number is "5489355421". To get this number:
- Swap index 7 with index 8: "5489355142" -> "5489355412"
- Swap index 8 with index 9: "5489355412" -> "5489355421"

Example 2:

Input: num = "11112", k = 4
Output: 4
Explanation: The 4^th smallest wonderful number is "21111". To get this number:
- Swap index 3 with index 4: "11112" -> "11121"
- Swap index 2 with index 3: "11121" -> "11211"
- Swap index 1 with index 2: "11211" -> "12111"
- Swap index 0 with index 1: "12111" -> "21111"

Example 3:

Input: num = "00123", k = 1
Output: 1
Explanation: The 1^st smallest wonderful number is "00132". To get this number:
- Swap index 3 with index 4: "00123" -> "00132"

Constraints:

2 <= num.length <= 1000
1 <= k <= 1000
num only consists of digits.

Solution: Next Permutation + Greedy

Time complexity: O(k*n + n^2)
Space complexity: O(n)

C++

class Solution {

public:

int getMinSwaps(string s, int k) {

string t(s);

while (k--) next_permutation(begin(t), end(t));

const int n = s.length();

int ans = 0;

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

if (s[i] == t[i]) continue;

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

if (s[i] != t[j]) continue;

ans += j - i;

t = t.substr(0, i + 1) + t.substr(i, j - i) + t.substr(j + 1);

break;

}

return ans;

}

};