#2561

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Rearranging Fruits

Solve the problem of rearranging fruit baskets by comparing fruit costs and minimizing swaps using array scanning and hash lookups.

array hash table greedy sort

Problem Statement

You are given two 0-indexed integer arrays, basket1 and basket2, each representing the cost of fruits in two baskets. Both arrays are of the same length, n. Your goal is to make these two baskets identical by performing swaps. Each swap consists of exchanging an element from basket1 with an element from basket2, and you are asked to minimize the total cost of the swaps. Baskets are considered equal if their sorted contents are the same.

Return the minimum cost to make the two baskets equal or -1 if it is impossible to do so. If the baskets cannot be rearranged into identical baskets through any number of swaps, return -1. Constraints ensure that basket lengths are between 1 and 100,000, and the individual element values are between 1 and 1 billion.

Examples

Example 1

Input: basket1 = [4,2,2,2], basket2 = [1,4,1,2]

Output: 1

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

It can be shown that it is impossible to make both the baskets equal.

Constraints

basket1.length == basket2.length
1 <= basket1.length <= 105
1 <= basket1[i], basket2[i] <= 109

Solution Approach

Frequency Maps

Start by creating frequency maps for both basket1 and basket2. This will help identify which elements need to be swapped and how many swaps are required for each fruit type.

Sorting and Scanning

After building the frequency maps, sort both baskets and use a greedy approach to scan both arrays. Minimize the swap cost by pairing the smallest available fruit from both baskets. This helps ensure the least costly swaps.

Cost Calculation

The next step is calculating the cost of the swaps. Iterate through the frequency maps and perform the necessary swaps between the two baskets, keeping track of the total cost of each operation. If no valid swap exists, return -1.

Complexity Analysis

Metric	Value
Time	O(n \log n)
Space	O(n)

The time complexity of this solution is O(n log n) due to the sorting of both arrays. The space complexity is O(n) because we use frequency maps to track the elements in each basket.

What Interviewers Usually Probe

Can the candidate efficiently track and compare element frequencies between two arrays?
Does the candidate recognize the importance of sorting in minimizing swap costs?
How well does the candidate optimize for both time and space complexity in a solution?

Common Pitfalls or Variants

Common pitfalls

Not handling cases where the two arrays contain different sets of elements, making it impossible to match them.
Overlooking the importance of sorting in making swaps efficient, which could lead to a higher swap cost.
Failing to optimize the space complexity by using unnecessary data structures for tracking element frequencies.

Follow-up variants

If the arrays have different sizes, return -1 immediately.
If all elements in the arrays are identical, no swaps are needed.
Consider optimizations for handling very large arrays with a large number of swaps.

FAQ

How do I solve the Rearranging Fruits problem with minimal swap cost?

Start by creating frequency maps for both baskets, then sort and scan both arrays. Minimize swap costs by pairing the smallest elements from both arrays.

What is the time complexity of the Rearranging Fruits problem?

The time complexity is O(n log n), primarily due to the sorting step for both baskets.

Can I optimize the space complexity in the Rearranging Fruits problem?

Yes, you can optimize space by using frequency maps and minimizing unnecessary data structures while still tracking the elements efficiently.

What if the arrays have different sets of elements?

If the arrays contain different elements, it is impossible to make the baskets equal, so you should return -1.

What are common mistakes in solving the Rearranging Fruits problem?

Common mistakes include not handling edge cases where arrays have different elements, failing to minimize swap costs through sorting, and not optimizing space usage.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        cnt = Counter()
        for a, b in zip(basket1, basket2):
            cnt[a] += 1
            cnt[b] -= 1
        mi = min(cnt)
        nums = []
        for x, v in cnt.items():
            if v % 2:
                return -1
            nums.extend([x] * (abs(v) // 2))
        nums.sort()
        m = len(nums) // 2
        return sum(min(x, mi * 2) for x in nums[:m])

Continue Practicing

#2554 maximum number of integers to choose from a range i #2598 smallest missing non negative integer after operations #2499 minimum total cost to make arrays unequal