870. Advantage Shuffle

Problem Description

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.

Examples:

Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]
Explanation: The advantage is max by placing:
2 > 1
11 > 10
7 > 4
15 > 11

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⁹

Python Solution

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # Sort nums1 in ascending order
        nums1.sort()
        
        # Create array of indices sorted by nums2 values in descending order
        indices = sorted(range(len(nums2)), key=lambda i: -nums2[i])
        
        # For each number in nums2 (from largest to smallest)
        # Use the largest number in nums1 that's greater than it
        # If no such number exists, use the smallest number in nums1
        left, right = 0, len(nums1) - 1
        result = [0] * len(nums1)
        
        for i in indices:
            if nums1[right] > nums2[i]:
                result[i] = nums1[right]
                right -= 1
            else:
                result[i] = nums1[left]
                left += 1
        
        return result

Implementation Notes:

• Uses greedy approach with sorting
• Time complexity: O(n log n)
• Space complexity: O(n)

Java Solution

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        
        // Sort nums1
        Arrays.sort(nums1);
        
        // Create array of indices sorted by nums2 values
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        Arrays.sort(indices, (a, b) -> nums2[b] - nums2[a]);
        
        // Match numbers using two pointers
        int[] result = new int[n];
        int left = 0, right = n - 1;
        
        for (int i = 0; i < n; i++) {
            if (nums1[right] > nums2[indices[i]]) {
                result[indices[i]] = nums1[right--];
            } else {
                result[indices[i]] = nums1[left++];
            }
        }
        
        return result;
    }
}

C++ Solution

class Solution {
public:
    vector advantageCount(vector& nums1, vector& nums2) {
        int n = nums1.size();
        
        // Sort nums1
        sort(nums1.begin(), nums1.end());
        
        // Create array of indices sorted by nums2 values
        vector indices(n);
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(),
             [&](int i, int j) { return nums2[i] > nums2[j]; });
        
        // Match numbers using two pointers
        vector result(n);
        int left = 0, right = n - 1;
        
        for (int i = 0; i < n; i++) {
            if (nums1[right] > nums2[indices[i]]) {
                result[indices[i]] = nums1[right--];
            } else {
                result[indices[i]] = nums1[left++];
            }
        }
        
        return result;
    }
};

JavaScript Solution

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var advantageCount = function(nums1, nums2) {
    const n = nums1.length;
    
    // Sort nums1
    nums1.sort((a, b) => a - b);
    
    // Create array of indices sorted by nums2 values
    const indices = Array.from({length: n}, (_, i) => i);
    indices.sort((a, b) => nums2[b] - nums2[a]);
    
    // Match numbers using two pointers
    const result = new Array(n);
    let left = 0, right = n - 1;
    
    for (let i = 0; i < n; i++) {
        if (nums1[right] > nums2[indices[i]]) {
            result[indices[i]] = nums1[right--];
        } else {
            result[indices[i]] = nums1[left++];
        }
    }
    
    return result;
};

C# Solution

public class Solution {
    public int[] AdvantageCount(int[] nums1, int[] nums2) {
        int n = nums1.Length;
        
        // Sort nums1
        Array.Sort(nums1);
        
        // Create array of indices sorted by nums2 values
        var indices = Enumerable.Range(0, n).ToArray();
        Array.Sort(indices, (a, b) => nums2[b].CompareTo(nums2[a]));
        
        // Match numbers using two pointers
        int[] result = new int[n];
        int left = 0, right = n - 1;
        
        for (int i = 0; i < n; i++) {
            if (nums1[right] > nums2[indices[i]]) {
                result[indices[i]] = nums1[right--];
            } else {
                result[indices[i]] = nums1[left++];
            }
        }
        
        return result;
    }
}

Implementation Notes:

• Uses sorting and two-pointer technique
• Time complexity: O(n log n)
• Space complexity: O(n)