Skip to content

2561. Rearranging Fruits 👍

  • Time: Quickselect: $O(n)$, Sort: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  long long minCost(vector<int>& basket1, vector<int>& basket2) {
    vector<int> swapped;
    unordered_map<int, int> count;

    for (const int b : basket1)
      ++count[b];

    for (const int b : basket2)
      --count[b];

    for (const auto& [num, freq] : count) {
      if (freq % 2 != 0)
        return -1;
      for (int i = 0; i < abs(freq) / 2; ++i)
        swapped.push_back(num);
    }

    const int minNum = min(ranges::min(basket1), ranges::min(basket2));
    const auto midIt = swapped.begin() + swapped.size() / 2;
    nth_element(swapped.begin(), midIt, swapped.end());
    return accumulate(swapped.begin(), midIt, 0L,
                      [minNum](long subtotal, int num) {
      return subtotal + min(2 * minNum, num);
    });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public long minCost(int[] basket1, int[] basket2) {
    long ans = 0;
    List<Integer> swapped = new ArrayList<>();
    Map<Integer, Integer> count = new HashMap<>();

    for (final int b : basket1)
      count.merge(b, 1, Integer::sum);

    for (final int b : basket2)
      count.merge(b, -1, Integer::sum);

    for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
      final Integer num = entry.getKey();
      final Integer freq = entry.getValue();
      if (freq % 2 != 0)
        return -1;
      for (int i = 0; i < Math.abs(freq) / 2; ++i)
        swapped.add(num);
    }

    final int minNum =
        Math.min(Arrays.stream(basket1).min().getAsInt(), Arrays.stream(basket2).min().getAsInt());
    Collections.sort(swapped);

    for (int i = 0; i < swapped.size() / 2; ++i)
      ans += Math.min(minNum * 2, swapped.get(i));
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
  def minCost(self, basket1: list[int], basket2: list[int]) -> int:
    swapped = []
    count = collections.Counter(basket1)
    count.subtract(collections.Counter(basket2))

    for num, freq in count.items():
      if freq % 2 != 0:
        return -1
      swapped += [num] * abs(freq // 2)

    swapped.sort()
    minNum = min(min(basket1), min(basket2))
    # Other than directly swap basket1[i] and basket2[j], we can swap basket1[i]
    # with `minNum` first then swap `minNum` with basket2[j], and vice versa.
    # That's why we take min(2 * minNum, num) in the below.
    return sum(min(2 * minNum, num) for num in swapped[0:len(swapped) // 2])