Posts tagged as “greedy”

花花酱 LeetCode 1605. Find Valid Matrix Given Row and Column Sums

By zxi on October 3, 2020

You are given two arrays rowSum and colSum of non-negative integers where rowSum[i] is the sum of the elements in the i^th row and colSum[j] is the sum of the elements of the j^th column of a 2D matrix. In other words, you do not know the elements of the matrix, but you do know the sums of each row and column.

Find any matrix of non-negative integers of size rowSum.length x colSum.length that satisfies the rowSum and colSum requirements.

Return a 2D array representing any matrix that fulfills the requirements. It’s guaranteed that at least one matrix that fulfills the requirements exists.

Example 1:

Input: rowSum = [3,8], colSum = [4,7]
Output: [[3,0],
         [1,7]]
Explanation:
0th row: 3 + 0 = 0 == rowSum[0]
1st row: 1 + 7 = 8 == rowSum[1]
0th column: 3 + 1 = 4 == colSum[0]
1st column: 0 + 7 = 7 == colSum[1]
The row and column sums match, and all matrix elements are non-negative.
Another possible matrix is: [[1,2],
                             [3,5]]

Example 2:

Input: rowSum = [5,7,10], colSum = [8,6,8]
Output: [[0,5,0],
         [6,1,0],
         [2,0,8]]

Example 3:

Input: rowSum = [14,9], colSum = [6,9,8]
Output: [[0,9,5],
         [6,0,3]]

Example 4:

Input: rowSum = [1,0], colSum = [1]
Output: [[1],
         [0]]

Example 5:

Input: rowSum = [0], colSum = [0]
Output: [[0]]

Constraints:

1 <= rowSum.length, colSum.length <= 500
0 <= rowSum[i], colSum[i] <= 10⁸
sum(rows) == sum(columns)

Solution: Greedy

Let a = min(row[i], col[j]), m[i][j] = a, row[i] -= a, col[j] -=a

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {

const int m = rowSum.size();

const int n = colSum.size();

vector<vector<int>> ans(m, vector<int>(n));

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

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

ans[i][j] = min(rowSum[i], colSum[j]);

rowSum[i] -= ans[i][j];

colSum[j] -= ans[i][j];

}

return ans;

}

};

花花酱 LeetCode 1589. Maximum Sum Obtained of Any Permutation

By zxi on September 19, 2020

We have an array of integers, nums, and an array of requests where requests[i] = [start_i, end_i]. The i^th request asks for the sum of nums[start_i] + nums[start_i + 1] + ... + nums[end_i - 1] + nums[end_i]. Both start_i and end_i are 0-indexed.

Return the maximum total sum of all requests among all permutations of nums.

Since the answer may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
Output: 19
Explanation: One permutation of nums is [2,1,3,4,5] with the following result: 
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
Total sum: 8 + 3 = 11.
A permutation with a higher total sum is [3,5,4,2,1] with the following result:
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5  = 8
Total sum: 11 + 8 = 19, which is the best that you can do.

Example 2:

Input: nums = [1,2,3,4,5,6], requests = [[0,1]]
Output: 11
Explanation: A permutation with the max total sum is [6,5,4,3,2,1] with request sums [11].

Example 3:

Input: nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
Output: 47
Explanation: A permutation with the max total sum is [4,10,5,3,2,1] with request sums [19,18,10].

Constraints:

n == nums.length
1 <= n <= 10⁵
0 <= nums[i] <= 10⁵
1 <= requests.length <= 10⁵
requests[i].length == 2
0 <= start_i <= end_i < n

Solution: Greedy + Sweep line

Sort the numbers, and sort the frequency of each index, it’s easy to show largest number with largest frequency gives us max sum.

ans = sum(nums[i] * freq[i])

We can use sweep line to compute the frequency of each index in O(n) time and space.

For each request [start, end] : ++freq[start], –freq[end + 1]

Then the prefix sum of freq array is the frequency for each index.

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

C++

class Solution {

public:

int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {

constexpr int kMod = 1e9 + 7;

const int n = nums.size();

vector<long> freq(n);

for (const auto& r : requests) {

++freq[r[0]];

if (r[1] + 1 < n) --freq[r[1] + 1];

}

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

freq[i] += freq[i - 1];

sort(begin(freq), end(freq));

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

long ans = 0;

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

ans += freq[i] * nums[i];

return ans % kMod;

}

};

花花酱 LeetCode 1578. Minimum Deletion Cost to Avoid Repeating Letters

By zxi on September 5, 2020

Given a string s and an array of integers cost where cost[i] is the cost of deleting the character i in s.

Return the minimum cost of deletions such that there are no two identical letters next to each other.

Notice that you will delete the chosen characters at the same time, in other words, after deleting a character, the costs of deleting other characters will not change.

Example 1:

Input: s = "abaac", cost = [1,2,3,4,5]
Output: 3
Explanation: Delete the letter "a" with cost 3 to get "abac" (String without two identical letters next to each other).

Example 2:

Input: s = "abc", cost = [1,2,3]
Output: 0
Explanation: You don't need to delete any character because there are no identical letters next to each other.

Example 3:

Input: s = "aabaa", cost = [1,2,3,4,1]
Output: 2
Explanation: Delete the first and the last character, getting the string ("aba").

Constraints:

s.length == cost.length
1 <= s.length, cost.length <= 10^5
1 <= cost[i] <= 10^4
s contains only lowercase English letters.

Solution: Group by group

For a group of same letters, delete all expect the one with the highest cost.

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

C++

class Solution {

public:

int minCost(string s, vector<int>& cost) {

int t = cost[0];

int m = cost[0];

int ans = 0;

for (int i = 1; i < s.length(); ++i) {

if (s[i] != s[i - 1]) {

ans += t - m;

t = m = 0;

}

t += cost[i];

m = max(m, cost[i]);

}

return ans + (t - m);

}

};

python3

class Solution:

def minCost(self, s: str, cost: List[int]) -> int:

s = '*' + s + '*'

cost = [0] + cost + [0]

ans = t = m = 0

for i in range(1, len(s)):

if s[i] != s[i - 1]:

ans += t - m

t = m = 0

t += cost[i]

m = max(m, cost[i])

return ans

花花酱 LeetCode 1561. Maximum Number of Coins You Can Get

By zxi on August 23, 2020

There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:

In each step, you will choose any 3 piles of coins (not necessarily consecutive).
Of your choice, Alice will pick the pile with the maximum number of coins.
You will pick the next pile with maximum number of coins.
Your friend Bob will pick the last pile.
Repeat until there are no more piles of coins.

Given an array of integers piles where piles[i] is the number of coins in the i^th pile.

Return the maximum number of coins which you can have.

Example 1:

Input: piles = [2,4,1,2,7,8]
Output: 9
Explanation: Choose the triplet (2, 7, 8), Alice Pick the pile with 8 coins, you the pile with 7 coins and Bob the last one.
Choose the triplet (1, 2, 4), Alice Pick the pile with 4 coins, you the pile with 2 coins and Bob the last one.
The maximum number of coins which you can have are: 7 + 2 = 9.
On the other hand if we choose this arrangement (1, 2, 8), (2, 4, 7) you only get 2 + 4 = 6 coins which is not optimal.

Example 2:

Input: piles = [2,4,5]
Output: 4

Example 3:

Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18

Constraints:

3 <= piles.length <= 10^5
piles.length % 3 == 0
1 <= piles[i] <= 10^4

Solution: Greedy

Always take the second largest element of a in the sorted array.
[1, 2, 3, 4, 5, 6, 7, 8, 9]
tuples: (1, 8, 9), (2, 6, 7), (3, 4, 5)
Alice: 9, 7, 5
You: 8, 6, 4
Bob: 1, 2, 3

Time complexity: O(nlogn) -> O(n + k)
Space complexity: O(1)

C++

class Solution {

public:

int maxCoins(vector<int>& piles) {

const int n = piles.size() / 3;

sort(begin(piles), end(piles));

int ans = 0;

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

ans += piles[n * 3 - 2 - i * 2];

return ans;

}

};

C++ counting sort

class Solution {

public:

int maxCoins(vector<int>& piles) {

constexpr int kMax = 10000;

const int n = piles.size() / 3;

vector<int> counts(kMax + 1);

for (int v : piles) ++counts[v];

int idx = 0;

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

while (counts[i]--) piles[idx++] = i;

int ans = 0;

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

ans += piles[n * 3 - 2 - i * 2];

return ans;

}

};

花花酱 LeetCode 1553. Minimum Number of Days to Eat N Oranges

By zxi on August 16, 2020

There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows:

Eat one orange.
If the number of remaining oranges (n) is divisible by 2 then you can eat n/2 oranges.
If the number of remaining oranges (n) is divisible by 3 then you can eat 2*(n/3) oranges.

You can only choose one of the actions per day.

Return the minimum number of days to eat n oranges.

Example 1:

Input: n = 10
Output: 4
Explanation: You have 10 oranges.
Day 1: Eat 1 orange,  10 - 1 = 9.  
Day 2: Eat 6 oranges, 9 - 2*(9/3) = 9 - 6 = 3. (Since 9 is divisible by 3)
Day 3: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. 
Day 4: Eat the last orange  1 - 1  = 0.
You need at least 4 days to eat the 10 oranges.

Example 2:

Input: n = 6
Output: 3
Explanation: You have 6 oranges.
Day 1: Eat 3 oranges, 6 - 6/2 = 6 - 3 = 3. (Since 6 is divisible by 2).
Day 2: Eat 2 oranges, 3 - 2*(3/3) = 3 - 2 = 1. (Since 3 is divisible by 3)
Day 3: Eat the last orange  1 - 1  = 0.
You need at least 3 days to eat the 6 oranges.

Example 3:

Input: n = 1
Output: 1

Example 4:

Input: n = 56
Output: 6

Constraints:

1 <= n <= 2*10^9

Solution: Greedy + DP

Eat oranges one by one to make it a multiply of 2 or 3 such that we can eat 50% or 66.66…% of the oranges in one step.
dp(n) := min steps to finish n oranges.
base case n <= 1, dp(n) = n
transition: dp(n) = 1 + min(n%2 + dp(n/2), n % 3 + dp(n / 3))
e.g. n = 11,
we eat 11%2 = 1 in one step, left = 10 and then eat 10 / 2 = 5 in another step. 5 left for the subproblem.
we eat 11%3 = 2 in two steps, left = 9 and then eat 9 * 2 / 3 = 6 in another step, 3 left for the subproblem.
dp(11) = 1 + min(1 + dp(5), 2 + dp(3))

T(n) = 2*T(n/2) + O(1) = O(n)
Time complexity: O(n) // w/o memoization, close to O(logn) in practice.
Space complexity: O(logn)

C++

class Solution {

public:

int minDays(int n) {

unordered_map<int, int> cache;

function<int(int)> dp = [&](int n) {

if (n <= 1) return n;

auto it = cache.find(n);

if (it != cache.end()) return it->second;

return cache[n] = 1 + min(n % 2 + dp(n / 2), n % 3 + dp(n / 3));

};

return dp(n);

}

};

Java

class Solution {

private static Map<Integer, Integer> cache = new HashMap<>();

public int minDays(int n) {

return dp(n);

}

private int dp(int n) {

if (n <= 1) return n;

if (cache.containsKey(n)) return cache.get(n);

int ans = 1 + Math.min(n % 2 + dp(n / 2), n % 3 + dp(n / 3));

cache.put(n, ans);

return ans;

}

Python3

class Solution:

def minDays(self, n: int) -> int:

@lru_cache(None)

def dp(n):

if n <= 1: return n

return 1 + min(n % 2 + dp(n // 2), n % 3 + dp(n // 3))

return dp(n)

Solution 2: BFS

if x % 2 == 0, push x/2 onto the queue
if x % 3 == 0, push x/3 onto the queue
always push x – 1 onto the queue

C++

class Solution {

public:

int minDays(int n) {

queue<int> q{{n}};

unordered_set<int> seen;

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

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

if (x == 0) return steps;

if (x % 2 == 0 && seen.insert(x / 2).second)

q.push(x / 2);

if (x % 3 == 0 && seen.insert(x / 3).second)

q.push(x / 3);

if (seen.insert(x - 1).second)

q.push(x - 1);

}

++steps;

}

return -1;

}

};