Posts tagged as “sort”

花花酱 LeetCode 1846. Maximum Element After Decreasing and Rearranging

By zxi on May 1, 2021

You are given an array of positive integers arr. Perform some operations (possibly none) on arr so that it satisfies these conditions:

The value of the first element in arr must be 1.
The absolute difference between any 2 adjacent elements must be less than or equal to 1. In other words, abs(arr[i] - arr[i - 1]) <= 1 for each i where 1 <= i < arr.length (0-indexed). abs(x) is the absolute value of x.

There are 2 types of operations that you can perform any number of times:

Decrease the value of any element of arr to a smaller positive integer.
Rearrange the elements of arr to be in any order.

Return the maximum possible value of an element in arr after performing the operations to satisfy the conditions.

Example 1:

Input: arr = [2,2,1,2,1]
Output: 2
Explanation: 
We can satisfy the conditions by rearranging arr so it becomes [1,2,2,2,1].
The largest element in arr is 2.

Example 2:

Input: arr = [100,1,1000]
Output: 3
Explanation: 
One possible way to satisfy the conditions is by doing the following:
1. Rearrange arr so it becomes [1,100,1000].
2. Decrease the value of the second element to 2.
3. Decrease the value of the third element to 3.
Now arr = [1,2,3], which satisfies the conditions.
The largest element in arr is 3.

Example 3:

Input: arr = [1,2,3,4,5]
Output: 5
Explanation: The array already satisfies the conditions, and the largest element is 5.

Constraints:

1 <= arr.length <= 10⁵
1 <= arr[i] <= 10⁹

Solution: Sort

arr[0] = 1,
arr[i] = min(arr[i], arr[i – 1] + 1)

ans = arr[n – 1]

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

C++

// Author: Huahua

class Solution {

public:

int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {

const int n = arr.size();

sort(begin(arr), end(arr));

arr[0] = 1;

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

arr[i] = min(arr[i], arr[i - 1] + 1);

return arr.back();

}

};

花花酱 LeetCode 1838. Frequency of the Most Frequent Element

By zxi on April 25, 2021

The frequency of an element is the number of times it occurs in an array.

You are given an integer array nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1.

Return the maximum possible frequency of an element after performing at most k operations.

Example 1:

Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment the first element three times and the second element two times to make nums = [4,4,4].
4 has a frequency of 3.

Example 2:

Input: nums = [1,4,8,13], k = 5
Output: 2
Explanation: There are multiple optimal solutions:
- Increment the first element three times to make nums = [4,4,8,13]. 4 has a frequency of 2.
- Increment the second element four times to make nums = [1,8,8,13]. 8 has a frequency of 2.
- Increment the third element five times to make nums = [1,4,13,13]. 13 has a frequency of 2.

Example 3:

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

Constraints:

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

Solution: Sliding Window

Sort the elements, maintain a window such that it takes at most k ops to make the all the elements equal to nums[i].

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

C++

class Solution {

public:

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

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

int l = 0;

long sum = 0;

int ans = 0;

for (int r = 0; r < nums.size(); ++r) {

sum += nums[r];

while (l < r &&

sum + k < static_cast<long>(nums[r]) * (r - l + 1))

sum -= nums[l++];

ans = max(ans, r - l + 1);

}

return ans;

}

};

花花酱 LeetCode 1834. Single-Threaded CPU

By zxi on April 18, 2021

You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTime_i, processingTime_i] means that the i^th task will be available to process at enqueueTime_i and will take processingTime_ito finish processing.

You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

If the CPU is idle and there are no available tasks to process, the CPU remains idle.
If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
Once a task is started, the CPU will process the entire task without stopping.
The CPU can finish a task then start a new one instantly.

Return the order in which the CPU will process the tasks.

Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows: 
- At time = 1, task 0 is available to process. Available tasks = {0}.
- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.

Example 2:

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation: The events go as follows:
- At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
- Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
- At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
- At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
- At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
- At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
- At time = 40, the CPU finishes task 1 and becomes idle.

Constraints:

tasks.length == n
1 <= n <= 10⁵
1 <= enqueueTime_i, processingTime_i <= 10⁹

Solution: Simulation w/ Sort + PQ

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = tasks.size();

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

tasks[i].push_back(i);

sort(begin(tasks), end(tasks)); // sort by enqueue_time;

vector<int> ans;

priority_queue<pair<int, int>> q; // {-processing_time, -index}

int i = 0;

long t = 0;

while (ans.size() != n) {

// Advance to next enqueue time if q is empty.

if (i < n && q.empty() && tasks[i][0] > t)

t = tasks[i][0];

// Enqueue all available tasks.

while (i < n && tasks[i][0] <= t) {

q.emplace(-tasks[i][1], -tasks[i][2]);

++i;

}

// Extra the top one.

t -= q.top().first;

ans.push_back(-q.top().second);

q.pop();

}

return ans;

}

};

花花酱 LeetCode 1833. Maximum Ice Cream Bars

By zxi on April 18, 2021

It is a sweltering summer day, and a boy wants to buy some ice cream bars.

At the store, there are n ice cream bars. You are given an array costs of length n, where costs[i] is the price of the i^th ice cream bar in coins. The boy initially has coins coins to spend, and he wants to buy as many ice cream bars as possible.

Return the maximum number of ice cream bars the boy can buy with coins coins.

Note: The boy can buy the ice cream bars in any order.

Example 1:

Input: costs = [1,3,2,4,1], coins = 7
Output: 4
Explanation: The boy can buy ice cream bars at indices 0,1,2,4 for a total price of 1 + 3 + 2 + 1 = 7.

Example 2:

Input: costs = [10,6,8,7,7,8], coins = 5
Output: 0
Explanation: The boy cannot afford any of the ice cream bars.

Example 3:

Input: costs = [1,6,3,1,2,5], coins = 20
Output: 6
Explanation: The boy can buy all the ice cream bars for a total price of 1 + 6 + 3 + 1 + 2 + 5 = 18.

Constraints:

costs.length == n
1 <= n <= 10⁵
1 <= costs[i] <= 10⁵
1 <= coins <= 10⁸

Solution: Greedy

Sort by price in ascending order, buy from the lowest price to the highest price.

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

C++

class Solution {

public:

int maxIceCream(vector<int>& costs, int coins) {

sort(begin(costs), end(costs));

int ans = 0;

for (int c : costs) {

if (c > coins) break;

coins -= c;

++ans;

}

return ans;

}

};

花花酱 LeetCode 1710. Maximum Units on a Truck

By zxi on January 2, 2021

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i]:

numberOfBoxes_i is the number of boxes of type i.
numberOfUnitsPerBox_iis the number of units in each box of the type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

Example 1:

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation: There are:
- 1 box of the first type that contains 3 units.
- 2 boxes of the second type that contain 2 units each.
- 3 boxes of the third type that contain 1 unit each.
You can take all the boxes of the first and second types, and one box of the third type.
The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.

Example 2:

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
Output: 91

Constraints:

1 <= boxTypes.length <= 1000
1 <= numberOfBoxes_i, numberOfUnitsPerBox_i <= 1000
1 <= truckSize <= 10⁶

Solution: Greedy

Sort by unit in descending order.

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

C++

// Author: Huahua

class Solution {

public:

int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {

sort(begin(boxTypes), end(boxTypes), [](const auto& a, const auto& b){

return a[1] > b[1]; // Sort by unit DESC

});

int ans = 0;

for (const auto& b : boxTypes) {

ans += b[1] * min(b[0], truckSize);

if ((truckSize -= b[0]) <= 0) break;

}

return ans;

}

};