Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

870. Advantage Shuffle

Time: $O(n\log n)$

Space: $O(n)$

			


class Solution {
 public:
  vector<int> advantageCount(vector<int>& A, vector<int>& B) {
    multiset<int> set{begin(A), end(A)};

    for (int i = 0; i < B.size(); ++i) {
      auto p = *rbegin(set) <= B[i] ? begin(set) : set.upper_bound(B[i]);
      A[i] = *p;
      set.erase(p);
    }

    return A;
  }
};




			


class Solution {
  public int[] advantageCount(int[] A, int[] B) {
    TreeMap<Integer, Integer> map = new TreeMap<>();

    for (int a : A)
      map.put(a, map.getOrDefault(a, 0) + 1);

    for (int i = 0; i < B.length; i++) {
      Integer key = map.higherKey(B[i]);
      if (key == null)
        key = map.firstKey();
      map.put(key, map.get(key) - 1);
      if (map.get(key) == 0)
        map.remove(key);
      A[i] = key;
    }

    return A;
  }
}




			


from sortedcontainers import SortedList


class Solution:
  def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
    sl = SortedList(A)

    for i, b in enumerate(B):
      index = 0 if sl[-1] <= b else sl.bisect_right(b)
      A[i] = sl[index]
      del sl[index]

    return A