Rearranging fruits

Array Hash Table Greedy Sort

57.5% acceptance

Feb 25, 2026

935

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: Choose 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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(basket1: Vec<i32>, basket2: Vec<i32>) -> i64 {
    use std::collections::HashMap;
    let mut combined: HashMap<i32, i32> = HashMap::new();
    for &x in &basket1 { *combined.entry(x).or_insert(0) += 1; }
    for &x in &basket2 { *combined.entry(x).or_insert(0) += 1; }

    // Each fruit type must appear an even number of times total
    for &v in combined.values() {
      if v % 2 != 0 { return -1; }
    }

    let global_min = basket1.iter().chain(basket2.iter()).copied().min().unwrap();

    let mut cnt1: HashMap<i32, i32> = HashMap::new();
    for &x in &basket1 { *cnt1.entry(x).or_insert(0) += 1; }

    // Find excess in basket1 (has more than half of combined)
    let mut excess1: Vec<i32> = Vec::new();
    let mut excess2: Vec<i32> = Vec::new();
    for (&k, &total) in &combined {
      let half = total / 2;
      let c1 = *cnt1.get(&k).unwrap_or(&0);
      if c1 > half {
        for _ in 0..(c1 - half) { excess1.push(k); }
      } else if c1 < half {
        for _ in 0..(half - c1) { excess2.push(k); }
      }
    }

    excess1.sort_unstable();
    excess2.sort_unstable_by(|a, b| b.cmp(a)); // descending

    // Pair smallest excess1 with largest excess2 to minimize sum of min(a, b).
    // For each pair, cost = min(direct_swap, indirect via global_min)
    excess1.iter().zip(excess2.iter())
      .map(|(&a, &b)| (a.min(b)).min(2 * global_min) as i64)
      .sum()
  }
}