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:
i and j, and swap the ith fruit of basket1 with the jth fruit of basket2.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] <= 109This 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.
In this C code, we first sort both baskets. Then, we iterate through the sorted arrays, comparing elements at each index. If equal, we proceed; if not, we calculate the swap cost using the sorted property. If elements are irreconcilable, we return -1.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as we sort in-place.
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.
This C implementation uses two arrays to keep track of frequencies of costs in each basket. Imbalances are corrected by finding differences and calculating costs using these differences.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where m is the maximum possible value in a basket.
Space Complexity: O(m), used for frequency arrays.
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Compare | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Frequency Map Balancing | Time Complexity: O(n + m), where m is the maximum possible value in a basket. |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,679 views views
Watch 9 more video solutions →Practice Rearranging Fruits with our built-in code editor and test cases.
Practice on FleetCode