LeetCode 870: Advantage Shuffle Solution

Master LeetCode problem 870 (Advantage Shuffle), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

870. Advantage Shuffle

Medium

Array Two Pointers Greedy Sorting

Problem Explanation

Explanation

To maximize the advantage of nums1 over nums2, we can sort both arrays and then greedily assign each element in nums1 to an element in nums2 such that the advantage is maximized. We can achieve this by using a priority queue (min-heap) to keep track of the elements in nums2 in a sorted manner. We iterate over the sorted nums1 array and for each element, we check if we can find a number in nums2 larger than it. If we find one, we assign it; otherwise, we assign the smallest number in nums2 that hasn't been assigned yet.

Time complexity: O(n log n) where n is the length of nums1 or nums2 (since we are sorting) Space complexity: O(n)

Solution Code

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < nums2.length; i++) {
            pq.add(new int[]{nums2[i], i});
        }
        Arrays.sort(nums2);
        
        int low = 0, high = nums1.length - 1;
        int[] result = new int[nums1.length];
        
        for (int num : nums1) {
            if (num > nums2[low]) {
                result[pq.poll()[1]] = num;
                low++;
            } else {
                result[pq.poll()[1]] = num;
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 870 (Advantage Shuffle)?

This page provides optimized solutions for LeetCode problem 870 (Advantage Shuffle) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 870 (Advantage Shuffle)?

The time complexity for LeetCode 870 (Advantage Shuffle) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 870 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 870 in Java, C++, or Python.

Back to LeetCode Solutions