870. Advantage Shuffle
Problem Description
In the given problem, we are provided with two integer arrays nums1
and nums2
of the same length. The term advantage refers to the number of positions i
at which the element in nums1
is greater than the corresponding element in nums2
, meaning nums1[i] > nums2[i]
. The goal is to rearrange nums1
in such a way that it maximizes the advantage with respect to nums2
. This means we need to reorder the elements in nums1
so that as many elements as possible are greater than the corresponding elements in nums2
when they are compared index-wise.
Intuition
The intuition behind solving this problem involves sorting and greedy strategy. First, we sort nums1
because we want to arrange its elements in an increasing order to match them with the elements from nums2
efficiently. We also sort nums2
, but since we need to create a resulting array that corresponds to the original indices of nums2
, we track the original indices by creating tuples (value, index)
.
For the solution approach, we employ a two-pointer technique. We consider the smallest element in nums1
and try to match it with the smallest element in nums2
. If the current element in nums1
does not exceed the smallest remaining element of nums2
, it cannot contribute to the advantage. In such a case, we assign it to the position of the largest element of nums2
where it's less likely to affect the advantage negatively.
On the other hand, if the current element in nums1
can surpass the smallest element in nums2
, we place it in the result array at the corresponding index and move to the next element in both nums1
and nums2
. This process is repeated until all elements in nums1
are placed into the result. This greedy approach ensures that we maximize the advantage by matching each 'nums1' element with the best possible counterpart in 'nums2'.
Learn more about Greedy, Two Pointers and Sorting patterns.
Solution Approach
The implementation of the solution approach is based on a sorted array, greedy algorithm, and two-pointer technique. Here's a step-by-step breakdown:
-
Sorting
nums1
: We start by sortingnums1
in non-decreasing order, which allows us to consider the smallest elements first and match them againstnums2
. -
Create and Sort tuple array for
nums2
: We create tuples containing the value and the original index fromnums2
and sort this array. This sorting helps us to consider the elements ofnums2
from the smallest to the largest, while remembering their original positions. -
Initialize the result array: We initialize an empty result array
ans
with the same length asnums1
andnums2
, which will store the final permutation ofnums1
maximizing the advantage. -
Two-pointer approach: We set up two pointers,
i
to point at the start andj
to point at the end of the sortednums2
tuple array. These pointers will be used to traverse the elements in the tuple array. -
Iterating over
nums1
and placing elements intoans
:- We iterate over each element
v
innums1
. For each elementv
, we look at the smallest yet-to-be-assigned element innums2
(pointed to byi
). - If
v
is less than or equal tot[i][0]
(the smallest element innums2
), the elementv
cannot contribute to the advantage. We then assignv
toans
at the index of the largest yet-to-be-assigned element innums2
(pointed to byj
), and decrementj
. - If
v
is greater thant[i][0]
,v
can contribute to the advantage. We assignv
toans
at the index of the smallest yet-to-be-assigned element innums2
(pointed to byi
), and incrementi
.
- We iterate over each element
-
Returning the result: After iterating through all elements in
nums1
, theans
array now represents a permutation ofnums1
that has been greedily arranged to maximize the advantage overnums2
. We returnans
as the final output.
The algorithm uses sorting and greedy matching to ensure each element from nums1
is used optimally against an element in nums2
, thus achieving the maximum advantage. Data structures used include an array of tuples for tracking nums2
elements with their original indices, and an additional array for constructing the result.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider two example arrays nums1 = [12, 24, 8, 32]
and nums2 = [13, 25, 32, 11]
. We aim to find a permutation of nums1
that maximizes the number of indices at which nums1[i]
is greater than nums2[i]
.
Following the solution approach:
-
Sorting
nums1
: We sortnums1
to[8, 12, 24, 32]
. -
Create and Sort tuple array for
nums2
: We create tuple pairs ofnums2
with their indices:[(13, 0), (25, 1), (32, 2), (11, 3)]
. After sorting, we get[(11, 3), (13, 0), (25, 1), (32, 2)]
. -
Initialize the result array (
ans
): We setans
as an empty array of the same length:[0, 0, 0, 0]
. -
Two-pointer approach: We initialize two pointers:
i
starts at 0 andj
starts at 3 (pointing at the first and last index of the sortednums2
tuple array). -
Iterating over
nums1
:- We compare
8
fromnums1
with11
(the smallest element innums2
tuple array). Since8
is less than11
, it can't contribute to the advantage. Place8
atans[2]
(index of largestnums2
which is 32) and decrementj
to2
. - Now, compare
12
fromnums1
with11
fromnums2
(current smallest).12
is greater, so it can contribute to the advantage. Place12
atans[3]
(index of current smallest innums2
) and incrementi
to1
. - Next, compare
24
fromnums1
with13
(new smallest innums2
).24
is greater, so it can also contribute to the advantage. Place24
atans[0]
and incrementi
to2
. - Lastly,
32
fromnums1
is compared with25
(new smallest innums2
).32
is greater and contributes to the advantage. Place32
atans[1]
and incrementi
to3
.
- We compare
-
Returning the result: The final
ans
array is[24, 32, 8, 12]
, representing the permutation ofnums1
that gives us the maximum advantage overnums2
.
By applying this solution approach to the given arrays, we successfully arranged nums1
([24, 32, 8, 12]
) to maximize the advantage against nums2
([13, 25, 32, 11]
), resulting in an advantage at 3 positions: at indices 0, 1, and 3.
Solution Implementation
1from typing import List
2
3class Solution:
4 def advantageCount(self, A: List[int], B: List[int]) -> List[int]:
5 # Sort the first list to efficiently assign elements
6 A.sort()
7
8 # Create tuples of value and index from list B, then sort these tuples.
9 # This will allow us to compare elements in A with the sorted elements of B.
10 sorted_B_with_indices = sorted((value, index) for index, value in enumerate(B))
11
12 # Initialize the length variable for convenience and readability.
13 length = len(B)
14
15 # Initialize the answer list with placeholder zeros.
16 answer = [0] * length
17
18 # Initialize two pointers for the sorted B list.
19 left_pointer, right_pointer = 0, length - 1
20
21 # Iterate over the sorted list A and try to assign an advantage
22 for value in A:
23 # If the current value in A is greater than the smallest unassigned value in B,
24 # we can assign it as an advantage over B.
25 if value > sorted_B_with_indices[left_pointer][0]:
26 answer[sorted_B_with_indices[left_pointer][1]] = value
27 left_pointer += 1
28 # Otherwise, there is no advantage, so assign the value to the largest
29 # remaining element in B to discard it as efficiently as possible.
30 else:
31 answer[sorted_B_with_indices[right_pointer][1]] = value
32 right_pointer -= 1
33
34 return answer
35
36# Example of using the class and method above:
37# solution = Solution()
38# print(solution.advantageCount([12,24,8,32], [13,25,32,11]))
39
1import java.util.Arrays;
2
3class Solution {
4 public int[] advantageCount(int[] A, int[] B) {
5 int n = A.length; // Length of input arrays
6 int[][] sortedBWithIndex = new int[n][2]; // Array to keep track of B's elements and their indices
7
8 // Fill the array with pairs {value, index} for B
9 for (int i = 0; i < n; ++i) {
10 sortedBWithIndex[i] = new int[] {B[i], i};
11 }
12
13 // Sort the array of pairs by their values (the values from B)
14 Arrays.sort(sortedBWithIndex, (a, b) -> a[0] - b[0]);
15 // Sort array A to efficiently find the advantage count
16 Arrays.sort(A);
17
18 int[] result = new int[n]; // Result array to store the advantage count
19 int left = 0; // Pointer for the smallest value in A
20 int right = n - 1; // Pointer for the largest value in A
21
22 // Iterate through A to determine the advantage
23 for (int value : A) {
24 // If the current value is less than or equal to the smallest in sortedBWithIndex,
25 // put the value at the end of result (because it doesn't have an advantage)
26 // and decrease the right pointer
27 if (value <= sortedBWithIndex[left][0]) {
28 result[sortedBWithIndex[right--][1]] = value;
29 } else {
30 // If the current value has an advantage (is larger),
31 // assign it to the corresponding index in the result array
32 // and increase the left pointer
33 result[sortedBWithIndex[left++][1]] = value;
34 }
35 }
36
37 return result; // Return the advantage array
38 }
39}
40
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 // The function is intended to find an "advantage" permutation of nums1
8 // such that for each element in nums2, there is a corresponding element in
9 // nums1 that is greater. The output is a permutation of nums1 that maximizes
10 // the number of elements in nums1 that are greater than elements in nums2 at
11 // the same index.
12 vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
13 // Get the size of the input vectors
14 int n = nums1.size();
15
16 // Create a vector of pairs to hold elements from nums2 and their indices
17 vector<pair<int, int>> nums2WithIndices;
18 for (int i = 0; i < n; ++i) {
19 nums2WithIndices.push_back({nums2[i], i});
20 }
21
22 // Sort the nums2WithIndices based on the values of nums2
23 sort(nums2WithIndices.begin(), nums2WithIndices.end());
24
25 // Sort nums1 in ascending order
26 sort(nums1.begin(), nums1.end());
27
28 // Use a two-pointer approach to assign elements from nums1 to nums2
29 // Start i from the beginning and j from the end
30 int i = 0, j = n - 1;
31
32 // The ans vector will store the "advantaged" permutation of nums1
33 vector<int> ans(n);
34
35 for (int num : nums1) {
36 // If the current num in nums1 is less than or equal to the smallest
37 // unprocessed num in nums2, then this num in nums1 cannot have advantage
38 // over any unprocessed nums in nums2. So, assign it to the largest remaining
39 // num in nums2 (by decreasing index "j").
40 //
41 // If num is greater, assign it to the current smallest unprocessed num in
42 // nums2 (by increasing index "i") for the advantage.
43 if (num <= nums2WithIndices[i].first) {
44 ans[nums2WithIndices[j--].second] = num;
45 } else {
46 ans[nums2WithIndices[i++].second] = num;
47 }
48 }
49
50 // Return the final "advantaged" permutation
51 return ans;
52 }
53};
54
1function advantageCount(nums1: number[], nums2: number[]): number[] {
2 // Determine the length of the arrays.
3 const length = nums1.length;
4
5 // Create an index array for sorting the indices based on nums2 values.
6 const indexArray = Array.from({ length }, (_, i) => i);
7 indexArray.sort((i, j) => nums2[i] - nums2[j]);
8
9 // Sort nums1 in ascending order to easily find the next greater element.
10 nums1.sort((a, b) => a - b);
11
12 // Initialize an answer array with zeroes to store results.
13 const answerArray = new Array(length).fill(0);
14 let leftPointer = 0;
15 let rightPointer = length - 1;
16
17 for (let i = 0; i < length; i++) {
18 // If current element is greater than the smallest element in nums2,
19 // assign it to the index where nums2 is smallest.
20 if (nums1[i] > nums2[indexArray[leftPointer]]) {
21 answerArray[indexArray[leftPointer]] = nums1[i];
22 leftPointer++;
23 } else {
24 // Otherwise, assign it to the index where nums2 is the largest.
25 answerArray[indexArray[rightPointer]] = nums1[i];
26 rightPointer--;
27 }
28 }
29
30 // Return the answer array where each element in nums1 has been placed
31 // to maximise the number of elements in nums1 that are greater than
32 // the element at the same index in nums2.
33 return answerArray;
34}
35
Time and Space Complexity
The given Python code sorts both arrays and then iterates through them to match elements in nums1
with elements in nums2
in a way that optimizes the advantage condition. Here's the computational complexity analysis of the code provided:
Time Complexity
-
Sorting
nums1
: Sorting an array of sizen
using a comparison-based sort like Timsort (the default in Python) usually takesO(n log n)
time. -
Creating and sorting
t
: The list comprehension first iterates overnums2
to create a list of tuples where each tuple contains an element and its index. This operation takesO(n)
. The listt
is then sorted, which again takesO(n log n)
time. -
Iterating and building the
ans
array: The main loop iterates over every element innums1
, which isn
operations. Within each operation, it performs constant time checks and assignments, so this step isO(n)
.
When combining these steps, the sorting operations dominate the complexity, so the total time complexity is O(n log n)
.
Space Complexity
-
The sorted list of tuples
t
: This requiresO(n)
space to store the elements ofnums2
along with their indices. -
The answer list
ans
: This also requiresO(n)
space to store the final output. -
The temporary variables used for indexing (
i
,j
, etc.): These are a constant number of extra space,O(1)
.
Adding these up, the total space complexity of the algorithm is O(n)
(since the O(n)
space for the ans
array and for the list t
is the significant factor, and the constant space is negligible).
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.