Rearranging Fruits - Practice Coding Problems

Rearranging Fruits - 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:

Choose two indices i and j, and swap the i^th fruit of basket1 with the j^th 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.

Input & Output

Example 1 — Impossible Case

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

› Output: -1

💡 Note: Fruit 1 appears 3 times total (2+1) and fruit 3 appears 1 time total. Since these are odd counts, equal distribution is impossible.

Example 2 — Single Swap

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

› Output: 0

💡 Note: Baskets are already equal, no swaps needed.

Example 3 — Optimal Swaps

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

› Output: 1

💡 Note: Both baskets have same fruit counts: 1 appears 2+2=4 times, 2 appears 1+1=2 times, 4 appears 1+1=2 times. Need to swap one element with cost min(any pair) = 1.

Constraints

1 ≤ basket1.length, basket2.length ≤ 10⁵
basket1.length == basket2.length
1 ≤ basket1[i], basket2[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Baskets

Two baskets with different fruit distributions

Frequency Check

Verify if equal distribution is mathematically possible

Optimal Swaps

Find minimum cost swaps to balance baskets

Key Takeaway

🎯 Key Insight: Use frequency analysis to check feasibility, then greedily match excess elements for minimum swap cost

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is using frequency analysis to determine if equal distribution is possible, then greedily matching excess elements. The optimal approach uses counting and sorting to achieve O(n log n) time complexity with O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Analysis + Greedy	O(n log n)	O(n)	Count frequencies, identify mismatches, and greedily swap cheapest elements
Brute Force - Try All Swaps	O(2^(n²))	O(n)	Try all possible combinations of swaps until baskets are equal

Frequency Analysis + Greedy — Algorithm Steps

Count frequency of each fruit across both baskets
Check if equal distribution is possible
Identify excess elements in each basket
Greedily match excess elements with minimum swap costs

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count each fruit type in both baskets

Find Excess

Identify which fruits are over/under represented

Greedy Match

Match excess fruits with minimum swap cost

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

long long solution(int *basket1, int *basket2, int n) {
    // Simple implementation for small inputs
    int fruits[200];
    int count1[200] = {0}, count2[200] = {0};
    int uniqueCount = 0;
    int minCost = INT_MAX;
    
    // Find unique fruits and their counts
    for (int i = 0; i < n; i++) {
        int found = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (fruits[j] == basket1[i]) {
                count1[j]++;
                found = 1;
                break;
            }
        }
        if (!found) {
            fruits[uniqueCount] = basket1[i];
            count1[uniqueCount]++;
            uniqueCount++;
        }
        if (basket1[i] < minCost) minCost = basket1[i];
    }
    
    for (int i = 0; i < n; i++) {
        int found = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (fruits[j] == basket2[i]) {
                count2[j]++;
                found = 1;
                break;
            }
        }
        if (!found) {
            fruits[uniqueCount] = basket2[i];
            count2[uniqueCount]++;
            uniqueCount++;
        }
        if (basket2[i] < minCost) minCost = basket2[i];
    }
    
    // Check if equal distribution possible
    for (int i = 0; i < uniqueCount; i++) {
        if ((count1[i] + count2[i]) % 2 != 0) {
            return -1;
        }
    }
    
    // Find excess elements
    int excess1[100], excess2[100];
    int e1Count = 0, e2Count = 0;
    
    for (int i = 0; i < uniqueCount; i++) {
        int total = count1[i] + count2[i];
        int target = total / 2;
        
        if (count1[i] > target) {
            for (int j = 0; j < count1[i] - target; j++) {
                excess1[e1Count++] = fruits[i];
            }
        }
        if (count2[i] > target) {
            for (int j = 0; j < count2[i] - target; j++) {
                excess2[e2Count++] = fruits[i];
            }
        }
    }
    
    qsort(excess1, e1Count, sizeof(int), compare);
    qsort(excess2, e2Count, sizeof(int), compare);
    
    long long totalCost = 0;
    for (int i = 0; i < e1Count; i++) {
        int directCost = (excess1[i] < excess2[i]) ? excess1[i] : excess2[i];
        int indirectCost = 2 * minCost;
        totalCost += (directCost < indirectCost) ? directCost : indirectCost;
    }
    
    return totalCost;
}

int main() {
    char line[1000];
    int basket1[100], basket2[100];
    int n1 = 0, n2 = 0;
    
    // Parse first array
    fgets(line, sizeof(line), stdin);
    char *ptr = strchr(line, '[') + 1;
    while (*ptr && *ptr != ']') {
        if ((*ptr >= '0' && *ptr <= '9') || *ptr == '-') {
            basket1[n1++] = atoi(ptr);
            while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
        } else {
            ptr++;
        }
    }
    
    // Parse second array
    fgets(line, sizeof(line), stdin);
    ptr = strchr(line, '[') + 1;
    while (*ptr && *ptr != ']') {
        if ((*ptr >= '0' && *ptr <= '9') || *ptr == '-') {
            basket2[n2++] = atoi(ptr);
            while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
        } else {
            ptr++;
        }
    }
    
    printf("%lld\n", solution(basket1, basket2, n1));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting the excess elements for greedy matching dominates the time complexity

⚡ Linearithmic

Space Complexity

O(n)

Hash map to store frequencies and arrays to store excess elements

⚡ Linearithmic Space

25.4K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Frequency Analysis + Greedy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler