Advantage Shuffle - Practice Coding Problems

Advantage Shuffle - Problem

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.

Input & Output

Example 1 — Basic Advantage

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

› Output: [2,11,7,15]

💡 Note: We rearrange nums1 to [2,11,7,15]. Comparing with nums2=[1,10,4,11]: 2>1 ✓, 11>10 ✓, 7>4 ✓, 15>11 ✓. All 4 positions give advantage.

Example 2 — Partial Advantage

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

› Output: [24,32,8,12]

💡 Note: Optimal arrangement: 24>13 ✓, 32>25 ✓, 8≤32 ✗, 12>11 ✓. We get 3 advantages out of 4 possible.

Example 3 — Minimum Case

$ Input: nums1 = [3,5], nums2 = [6,4]

› Output: [5,3]

💡 Note: With 2 elements: 5≤6 ✗, 3≤4 ✗. No advantage possible, but [5,3] is one valid arrangement.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums1=[2,7,11,15] vs nums2=[1,10,4,11]

Find Optimal Arrangement

Use greedy strategy to maximize advantages

Result

Rearranged nums1=[2,11,7,15] achieves 4 wins

Key Takeaway

🎯 Key Insight: Use greedy strategy - assign the smallest element that can win, or waste the smallest if no win is possible

Asked in

G Google 25 a Amazon 18 M Microsoft 15 A Apple 12

The key insight is to use a greedy strategy: for each element in nums2, assign the smallest element from nums1 that can beat it, or waste the smallest element if no win is possible. Best approach is Greedy with Sorting with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Sorting	O(n log n)	O(n)	Sort both arrays and use greedy strategy to match elements optimally
Brute Force - Try All Permutations	O(n! × n)	O(n)	Generate all permutations of nums1 and find the one with maximum advantage

Greedy with Sorting — Algorithm Steps

Sort nums1 and create sorted index-value pairs for nums2
For each nums2 element, find smallest nums1 element that can beat it
If no element can beat it, assign the smallest remaining nums1 element
Reconstruct result array using original indices

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Arrays

Sort nums1 and create sorted pairs for nums2

Greedy Assignment

For each nums2 element, use smallest winning nums1 element

Reconstruct

Build final result array using original indices

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int value;
    int index;
} Pair;

int comparePairs(const void* a, const void* b) {
    return ((Pair*)a)->value - ((Pair*)b)->value;
}

int compareInts(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int* solution(int* nums1, int* nums2, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    
    // Sort nums1
    int* sortedNums1 = (int*)malloc(numsSize * sizeof(int));
    int* available = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        sortedNums1[i] = nums1[i];
        available[i] = 1;
    }
    qsort(sortedNums1, numsSize, sizeof(int), compareInts);
    
    // Create (value, index) pairs for nums2 and sort by value
    Pair* nums2Pairs = (Pair*)malloc(numsSize * sizeof(Pair));
    for (int i = 0; i < numsSize; i++) {
        nums2Pairs[i].value = nums2[i];
        nums2Pairs[i].index = i;
    }
    qsort(nums2Pairs, numsSize, sizeof(Pair), comparePairs);
    
    int* result = (int*)malloc(numsSize * sizeof(int));
    
    // For each element in nums2 (sorted by value)
    for (int p = 0; p < numsSize; p++) {
        int value = nums2Pairs[p].value;
        int idx = nums2Pairs[p].index;
        int assigned = 0;
        
        // Try to find the smallest element in nums1 that can beat this value
        for (int i = 0; i < numsSize; i++) {
            if (available[i] && sortedNums1[i] > value) {
                result[idx] = sortedNums1[i];
                available[i] = 0;
                assigned = 1;
                break;
            }
        }
        
        // If no element can beat it, use the smallest remaining element
        if (!assigned) {
            for (int i = 0; i < numsSize; i++) {
                if (available[i]) {
                    result[idx] = sortedNums1[i];
                    available[i] = 0;
                    break;
                }
            }
        }
    }
    
    free(sortedNums1);
    free(available);
    free(nums2Pairs);
    
    return result;
}

int main() {
    int nums1[1000], nums2[1000];
    int n = 0;
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if ((token[0] >= '0' && token[0] <= '9') || token[0] == '-') {
            nums1[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int m = 0;
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    while (token != NULL) {
        if ((token[0] >= '0' && token[0] <= '9') || token[0] == '-') {
            nums2[m++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* result = solution(nums1, nums2, n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting both arrays takes O(n log n), then single pass through arrays

⚡ Linearithmic

Space Complexity

O(n)

Extra space for sorted arrays and result array

⚡ Linearithmic Space

89.2K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Sorting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler