Maximize first array using elements from second array
Filed under Microsoft
Free read 1 of 3Understand whether 'maximize' means lexicographical maximization or sum maximization.
The question
Given two arrays of equal size, maximize the first array lexicographically or sum-wise by replacing its elements with elements from the second array. Each element from the second array can be used at most once.
Constraints
- Array lengths are equal, up to 10^5.
- Elements can be negative, zero, or positive integers.
Examples
- Input
- arr1 = [1, 2, 3], arr2 = [3, 2, 1]
- Output
- [3, 2, 1]
- Why
- We can sort both arrays or use a greedy approach to place the largest possible elements into arr1.
Approach
Understand whether 'maximize' means lexicographical maximization or sum maximization.
Generate all permutations of the second array and test all possible swaps, leading to factorial time complexity.
Sort both arrays or use sorting combined with a greedy strategy to match the largest available elements from the second array with the first array.
Empty arrays, arrays with identical elements, and handling negative numbers correctly.
Tips
- What they are testing: Test with duplicate elements, completely smaller/larger second arrays, and arrays with negative numbers.
- Common mistake: Failing to track used elements from the second array correctly or not considering the optimal pairing strategy.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.