Computer Science
Updated 7 days ago | GitHub

Advantage Shuffle

Problem Highlights

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Why should we pair a and b if a > b?
    • Because every card in A is larger than b, any card we place in front of b will score a point. We might as well use the weakest card to pair with b as it makes the rest of the cards in A strictly larger, and thus have more potential to score points.
  • Can we assume array nums2 is sorted?
    • Yes

Run through a set of example cases:

HAPPY CASE
Input: nums1 = [2,7,11,18], nums2 = [1,11,4,11]
Output: [2,18,7,11]

Input: nums1 = [1,1,1,1], nums2 = [0,0,0,0]
Output: [1,1,1,1]

EDGE CASE
Input: nums1 = [1,0,0,1000000], nums2 = [0,0,0,0]
Output: [1000000,1,0,0]

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

  • A greedy solution can be applied here, where the current smallest card to beat in B will always be b = sortedB[j]. For each card a in sortedA, we will either have a beat that card b (put a into assigned[b]), or throw a out (put a into remaining). For each number n in A, the optimal solution is to find the minimum number in B m such that n > m.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: For each value in nums2, we ideally want to pick a number from nums1 that is just higher to match up against it. If we had a sorted nums2 as well, we could just match up the values very easily in descending order. Create an index order lookup array and sort it in reference to the values in nums2, then use it as a bridge between the sorted nums1 and unsorted nums2.

1) count elements in A to a map m.
2) for each element in B, find the least bigger element in map m.
3) otherwise, we'll take the smallest element.
4) then we update the m.

⚠️ Common Mistakes

  • Sorting both arrays but losing the original positions of nums2. The answer has to be returned in the original order of nums2, so if you sort nums2 you must track each element’s original index (via a (value, index) pair, as the Java implementation does) and place assignments back at that index.
  • Advancing the nums2 pointer even when the current nums1 card cannot beat it. In the greedy scheme, the pointer for the smallest unmatched nums2 value should only advance when we actually make a winning assignment — otherwise the “wasted” nums1 card should be set aside for a later slot rather than counted as an attempt against the current opponent.
  • Discarding “useless” cards instead of placing them in the answer. When a nums1 card cannot beat any remaining nums2 value, it still has to appear in the output — the greedy strategy pairs it with the largest remaining nums2 value so the stronger cards stay available for opponents they can actually beat.

4: I-mplement

Implement the code to solve the algorithm.

def advantageCount(A, B):
    sortedA = sorted(A)
    sortedB = sorted(B)

    # assigned[b] = list of a that are assigned to beat b
    # remaining = list of a that are not assigned to any b
    assigned = {b: [] for b in B}
    remaining = []

    # populate (assigned, remaining) appropriately
    # sortedB[j] is always the smallest unassigned element in B
    j = 0
    for a in sortedA:
        if a > sortedB[j]:
            assigned[sortedB[j]].append(a)
            j += 1
        else:
            remaining.append(a)

    # reconstruct the answer from annotations (assigned, remaining)
    return [assigned[b].pop() if assigned[b] else remaining.pop() for b in B]

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        
        int[] answer = new int[n];
		
	// we would have to store elements with indexes, so that we remember
	// where to place nums1 elements.
        List<int[]> list = new ArrayList<>();
        
        for(int i = 0; i < n; ++i) {
            list.add(new int[] {nums2[i], i});
        }
        
	// sort elements in descending order
        Collections.sort(list, (a, b) -> Integer.compare(b[0], a[0]));
		
	// sort in ascending order
	// we can use two pointers to pick elements from left and right ends of nums1
        Arrays.sort(nums1);
        
        for(int i = 0, left  = 0, right = n - 1; left <= right; ++i) {
            int[] current = list.get(i);
            
	    // right pointer will always point to the highest element of nums1 
	    // which isn't used yet
            if(current[0] < nums1[right]) {
                answer[current[1]] = nums1[right--];
            } else {
			
		// the easiest permutation would be to pick the smallest element,
		// as they would never contribute to increasing nums1's advantage over nums2.
                answer[current[1]] = nums1[left++];
            }
        }
        
        return answer;
    }
}

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

  • Trace through your code with an input to check for the expected output
  • Catch possible edge cases and off-by-one errors

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

  • Time Complexity: O(N log N), where N is the length of A and B.
  • Space Complexity: O(N)