Skip to main content
Talentd

Advantage Shuffle - Solution & Explanation

MediumArrayTwo PointersGreedySorting8 min readAsked at: Amazon, Palo Alto Networks, Walmart Labs
Practice this problem

Problem Statement

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 <= 105
  • nums2.length == nums1.length
  • 0 <= nums1[i], nums2[i] <= 109

Approach Overview

Problem Overview: You are given two arrays of equal length. Rearrange nums1 so that the number of indices where nums1[i] > nums2[i] is maximized. The challenge is deciding which elements should "compete" against each value in nums2 to gain the most wins.

Approach 1: Greedy with Sorting and Two Pointers (O(n log n) time, O(n) space)

This method uses a classic greedy strategy combined with sorting. Sort nums1 in ascending order. Then sort the indices of nums2 by their values. Use two pointers on nums1: one pointing to the smallest element and another to the largest. Iterate through nums2 from its largest value down. If the largest remaining value in nums1 can beat the current nums2 value, assign it and move the right pointer. Otherwise, sacrifice the smallest value in nums1. This greedy choice ensures strong numbers are reserved for winnable comparisons while weaker numbers are used where winning is impossible.

The algorithm performs a single pass after sorting and builds the result array directly. Sorting dominates the runtime, giving O(n log n) time and O(n) extra space for the result and index mapping.

Approach 2: Optimal Utilization with Map and Binary Search (O(n log n) time, O(n) space)

This version maintains an ordered map (such as TreeMap) of available values from nums1. For each element in nums2, perform a binary search to find the smallest number strictly greater than it. If such a value exists, use it and remove it from the map. Otherwise, remove the smallest available number and assign it as a deliberate loss.

The key insight: always use the minimum number that still beats the current value. That preserves larger numbers for future comparisons. Balanced tree operations like insertion, lookup, and removal take O(log n), and since they run for every element, the total complexity is O(n log n) with O(n) space.

This approach is conceptually clean and works well in languages with built-in ordered maps. It highlights the "assign the smallest winning candidate" greedy rule and relies heavily on array iteration plus binary search inside the map.

Recommended for interviews: The greedy sorting + two pointer solution is what most interviewers expect. It shows you recognize the "Tian Ji horse racing" pattern: use strong elements to beat winnable matches and sacrifice weak ones otherwise. The map + binary search method is also acceptable, but the two-pointer approach is simpler and usually preferred during whiteboard discussions.

Approach 1: Approach 1: Greedy with Sorting and Two Pointers

This approach involves sorting the arrays and using a two-pointer technique to maximize the advantage. By sorting, we can easily find which elements can pair to maximize the advantage.

Steps:

  • Sort nums1 and create an array of indices of nums2 sorted based on values.
  • Use two pointers to assign elements from nums1 to the sorted indices of nums2, ensuring we maximize comparisons where nums1[i] > nums2[i].
This Python solution sorts nums1 and uses two pointers to optimally distribute its elements to maximize advantage. Unsuited elements replace the largest unmatched element from nums2 which minimizes their impact.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n log n), primarily due to sorting of arrays.

Space Complexity: O(n), due to the storage of results and sorted indices.

Try this approach in the editor →

Approach 2: Approach 2: Optimal Utilization with Map and Binary Search

This method involves using a map to store elements of nums1 and using binary search to quickly find the smallest usable element to maximize the advantage.

Steps:

  • Store frequencies of elements of nums1 in a map.
  • For each element in nums2, find the smallest greater element from the map to maximize the advantage, using binary search capabilities.
  • Adjust map accordingly after each selection.
This Java solution leverages sorted TreeMap to find and assign the smallest advantageous element from nums1 for each element in nums2. Efficient for matching large sets due to logarithmic lookup complexity.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n log n), due to sorting and map operations.

Space Complexity: O(n), as we store frequencies in a map.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Greedy with Sorting and Two Pointers

Time Complexity: O(n log n), primarily due to sorting of arrays.

Space Complexity: O(n), due to the storage of results and sorted indices.

Approach 2: Optimal Utilization with Map and Binary Search

Time Complexity: O(n log n), due to sorting and map operations.

Space Complexity: O(n), as we store frequencies in a map.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Sorting and Two PointersO(n log n)O(n)Best general solution. Easy to reason about and commonly expected in interviews.
Map with Binary Search (TreeMap)O(n log n)O(n)Useful when an ordered map or multiset is available and binary search on remaining values is convenient.

Video Solution

Advantage Shuffle | Live Coding with Explanation | Leetcode - 870 • Algorithms Made Easy • 2,702 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Advantage Shuffle easy or hard?
Advantage Shuffle is rated Medium on LeetCode. The coding itself is straightforward once the greedy idea is clear, but recognizing the strategy of sacrificing smaller values and saving larger ones for winnable comparisons can take practice.
Advantage Shuffle Python/Java solution
Python implementations usually sort nums1 and use index sorting for nums2, then assign values with two pointers. Java solutions often use either the same greedy sorting approach or a TreeMap to perform ceiling lookups. Both achieve O(n log n) time and O(n) space.
How to solve Advantage Shuffle in O(n)?
A strict O(n) solution is not typical because sorting or ordered lookups are required to determine optimal pairings. The practical optimal solution is O(n log n) using sorting with a greedy two-pointer strategy. Any approach that needs ordering comparisons between elements generally requires sorting or balanced-tree operations.
What is the best approach for Advantage Shuffle?
The most common solution uses a greedy strategy with sorting and two pointers. Sort nums1 and process nums2 in descending order. If the largest remaining element in nums1 can beat the current nums2 value, assign it; otherwise sacrifice the smallest element. This runs in O(n log n) time due to sorting and uses O(n) space.
Is Advantage Shuffle asked at Google/Amazon/Meta?
Advantage Shuffle represents a common greedy matching pattern similar to problems asked at major tech companies including Google, Amazon, and Meta. Variants of this problem appear in interviews where candidates must maximize wins between two arrays using sorting and greedy decisions.
What data structure is used in Advantage Shuffle?
The main structures are arrays combined with sorting and two-pointer traversal. Some implementations also use ordered maps such as TreeMap or multiset structures to perform binary search for the smallest element greater than a target.
What is the time complexity of Advantage Shuffle?
Most optimal implementations run in O(n log n) time. The complexity comes from sorting one or both arrays or performing O(log n) ordered-map operations for each element. Space complexity is typically O(n) to store the result and auxiliary structures.

Ready to solve this problem?

Practice Advantage Shuffle with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays