2561. Rearranging Fruits Hard

1/**
2 * [2561] Rearranging Fruits
3 *
4 * 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:
5 *
6 * Chose two indices i and j, and swap the i^th fruit of basket1 with the j^th fruit of basket2.
7 * The cost of the swap is min(basket1[i],basket2[j]).
8 *
9 * Two baskets are considered equal if sorting them according to the fruit cost makes them exactly the same baskets.
10 * Return the minimum cost to make both the baskets equal or -1 if impossible.
11 *  
12 * <strong class="example">Example 1:
13 *
14 * Input: basket1 = [4,2,2,2], basket2 = [1,4,1,2]
15 * Output: 1
16 * 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.
17 *
18 * <strong class="example">Example 2:
19 *
20 * Input: basket1 = [2,3,4,1], basket2 = [3,2,5,1]
21 * Output: -1
22 * Explanation: It can be shown that it is impossible to make both the baskets equal.
23 *
24 *  
25 * Constraints:
26 *
27 * basket1.length == bakste2.length
28 * 1 <= basket1.length <= 10^5
29 * 1 <= basket1[i],basket2[i] <= 10^9
30 *
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/rearranging-fruits/
35// discuss: https://leetcode.com/problems/rearranging-fruits/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38impl Solution {
39    pub fn min_cost(basket1: Vec<i32>, basket2: Vec<i32>) -> i64 {
40        // Create a BTreeMap to count the frequency of each fruit cost in both baskets
41        let costs = std::collections::BTreeMap::<i32, i32>::new();
42
43        // Count the frequency of each fruit cost in basket1
44        let costs = basket1.iter().fold(costs, |mut costs, &cost| {
45            *costs.entry(cost).or_insert(0) += 1;
46            costs
47        });
48
49        // Count the frequency of each fruit cost in basket2
50        let costs = basket2.iter().fold(costs, |mut costs, &cost| {
51            *costs.entry(cost).or_insert(0) -= 1;
52            costs
53        });
54
55        // Create a vec to store the costs of swapping fruits with the same cost
56        let mut swaps = Vec::<i32>::new();
57
58        // Iterate over each fruit cost and its frequency in the BTreeMap
59        for (cost, count) in costs
60            .iter()
61            .map(|(&cost, &count)| (cost, count.abs() as usize))
62        {
63            // If the frequency of a fruit cost is odd in either basket, return -1
64            if count & 1 > 0 {
65                return -1;
66            }
67            // Add the cost of swapping half of the fruits with each other
68            swaps.extend(std::iter::repeat(cost).take(count >> 1));
69        }
70
71        // Initialize the cost of swapping fruits
72        let mut cost = 0;
73
74        // Get the smallest fruit cost
75        if let Some(small) = costs.keys().next().map(|&val| val as i64) {
76            // Add the cost of swapping each pair of fruits with the same cost
77            for swap in swaps.iter().take(swaps.len() >> 1).map(|&val| val as i64) {
78                cost += swap.min(2 * small);
79            }
80        }
81
82        cost
83    }
84}
85
86/*
87The time complexity of this solution is O(n log n), where n is the total number of fruits in both baskets.
88
89The main operation that contributes to the time complexity is the sorting of the fruits in both baskets, which takes O(n log n) time. This sorting is done implicitly by using a BTreeMap, which sorts its keys in ascending order.
90
91The other operations, such as counting the frequency of each fruit cost in both baskets and creating a vec of swap costs, have time complexity O(n). However, as n log n is a higher-order term than n, it dominates the overall time complexity of the solution.
92*/
93
94// submission codes end
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99
100    #[test]
101    fn test_2561() {
102        let basket1 = vec![4, 2, 2, 2];
103        let basket2 = vec![1, 4, 1, 2];
104        let expected = 1;
105
106        let result = Solution::min_cost(basket1, basket2);
107        assert_eq!(result, expected);
108    }
109}
110