Rearranging Fruits solution and explanation
Google
9 more videos on this problem
Rearranging Fruits | Detailed Explanation | Minute Details | Leetcode 2561 | codestorywithMIKcodestorywithMIK · 41:10 · 12K views
Rearranging Fruits | Leetcode 2561Techdose · 33:21 · 3K views
2561. Rearranging Fruits | Leetcode Daily - PythonLeetcode Daily · 6:06 · 2K views
Leetcode 2561 🔥 Rearranging Fruits | Greedy + HashMap + Java Logic | Daily Challenge Study Placement · 15:43 · 2K views
2561. Rearranging Fruits | LeetCode HardDeep Tech · 16:13 · 1K views
Rearranging Fruits | Weekly Contest 331 | LeetcodecodingMohan · 20:58 · 1K views
Daily Leetcode #1950: Aug 02, 2025 - 2561. Rearranging FruitsProgramming Live with Larry · 35:56 · 1K views
2561. Rearranging Fruits (Leetcode Hard)Programming Live with Larry · 20:21 · 755 views
[Beats 100% Solution] 2561. Rearranging Fruits [LeetCode Weekly Contest]TheGrayMind · 14:42 · 751 views
Rearranging Fruits : LeetCode POTD | LeetCode 2561Code With Vyk · 19:15 · 643 views
The problem
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
iandj, and swap theithfruit ofbasket1with thejthfruit ofbasket2. - 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.
Constraints:
basket1.length == basket2.length1 <= basket1.length <= 1051 <= basket1[i],basket2[i] <= 109
Approach overview
Problem Overview: You are given two baskets of fruits represented as arrays. Each value represents the cost of a fruit. The goal is to make both baskets identical by swapping fruits between them while minimizing the total swap cost. A swap costs the minimum value of the two fruits involved. If it is impossible to balance the baskets, return -1.
Approach 1: Sort and Compare (O(n log n) time, O(n) space)
Start by counting how many times each fruit value appears across both baskets. If any fruit has an odd total frequency, balancing is impossible because swaps always move fruits in pairs. After validation, identify the extra fruits that must move out of each basket. Store these extras in two arrays and sort them.
Traverse the sorted arrays and calculate the cost of pairing mismatched fruits. A key optimization comes from using the globally smallest fruit as an intermediate swap when direct swaps are expensive. For each pair, compute min(direct_swap_cost, 2 * global_min). Sorting ensures you match cheapest elements first, which minimizes the total cost. This approach relies heavily on array manipulation and greedy pairing, commonly seen in array and greedy problems.
Approach 2: Frequency Map Balancing (O(n log n) time, O(n) space)
This approach focuses on balancing counts using a hash map. Build a frequency difference map between the two baskets. Positive values indicate extra fruits in the first basket; negative values indicate extras in the second. Each imbalance must be corrected by swaps.
Expand the imbalance map into a list of required moves. For example, if a fruit appears four extra times, it contributes two swap operations. After collecting all required elements, sort the list and process the smallest half since each swap fixes two elements. Again apply the greedy rule: choose the cheaper option between a direct swap and swapping through the global minimum fruit. Hash-based counting makes imbalance detection straightforward and highlights patterns typical in hash table problems.
Recommended for interviews: The frequency map balancing approach is usually preferred. It demonstrates strong understanding of counting techniques, greedy optimization, and swap cost minimization. Interviewers expect candidates to first detect the feasibility condition (even total frequencies), then reduce the problem to pairing surplus elements efficiently. The sorted greedy pairing step shows awareness of cost optimization patterns often used in hard array problems.
Approach 1: Approach 1: Sort and Compare
This approach involves sorting both baskets and then attempting to swap elements such that both baskets can be made equal. The key is to minimize the cost of swaps using the given operation constraint, min(basket1[i], basket2[j]). By leveraging sorting, we ensure that similar elements are aligned, facilitating minimal swaps.
def min_cost_swap(basket1, basket2):
basket1.sort()
basket2.sort()
i = 0
j = 0
cost = 0
while i < len(basket1) and j < len(basket2):
if basket1[i] == basket2[j]:
i += 1
j += 1
elif basket1[i] < basket2[j]:
return -1
else:
cost += basket1[i]
i += 1
return cost if i == len(basket1) and j == len(basket2) else -1
print(min_cost_swap([4, 2, 2, 2], [1, 4, 1, 2]))import java.util.Arrays;
public class Main {
public static int minCostSwap(int[] basket1, int[] basket2) {
Arrays.sort(basket1);
Arrays.sort(basket2);
int i = 0, j = 0, cost = 0;
while (i < basket1.length && j < basket2.length) {
if (basket1[i] == basket2[j]) {
i++;
j++;
} else if (basket1[i] < basket2[j]) {
return -1;
} else {
cost += basket1[i];
i++;
}
}
return i == basket1.length && j == basket2.length ? cost : -1;
}
public static void main(String[] args) {
int[] basket1 = {4, 2, 2, 2};
int[] basket2 = {1, 4, 1, 2};
System.out.println(minCostSwap(basket1, basket2));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int minCostSwap(std::vector<int>& basket1, std::vector<int>& basket2) {
std::sort(basket1.begin(), basket1.end());
std::sort(basket2.begin(), basket2.end());
int i = 0, j = 0, cost = 0;
while (i < basket1.size() && j < basket2.size()) {
if (basket1[i] == basket2[j]) {
i++;
j++;
} else if (basket1[i] < basket2[j]) {
return -1;
} else {
cost += basket1[i];
i++;
}
}
return i == basket1.size() && j == basket2.size() ? cost : -1;
}
int main() {
std::vector<int> basket1 = {4, 2, 2, 2};
std::vector<int> basket2 = {1, 4, 1, 2};
std::cout << minCostSwap(basket1, basket2) << std::endl;
return 0;
}function minCostSwap(basket1, basket2) {
basket1.sort((a, b) => a - b);
basket2.sort((a, b) => a - b);
let i = 0, j = 0, cost = 0;
while (i < basket1.length && j < basket2.length) {
if (basket1[i] == basket2[j]) {
i++;
j++;
} else if (basket1[i] < basket2[j]) {
return -1;
} else {
cost += basket1[i];
i++;
}
}
return i == basket1.length && j == basket2.length ? cost : -1;
}
console.log(minCostSwap([4, 2, 2, 2], [1, 4, 1, 2]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int minCostSwap(int *basket1, int basket1Size, int *basket2, int basket2Size) {
qsort(basket1, basket1Size, sizeof(int), compare);
qsort(basket2, basket2Size, sizeof(int), compare);
int i = 0, j = 0, cost = 0;
while (i < basket1Size && j < basket2Size) {
if (basket1[i] == basket2[j]) {
i++;
j++;
} else if (basket1[i] < basket2[j]) {
return -1; // Impossible to make equal
} else {
cost += basket1[i]; // Calculate swap cost
i++;
}
}
return i == basket1Size && j == basket2Size ? cost : -1;
}
int main() {
int basket1[] = {4, 2, 2, 2};
int basket2[] = {1, 4, 1, 2};
int result = minCostSwap(basket1, 4, basket2, 4);
printf("%d\n", result);
return 0;
}using System;
public class Program {
public static int MinCostSwap(int[] basket1, int[] basket2) {
Array.Sort(basket1);
Array.Sort(basket2);
int i = 0, j = 0, cost = 0;
while (i < basket1.Length && j < basket2.Length) {
if (basket1[i] == basket2[j]) {
i++;
j++;
} else if (basket1[i] < basket2[j]) {
return -1;
} else {
cost += basket1[i];
i++;
}
}
return i == basket1.Length && j == basket2.Length ? cost : -1;
}
public static void Main() {
int[] basket1 = {4, 2, 2, 2};
int[] basket2 = {1, 4, 1, 2};
Console.WriteLine(MinCostSwap(basket1, basket2));
}
}In Python, the solution is concise, utilizing Python's built-in sorting and tuple unpacking to iterate and manipulate indices.
Time Complexity: O(n log n) from sorting.
Space Complexity: O(1).
Approach 2: Approach 2: Frequency Map Balancing
This approach focuses on using frequency maps (hashmaps) to account for unmatched elements between the baskets. By using frequency counts and balancing the excesses in both baskets, we aim to minimize the swaps required.
def min_cost_freq_map(basket1, basket2):
from collections import Counter
freq1 = Counter(basket1)
freq2 = Counter(basket2)
cost = 0
for key in set(freq1.keys()).union(freq2.keys()):
diff = abs(freq1.get(key, 0) - freq2.get(key, 0)) // 2
cost += diff * key
return cost
print(min_cost_freq_map([4, 2, 2, 2], [1, 4, 1, 2]))import java.util.HashMap;
public class Main {
public static int minCostFreqMap(int[] basket1, int[] basket2) {
HashMap<Integer, Integer> freq1 = new HashMap<>();
HashMap<Integer, Integer> freq2 = new HashMap<>();
for (int cost : basket1) {
freq1.put(cost, freq1.getOrDefault(cost, 0) + 1);
}
for (int cost : basket2) {
freq2.put(cost, freq2.getOrDefault(cost, 0) + 1);
}
int cost = 0;
for (int key : freq1.keySet()) {
int diff = Math.abs(freq1.get(key) - freq2.getOrDefault(key, 0)) / 2;
cost += diff * key;
}
for (int key : freq2.keySet()) {
if (!freq1.containsKey(key)) {
cost += freq2.get(key) * key;
}
}
return cost;
}
public static void main(String[] args) {
int[] basket1 = {4, 2, 2, 2};
int[] basket2 = {1, 4, 1, 2};
System.out.println(minCostFreqMap(basket1, basket2));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
#include <cmath>
int minCostFreqMap(std::vector<int>& basket1, std::vector<int>& basket2) {
std::unordered_map<int, int> freq1, freq2;
for (const auto& cost : basket1) {
freq1[cost]++;
}
for (const auto& cost : basket2) {
freq2[cost]++;
}
int cost = 0;
for (const auto& [key, value] : freq1) {
if (freq2.count(key)) {
int diff = abs(value - freq2[key]) / 2;
cost += diff * key;
freq1[key] -= diff;
freq2[key] -= diff;
} else {
cost += value * key;
}
}
for (const auto& [key, value] : freq2) {
if (!freq1.count(key)) {
cost += value * key;
}
}
return cost;
}
int main() {
std::vector<int> basket1 = {4, 2, 2, 2};
std::vector<int> basket2 = {1, 4, 1, 2};
std::cout << minCostFreqMap(basket1, basket2) << std::endl;
return 0;
}function minCostFreqMap(basket1, basket2) {
let freq1 = {};
let freq2 = {};
let countFreq = (arr, freq) => {
arr.forEach(el => {
freq[el] = (freq[el] || 0) + 1;
});
};
countFreq(basket1, freq1);
countFreq(basket2, freq2);
let cost = 0;
let allKeys = new Set([...Object.keys(freq1), ...Object.keys(freq2)]);
allKeys.forEach(key => {
let diff = Math.abs((freq1[key] || 0) - (freq2[key] || 0)) / 2;
cost += diff * key;
});
return cost;
}
console.log(minCostFreqMap([4, 2, 2, 2], [1, 4, 1, 2]));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int minCostFreqMap(int *basket1, int basket1Size, int *basket2, int basket2Size) {
int freq1[1000001] = {0};
int freq2[1000001] = {0};
for (int i = 0; i < basket1Size; i++) {
freq1[basket1[i]]++;
freq2[basket2[i]]++;
}
int cost = 0;
for (int i = 0; i <= 1000000; i++) {
if (freq1[i] != freq2[i]) {
int diff = abs(freq1[i] - freq2[i]) / 2;
if (freq1[i] > freq2[i]) {
cost += diff * i;
freq1[i] -= diff;
} else {
cost += diff * i;
freq2[i] -= diff;
}
}
}
return cost;
}
int main() {
int basket1[] = {4, 2, 2, 2};
int basket2[] = {1, 4, 1, 2};
int result = minCostFreqMap(basket1, 4, basket2, 4);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class Program {
public static int MinCostFreqMap(int[] basket1, int[] basket2) {
var freq1 = new Dictionary<int, int>();
var freq2 = new Dictionary<int, int>();
foreach (var cost in basket1) {
if (freq1.ContainsKey(cost)) freq1[cost]++;
else freq1[cost] = 1;
}
foreach (var cost in basket2) {
if (freq2.ContainsKey(cost)) freq2[cost]++;
else freq2[cost] = 1;
}
int cost = 0;
foreach (var key in freq1.Keys) {
int diff = Math.Abs(freq1[key] - freq2.GetValueOrDefault(key, 0)) / 2;
cost += diff * key;
}
return cost;
}
public static void Main() {
int[] basket1 = {4, 2, 2, 2};
int[] basket2 = {1, 4, 1, 2};
Console.WriteLine(MinCostFreqMap(basket1, basket2));
}
}Python's Counter is utilized to register frequency counts. This solution balances frequency discrepancies to compute necessary swap costs.
Time Complexity: O(n + m), m is the distinct element count.
Space Complexity: O(m) due to utilization of collections.
Approach 3: Greedy + Construction
First, we can remove the common elements from both arrays. For the remaining numbers, the occurrence of each number must be even, otherwise, it is impossible to construct identical arrays. Let's denote the arrays after removing common elements as a and b.
Next, we consider how to perform the swaps.
If we want to swap the smallest number in a, we need to find the largest number in b to swap with it; similarly, if we want to swap the smallest number in b, we need to find the largest number in a to swap with it. This can be achieved by sorting.
However, there is another swapping scheme. We can use a smallest number mi as a transition element, first swap the number in a with mi, and then swap mi with the number in b. In this way, the cost of swapping is 2 times mi.
In the code implementation, we can directly merge arrays a and b into an array nums, and then sort the array nums. Next, we enumerate the first half of the numbers, calculate the minimum cost each time, and add it to the answer.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array.
function minCost(basket1: number[], basket2: number[]): number {
const n = basket1.length;
const cnt: Map<number, number> = new Map();
for (let i = 0; i < n; i++) {
cnt.set(basket1[i], (cnt.get(basket1[i]) || 0) + 1);
cnt.set(basket2[i], (cnt.get(basket2[i]) || 0) - 1);
}
let mi = Number.MAX_SAFE_INTEGER;
const nums: number[] = [];
for (const [x, v] of cnt.entries()) {
if (v % 2 !== 0) {
return -1;
}
for (let i = 0; i < Math.abs(v) / 2; i++) {
nums.push(x);
}
mi = Math.min(mi, x);
}
nums.sort((a, b) => a - b);
const m = nums.length;
let ans = 0;
for (let i = 0; i < m / 2; i++) {
ans += Math.min(nums[i], mi * 2);
}
return ans;
}func minCost(basket1 []int, basket2 []int) (ans int64) {
cnt := map[int]int{}
for i, a := range basket1 {
cnt[a]++
cnt[basket2[i]]--
}
mi := 1 << 30
nums := []int{}
for x, v := range cnt {
if v%2 != 0 {
return -1
}
for i := abs(v) / 2; i > 0; i-- {
nums = append(nums, x)
}
mi = min(mi, x)
}
sort.Ints(nums)
m := len(nums)
for i := 0; i < m/2; i++ {
ans += int64(min(nums[i], mi*2))
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}use std::collections::HashMap;
impl Solution {
pub fn min_cost(basket1: Vec<i32>, basket2: Vec<i32>) -> i64 {
let n = basket1.len();
let mut cnt: HashMap<i32, i32> = HashMap::new();
for i in 0..n {
*cnt.entry(basket1[i]).or_insert(0) += 1;
*cnt.entry(basket2[i]).or_insert(0) -= 1;
}
let mut mi = i32::MAX;
let mut nums = Vec::new();
for (x, v) in cnt {
if v % 2 != 0 {
return -1;
}
for _ in 0..(v.abs() / 2) {
nums.push(x);
}
mi = mi.min(x);
}
nums.sort();
let m = nums.len();
let mut ans = 0;
for i in 0..(m / 2) {
ans += nums[i].min(mi * 2) as i64;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Compare | Time Complexity: O(n log n) from sorting. |
| Approach 2: Frequency Map Balancing | Time Complexity: O(n + m), m is the distinct element count. |
| Greedy + Construction | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Compare | O(n log n) | O(n) | When you explicitly track surplus fruits from both baskets and pair them after sorting. |
| Frequency Map Balancing | O(n log n) | O(n) | General case; easiest way to detect imbalance using hash maps and build swap candidates. |
Frequently asked questions
Is Rearranging Fruits easy or hard?
Rearranging Fruits is categorized as a hard problem because it combines multiple concepts: feasibility checks using frequency counts, greedy cost optimization, and careful handling of swap operations. The tricky part is recognizing that using the global minimum fruit can reduce expensive swaps.
Rearranging Fruits Python/Java solution
Implementations in Python or Java typically use a HashMap or dictionary to count frequencies, build a list of imbalance values, sort them, and compute swap costs using the greedy rule min(direct_cost, 2 * global_min). The same logic translates easily to C++, C#, and JavaScript.
How to solve Rearranging Fruits in O(n)?
A fully O(n) solution is difficult because pairing swaps optimally requires ordering the surplus fruits by value. The standard method sorts the imbalance list, which results in O(n log n) time. Hash maps allow O(n) frequency counting, but the greedy pairing step still needs sorting for minimal cost.
What is the best approach for Rearranging Fruits?
The most reliable approach uses a frequency map to detect surplus fruits in each basket, followed by sorting the swap candidates. After balancing counts, pair elements greedily and compute the minimum cost using either direct swaps or two swaps via the global minimum fruit. The overall complexity is O(n log n).
Is Rearranging Fruits asked at Google/Amazon/Meta?
Problems involving greedy swaps, frequency balancing, and cost minimization frequently appear in interviews at companies like Amazon, Google, and Meta. Rearranging Fruits represents a typical hard-level greedy + hash map pattern used to test algorithmic reasoning and optimization skills.
What data structure is used in Rearranging Fruits?
The core data structures are hash maps for frequency counting and arrays or lists for storing surplus fruits that require swaps. Sorting these arrays enables greedy pairing. The algorithm also tracks the global minimum fruit value to compute cheaper indirect swaps.
What is the time complexity of Rearranging Fruits?
Most optimal solutions run in O(n log n) time because they sort the list of surplus fruits before pairing them. Building the frequency map takes O(n), but sorting the imbalance list dominates the runtime. Space complexity is typically O(n) to store frequency maps and swap candidates.