2025-08-06 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 6

Description

Fruits Into Baskets III

You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth basket.

From left to right, place the fruits according to these rules:

  • Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
  • Each basket can hold only one type of fruit.
  • If a fruit type cannot be placed in any basket, it remains unplaced.

Return the number of fruit types that remain unplaced after all possible allocations are made.

 

Example 1:

Input: fruits = [4,2,5], baskets = [3,5,4]

Output: 1

Explanation:

  • fruits[0] = 4 is placed in baskets[1] = 5.
  • fruits[1] = 2 is placed in baskets[0] = 3.
  • fruits[2] = 5 cannot be placed in baskets[2] = 4.

Since one fruit type remains unplaced, we return 1.

Example 2:

Input: fruits = [3,6,1], baskets = [6,4,7]

Output: 0

Explanation:

  • fruits[0] = 3 is placed in baskets[0] = 6.
  • fruits[1] = 6 cannot be placed in baskets[1] = 4 (insufficient capacity) but can be placed in the next available basket, baskets[2] = 7.
  • fruits[2] = 1 is placed in baskets[1] = 4.

Since all fruits are successfully placed, we return 0.

 

Constraints:

  • n == fruits.length == baskets.length
  • 1 <= n <= 105
  • 1 <= fruits[i], baskets[i] <= 109

Solution

inline constexpr int lowbit(int x) {
  return x & -x;
}
class BITS {
  int size = 0;
  vector<int> container;
public:
  BITS(int n): container(n), size(n) {}
  BITS(vector<int> &original) {
    size = original.size() + 1;
    container.resize(size + 1);
    for(int i = 1; i <= size; ++i) {
      update(i, original[i - 1], original);
    }
  }

  int query(int x) {
    int result = 0;
    while(x >= 1) {
      result = max(result, container[x]);
      x -= 1;
      while(x - lowbit(x) >= 1) {
        result = max(result, container[x]);
        x -= lowbit(x);
      }
    }
    return result;
  }

  void update(int x, int val, vector<int> &original) {
    original[x - 1] = val;
    while(x < size) {
      container[x] = original[x - 1];
      for(int i = 1; i < lowbit(x); i *= 2) {
        container[x] = max(container[x], container[x - i]);
      }
      x += lowbit(x);
    }
  }
};
class Solution {
public:
  int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
    int len = baskets.size();
    BITS bits(len + 1);
    for(int i = 0; i < len; ++i) {
      bits.update(i + 1, baskets[i],baskets);
    }
    // for(int i = 1; i <= len; ++i) {
    //   cout << bits.query(i) << ' ';
    // }
      cout << endl;
    int answer = 0;
    for(auto f : fruits) {
      int low = 1;
      int high = len;
      while(low < high) {
        int mid = (low + high) / 2;
        if(bits.query(mid) < f) {
          low = mid + 1;
        } else {
          high = mid;
        }
      }
      if(baskets[low - 1] < f) {
        answer += 1;
      } else {
        bits.update(low, 0, baskets);
      }
      
      // for(int i = 1; i <= len; ++i) {
      //   cout << bits.query(i) << ' ';
      // }
      // cout << endl;
    }
    return answer;
  }
};

// Accepted
// 740/740 cases passed (1270 ms)
// Your runtime beats 5.06 % of cpp submissions
// Your memory usage beats 91.85 % of cpp submissions (179.5 MB)
Algorithm