LeetCode 870 - Advantage Shuffle

The problem asks us to maximize the advantage of one array over another. Given two arrays nums1 and nums2 of equal length, the advantage is defined as the number of positions i where nums1[i] nums2[i]. Our task is to rearrange nums1 to maximize this advantage.

leetcodemediumarraytwo-pointersgreedysorting

LeetCode Problem 870

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to maximize the advantage of one array over another. Given two arrays nums1 and nums2 of equal length, the advantage is defined as the number of positions i where nums1[i] > nums2[i]. Our task is to rearrange nums1 to maximize this advantage.

The input arrays represent two sets of numbers, and we want to "beat" the numbers in nums2 as often as possible using numbers from nums1. The output should be a permutation of nums1 where each element is assigned to a position against nums2 to maximize the count of nums1[i] > nums2[i]. The constraints indicate the arrays can be as long as 100,000 elements and values can be up to 1 billion, so brute force comparison of all permutations is infeasible.

Important edge cases include arrays where all elements are equal, arrays where nums1 has smaller elements than nums2, arrays with repeated elements, and arrays with maximum allowed sizes.

Approaches

Brute Force: One naive approach is to generate all permutations of nums1 and compute the advantage for each permutation. We would then select the permutation with the maximum advantage. While this guarantees correctness, it is computationally infeasible because generating all permutations of nums1 requires O(n!) time, which is impossible for n up to 10^5.

Optimal Approach: The key insight is to use a greedy strategy combined with sorting. By sorting nums1 in ascending order and pairing it against nums2 sorted by value, we can assign the smallest number in nums1 that is still larger than the current nums2 element. If no such number exists, we assign the smallest number in nums1 (a "sacrifice") to lose minimally. This ensures each number in nums2 is either beaten by the smallest sufficient number in nums1 or loses with the smallest element, maximizing the total advantage.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n!) Check all permutations of nums1
Optimal O(n log n) O(n) Sort arrays and assign greedily using two pointers

Algorithm Walkthrough

  1. Sort nums1 in ascending order so we can efficiently find the smallest number that can beat an element in nums2.
  2. Pair elements in nums2 with their original indices and sort by value. This allows us to reconstruct the final permutation of nums1 in the original order of nums2.
  3. Use a deque for nums1 (or two pointers approach). For each element val in the sorted nums2:
  • If the largest remaining number in nums1 is greater than val, assign it to that position.
  • Otherwise, assign the smallest remaining number in nums1 (a "sacrifice") to that position.
  1. Return the constructed permutation of nums1 which maximizes the advantage.

Why it works: Sorting allows us to make locally optimal decisions that are globally optimal. Each number in nums2 is either beaten by the smallest number in nums1 that is larger, or is assigned the smallest remaining number to minimize wasted value. This guarantees the total advantage is maximized.

Python Solution

from typing import List
from collections import deque

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        sorted_nums1 = deque(sorted(nums1))
        sorted_nums2 = sorted([(val, idx) for idx, val in enumerate(nums2)])
        res = [0] * len(nums1)
        
        for val, idx in reversed(sorted_nums2):
            if sorted_nums1[-1] > val:
                res[idx] = sorted_nums1.pop()
            else:
                res[idx] = sorted_nums1.popleft()
        
        return res

Explanation: We first sort nums1 and nums2 (with indices). Using a deque for nums1 allows efficient removal from both ends. We iterate over nums2 in descending order and either assign the largest available number that can beat val or the smallest remaining number. The res array stores the final permutation.

Go Solution

package main

import (
    "sort"
)

func advantageCount(nums1 []int, nums2 []int) []int {
    n := len(nums1)
    sortedNums1 := make([]int, n)
    copy(sortedNums1, nums1)
    sort.Ints(sortedNums1)
    
    type pair struct {
        val, idx int
    }
    
    sortedNums2 := make([]pair, n)
    for i, v := range nums2 {
        sortedNums2[i] = pair{v, i}
    }
    sort.Slice(sortedNums2, func(i, j int) bool { return sortedNums2[i].val < sortedNums2[j].val })
    
    res := make([]int, n)
    left, right := 0, n-1
    for i := n-1; i >= 0; i-- {
        if sortedNums1[right] > sortedNums2[i].val {
            res[sortedNums2[i].idx] = sortedNums1[right]
            right--
        } else {
            res[sortedNums2[i].idx] = sortedNums1[left]
            left++
        }
    }
    
    return res
}

Go-specific notes: We use a struct to pair values with indices since Go does not have tuples. Sorting slices and using two pointers achieves the same logic as Python's deque approach. Slice copying avoids mutating the input nums1.

Worked Examples

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

  1. Sort nums1: [2,7,11,15]
  2. Pair and sort nums2: [(1,0),(4,2),(10,1),(11,3)]
  3. Iterate in reverse:
  • 11: largest 15 > 11, assign 15 → index 3
  • 10: largest 11 > 10, assign 11 → index 1
  • 4: largest 7 > 4, assign 7 → index 2
  • 1: largest 2 > 1, assign 2 → index 0

Result: [2,11,7,15]

Example 2: nums1 = [12,24,8,32], nums2 = [13,25,32,11]

  1. Sort nums1: [8,12,24,32]
  2. Pair and sort nums2: [(11,3),(13,0),(25,1),(32,2)]
  3. Iterate in reverse:
  • 32: largest 32 ≤ 32, assign smallest 8 → index 2
  • 25: largest 32 > 25, assign 32 → index 1
  • 13: largest 24 > 13, assign 24 → index 0
  • 11: largest 12 > 11, assign 12 → index 3

Result: [24,32,8,12]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting nums1 and nums2 dominates the runtime
Space O(n) Extra space for sorted nums2 with indices and result array

The algorithm scales efficiently up to the constraint limit of 10^5.

Test Cases

# Basic examples
assert Solution().advantageCount([2,7,11,15], [1,10,4,11]) == [2,11,7,15]  # example 1
assert Solution().advantageCount([12,24,8,32], [13,25,32,11]) == [24,32,8,12]  # example 2

# Edge cases
assert Solution().advantageCount([1], [1]) == [1]  # single element, equal
assert Solution().advantageCount([1], [2]) == [1]  # single element, nums1 < nums2
assert Solution().advantageCount([5,5,5], [1,2,3]) == [5,5,5]  # nums1 all greater
assert Solution().advantageCount([1,2,3], [4,5,6]) == [1,2,3]  # nums1 all smaller
assert Solution().advantageCount([2,2,2,2], [2,2,2,2]) == [2,2,2,2]  # repeated elements
Test Why
[2,7,11,15] vs [1,10,4,11] validates normal case with mixed advantage
[12,24,8,32] vs [13,25,32,11] validates larger numbers and partial advantage
[1] vs [1] minimal input with equal values
[1] vs [2] minimal input with nums