In this guide, you will get 2561. Rearranging Fruits LeetCode Solution with the best time and space complexity. The solution to Rearranging Fruits problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You have two fruit baskets containing n fruits each. You are given two 0-indexed integer arrays basket1 and basket2 representing the cost of fruit in each basket. You want to make both baskets equal. To do so, you can use the following operation as many times as you want:
Chose two indices i and j, and swap the ith fruit of basket1 with the jth fruit of basket2.
The cost of the swap is min(basket1[i],basket2[j]).
Two baskets are considered equal if sorting them according to the fruit cost makes them exactly the same baskets.
Return the minimum cost to make both the baskets equal or -1 if impossible.
Example 1:
Input: basket1 = [4,2,2,2], basket2 = [1,4,1,2]
Output: 1
Explanation: Swap index 1 of basket1 with index 0 of basket2, which has cost 1. Now basket1 = [4,1,2,2] and basket2 = [2,4,1,2]. Rearranging both the arrays makes them equal.
Example 2:
Input: basket1 = [2,3,4,1], basket2 = [3,2,5,1]
Output: -1
Explanation: It can be shown that it is impossible to make both the baskets equal.
class Solution {
public:
long long minCost(vector<int>& basket1, vector<int>& basket2) {
vector<int> swapped;
unordered_map<int, int> count;
for (const int b : basket1)
++count[b];
for (const int b : basket2)
--count[b];
for (const auto& [num, freq] : count) {
if (freq % 2 != 0)
return -1;
for (int i = 0; i < abs(freq) / 2; ++i)
swapped.push_back(num);
}
const int minNum = min(ranges::min(basket1), ranges::min(basket2));
const auto midIt = swapped.begin() + swapped.size() / 2;
nth_element(swapped.begin(), midIt, swapped.end());
return accumulate(swapped.begin(), midIt, 0L,
[minNum](long subtotal, int num) {
return subtotal + min(2 * minNum, num);
});
}
}; /* code provided by PROGIEZ */
2561. Rearranging Fruits LeetCode Solution in Java
class Solution {
public long minCost(int[] basket1, int[] basket2) {
long ans = 0;
List<Integer> swapped = new ArrayList<>();
Map<Integer, Integer> count = new HashMap<>();
for (final int b : basket1)
count.merge(b, 1, Integer::sum);
for (final int b : basket2)
count.merge(b, -1, Integer::sum);
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
final Integer num = entry.getKey();
final Integer freq = entry.getValue();
if (freq % 2 != 0)
return -1;
for (int i = 0; i < Math.abs(freq) / 2; ++i)
swapped.add(num);
}
final int minNum =
Math.min(Arrays.stream(basket1).min().getAsInt(), Arrays.stream(basket2).min().getAsInt());
Collections.sort(swapped);
for (int i = 0; i < swapped.size() / 2; ++i)
ans += Math.min(minNum * 2, swapped.get(i));
return ans;
}
} // code provided by PROGIEZ
2561. Rearranging Fruits LeetCode Solution in Python
class Solution:
def minCost(self, basket1: list[int], basket2: list[int]) -> int:
swapped = []
count = collections.Counter(basket1)
count.subtract(collections.Counter(basket2))
for num, freq in count.items():
if freq % 2 != 0:
return -1
swapped += [num] * abs(freq // 2)
swapped.sort()
minNum = min(min(basket1), min(basket2))
# Other than directly swap basket1[i] and basket2[j], we can swap basket1[i]
# with `minNum` first then swap `minNum` with basket2[j], and vice versa.
# That's why we take min(2 * minNum, num) in the below.
return sum(min(2 * minNum, num) for num in swapped[0:len(swapped) // 2]) # code by PROGIEZ
