901. Advantage Shuffle¶

Difficulty: Medium

901. Advantage Shuffle

Medium

You are given two integer arrays nums1 and nums2 both of the same length. The advantage of nums1 with respect to nums2 is the number of indices i for which nums1[i] > nums2[i].

Return any permutation of nums1 that maximizes its advantage with respect to nums2.

Example 1:

Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]

Example 2:

Input: nums1 = [12,24,8,32], nums2 = [13,25,32,11]
Output: [24,32,8,12]

Constraints:

1 <= nums1.length <= 10⁵
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 10⁹

Solution¶

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int ans[] = new int[n];
        TreeSet<Integer> set = new TreeSet<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int ele : nums1) {
            set.add(ele);
            map.put(ele, map.getOrDefault(ele, 0) + 1);
        }
        for (int i = 0; i < n; i++) {
            int current_ele = nums2[i];
            Integer next = set.higher(current_ele);
            if (next != null) {
                ans[i] = next;
                map.put(next, map.getOrDefault(next, 0) -1);
                if (map.getOrDefault(next, 0) == 0) set.remove(next);
            }
            else {
                ans[i] = set.first();
                map.put(set.first(), map.getOrDefault(set.first(), 0) -1);
                if (map.getOrDefault(set.first(), 0) == 0) set.remove(set.first());
            }
        }
        return ans;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here