Posts tagged as “sorting”

花花酱 LeetCode 1705. Maximum Number of Eaten Apples

By zxi on December 27, 2020

There is a special kind of apple tree that grows apples every day for n days. On the i^th day, the tree grows apples[i] apples that will rot after days[i] days, that is on day i + days[i] the apples will be rotten and cannot be eaten. On some days, the apple tree does not grow any apples, which are denoted by apples[i] == 0 and days[i] == 0.

You decided to eat at most one apple a day (to keep the doctors away). Note that you can keep eating after the first n days.

Given two integer arrays days and apples of length n, return the maximum number of apples you can eat.

Example 1:

Input: apples = [1,2,3,5,2], days = [3,2,1,4,2]
Output: 7
Explanation: You can eat 7 apples:
- On the first day, you eat an apple that grew on the first day.
- On the second day, you eat an apple that grew on the second day.
- On the third day, you eat an apple that grew on the second day. After this day, the apples that grew on the third day rot.
- On the fourth to the seventh days, you eat apples that grew on the fourth day.

Example 2:

Input: apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
Output: 5
Explanation: You can eat 5 apples:
- On the first to the third day you eat apples that grew on the first day.
- Do nothing on the fouth and fifth days.
- On the sixth and seventh days you eat apples that grew on the sixth day.

Constraints:

apples.length == n
days.length == n
1 <= n <= 2 * 10⁴
0 <= apples[i], days[i] <= 2 * 10⁴
days[i] = 0 if and only if apples[i] = 0.

Solution: PriorityQueue

Sort by rotten day in ascending order, only push onto the queue when that day has come (be able to grow apples).

Time complexity: O((n+ d)logn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int eatenApples(vector<int>& apples, vector<int>& days) {

const int n = apples.size();

using P = pair<int, int>;

priority_queue<P, vector<P>, greater<P>> q; // {rotten_day, index}

int ans = 0;

for (int d = 0; d < n || !q.empty(); ++d) {

if (d < n && apples[d]) q.emplace(d + days[d], d);

while (!q.empty()

&& (q.top().first <= d || apples[q.top().second] == 0)) q.pop();

if (q.empty()) continue;

--apples[q.top().second];

++ans;

}

return ans;

}

};

花花酱 LeetCode 1697. Checking Existence of Edge Length Limited Paths

By zxi on December 20, 2020

An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [u_i, v_i, dis_i] denotes an edge between nodes u_i and v_i with distance dis_i. Note that there may be multiple edges between two nodes.

Given an array queries, where queries[j] = [p_j, q_j, limit_j], your task is to determine for each queries[j] whether there is a path between p_j and q_jsuch that each edge on the path has a distance strictly less than limit_j .

Return a boolean array answer, where answer.length == queries.length and the j^th value of answer is true if there is a path for queries[j] is true, and false otherwise.

Example 1:

Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
Output: [false,true]
Explanation: The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.
For the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query.
For the second query, there is a path (0 -> 1 -> 2) of two edges with distances less than 5, thus we return true for this query.

Example 2:

Input: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
Output: [true,false]
Exaplanation: The above figure shows the given graph.

Constraints:

2 <= n <= 10⁵
1 <= edgeList.length, queries.length <= 10⁵
edgeList[i].length == 3
queries[j].length == 3
0 <= u_i, v_i, p_j, q_j <= n - 1
u_i != v_i
p_j != q_j
1 <= dis_i, limit_j <= 10⁹
There may be multiple edges between two nodes.

Solution: Union Find

Since queries are offline, we can reorder them to optimize time complexity. Answer queries by their limits in ascending order while union edges by weights up to the limit. In this case, we just need to go through the entire edge list at most once.

Time complexity: O(QlogQ + ElogE)
Space complexity: O(Q + E)

C++

// Author: Huahua

class Solution {

public:

vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& E, vector<vector<int>>& Q) {

vector<int> parents(n);

iota(begin(parents), end(parents), 0);

function<int(int)> find = [&](int x) {

return parents[x] == x ? x : parents[x] = find(parents[x]);

};

const int m = Q.size();

for (int i = 0; i < m; ++i) Q[i].push_back(i);

// Sort edges by weight in ascending order.

sort(begin(E), end(E), [](const auto& a, const auto& b) { return a[2] < b[2]; });

// Sort queries by limit in ascending order

sort(begin(Q), end(Q), [](const auto& a, const auto& b) { return a[2] < b[2]; });

vector<bool> ans(m);

int i = 0;

for (const auto& q : Q) {

while (i < E.size() && E[i][2] < q[2])

parents[find(E[i++][0])] = find(E[i][1]);

ans[q[3]] = find(q[0]) == find(q[1]);

}

return ans;

}

};

花花酱 LeetCode 1691. Maximum Height by Stacking Cuboids

By zxi on December 13, 2020

Given n cuboids where the dimensions of the i^th cuboid is cuboids[i] = [width_i, length_i, height_i] (0-indexed). Choose a subset of cuboids and place them on each other.

You can place cuboid i on cuboid j if width_i <= width_j and length_i <= length_j and height_i <= height_j. You can rearrange any cuboid’s dimensions by rotating it to put it on another cuboid.

Return the maximum height of the stacked cuboids.

Example 1:

Input: cuboids = [[50,45,20],[95,37,53],[45,23,12]]
Output: 190
Explanation:
Cuboid 1 is placed on the bottom with the 53x37 side facing down with height 95.
Cuboid 0 is placed next with the 45x20 side facing down with height 50.
Cuboid 2 is placed next with the 23x12 side facing down with height 45.
The total height is 95 + 50 + 45 = 190.

Example 2:

Input: cuboids = [[38,25,45],[76,35,3]]
Output: 76
Explanation:
You can't place any of the cuboids on the other.
We choose cuboid 1 and rotate it so that the 35x3 side is facing down and its height is 76.

Example 3:

Input: cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
Output: 102
Explanation:
After rearranging the cuboids, you can see that all cuboids have the same dimension.
You can place the 11x7 side down on all cuboids so their heights are 17.
The maximum height of stacked cuboids is 6 * 17 = 102.

Constraints:

n == cuboids.length
1 <= n <= 100
1 <= width_i, length_i, height_i <= 100

Solution: Math/Greedy + DP

Direct DP is very hard, since there is no orders.

We have to find some way to sort the cuboids such that cuboid i can NOT stack on cuboid j if i > j. Then dp[i] = max(dp[j]) + height[i], 0 <= j < i, for each i, find the best base j and stack on top of it.
ans = max(dp)

We can sort the cuboids by their sorted dimensions, and cuboid i can stack stack onto cuboid j if and only if w[i] <= w[j] and l[i] <= l[j] and h[i] <= h[j].

First of all, we need to prove that all heights must come from the largest dimension of each cuboid.

1. If the top of the stack is A1*A2*A3, A3 < max(A1, A2), we can easily swap A3 with max(A1, A2), it’s still stackable but we get larger heights.
e.g. 3x5x4, base is 3×5, height is 4, we can rotate to get base of 3×4 with height of 5.

2. If a middle cuboid A of size A1*A2*A3, assuming A1 >= A2, A1 > A3, on top of A we have another cuboid B of size B1*B2*B3, B1 <= B2 <= B3.
We have A1 >= B1, A2 >= B2, A3 >= B3, by rotating A we have A3*A2*A1
A3 >= B3 >= B1, A2 >= B2, A1 > A3 >= B3, so B can be still on top of A, and we get larger height.

e.g. A: 3x5x4, B: 2x3x4
A -> 3x4x5, B is still stackable.

…

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

int maxHeight(vector<vector<int>>& A) {

A.push_back({0, 0, 0});

const int n = A.size();

for (auto& box : A) sort(begin(box), end(box));

sort(begin(A), end(A));

vector<int> dp(n);

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

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

if (A[i][0] >= A[j][0] && A[i][1] >= A[j][1] && A[i][2] >= A[j][2])

dp[i] = max(dp[i], dp[j] + A[i][2]);

return *max_element(begin(dp), end(dp));

}

};

花花酱 LeetCode 1642. Furthest Building You Can Reach

By zxi on November 1, 2020

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

If the current building’s height is greater than or equal to the next building’s height, you do not need a ladder or bricks.
If the current building’s height is less than the next building’s height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Example 1:

Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.

Example 2:

Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7

Example 3:

Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3

Constraints:

1 <= heights.length <= 10⁵
1 <= heights[i] <= 10⁶
0 <= bricks <= 10⁹
0 <= ladders <= heights.length

Solution 0: DFS

Time complexity: O(2^n)
Space complexity: O(n)

AC but should be TLE

Solution 1: Binary Search + Greedy

Guess we can reach to m, sort the height differences from 0~m. Use ladders for larger values and use bricks for smallest values left.

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

C++

// Author: Huahua, 300 ms

class Solution {

public:

int furthestBuilding(vector<int>& heights, int bricks, int ladders) {

const int n = heights.size();

if (ladders >= n - 1) return n - 1;

vector<int> diffs(n);

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

diffs[i - 1] = max(0, heights[i] - heights[i - 1]);

int l = ladders;

int r = n;

while (l < r) {

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

vector<int> d(begin(diffs), begin(diffs) + m);

nth_element(begin(d), end(d) - ladders, end(d));

if (accumulate(begin(d), end(d) - ladders, 0) > bricks)

r = m;

else

l = m + 1;

}

return l - 1;

}

};

Solution 2: Min heap

Use a min heap to store all the height differences ( > 0) so far, if heap size is greater than ladders, which means we have to use bricks, extract the smallest value and subtract the bricks.

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

C++

// Author: Huahua, 216 ms

class Solution {

public:

int furthestBuilding(vector<int>& heights, int bricks, int ladders) {

const int n = heights.size();

priority_queue<int, vector<int>, greater<int>> q;

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

const int d = heights[i] - heights[i - 1];

if (d <= 0) continue;

q.push(d);

if (q.size() <= ladders) continue;

bricks -= q.top(); q.pop();

if (bricks < 0) return i - 1;

}

return n - 1;

}

};

花花酱 LeetCode 1630. Arithmetic Subarrays

By zxi on October 24, 2020

A sequence of numbers is called arithmetic if it consists of at least two elements, and the difference between every two consecutive elements is the same. More formally, a sequence s is arithmetic if and only if s[i+1] - s[i] == s[1] - s[0] for all valid i.

For example, these are arithmetic sequences:

1, 3, 5, 7, 9

7, 7, 7, 7

3, -1, -5, -9

The following sequence is not arithmetic:

1, 1, 2, 5, 7

You are given an array of n integers, nums, and two arrays of m integers each, l and r, representing the m range queries, where the i^th query is the range [l[i], r[i]]. All the arrays are 0-indexed.

Return a list of boolean elements answer, where answer[i] is true if the subarray nums[l[i]], nums[l[i]+1], ... , nums[r[i]] can be rearranged to form an arithmetic sequence, and false otherwise.

Example 1:

Input: nums = [4,6,5,9,3,7], l = [0,0,2], r = [2,3,5]
Output: [true,false,true]
Explanation:
In the 0^th query, the subarray is [4,6,5]. This can be rearranged as [6,5,4], which is an arithmetic sequence.
In the 1^st query, the subarray is [4,6,5,9]. This cannot be rearranged as an arithmetic sequence.
In the 2^nd query, the subarray is [5,9,3,7]. This can be rearranged as [3,5,7,9], which is an arithmetic sequence.

Example 2:

Input: nums = [-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10], l = [0,1,6,4,8,7], r = [4,4,9,7,9,10]
Output: [false,true,false,false,true,true]

Constraints:

n == nums.length
m == l.length
m == r.length
2 <= n <= 500
1 <= m <= 500
0 <= l[i] < r[i] < n
-10⁵ <= nums[i] <= 10⁵

Solution: Brute Force

Sort the range of each query and check.

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

C++

// Author: Huahua

class Solution {

public:

vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {

vector<bool> ans(l.size(), true);

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

vector<int> arr(begin(nums) + l[i], begin(nums) + r[i] + 1);

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

const int d = arr[1] - arr[0];

for (int j = 2; j < arr.size() && ans[i]; ++j)

ans[i] = ans[i] && (arr[j] - arr[j - 1] == d);

}

return ans;

}

};