algoadvance

Leetcode 561. Array Partition

Problem Statement:

Given an integer array nums of 2n integers, your task is to group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

Example:

1. Input: nums = [1,4,3,2] Output: 4 Explanation: n is 2, and the maximum sum of pairs is min(1, 2) + min(3, 4) = 1 + 3 = 4.

2. Input: nums = [6,2,6,5,1,2] Output: 9 Explanation: n is 3, and the maximum sum of pairs is min(1, 2) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

Clarifying Questions:

1. Q: What is the range of values in the array? A: The values can be any integer within the range defined by the problem constraints.

2. Q: Can nums contain duplicate elements? A: Yes, nums can have duplicate elements.

3. Q: Is the input array always guaranteed to be of even length? A: Yes, as per the problem description, the array length will be 2n.

Strategy:

1. Sorting Approach:
   • Sort the array nums.
   • After sorting, pair elements in such a way that the smallest possible values are paired together.
   • Summing the first element of each pair will maximize the sum of min(ai, bi) as the minimum of each pair would always be the first element of the sorted pair, and it will accumulate the smallest values first.

Code:

public class Solution {
    public int arrayPairSum(int[] nums) {
        // Sort the array
        Arrays.sort(nums);

        int sum = 0;
        // Iterate through the array, taking every second element starting from index 0
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        
        return sum;
    }
}

Time Complexity:

• Time Complexity: The dominant step is the sorting of the array which takes O(n log n) where n is the number of elements in the array nums.
• Space Complexity: The space complexity for this solution is O(1) if we do not account for the space taken by the sorting algorithm itself (assuming it’s an in-place sort). Sorting typically requires O(n) space for auxiliary arrays if the sorting algorithm is not in-place.

This approach ensures that we achieve the maximum sum of min(ai, bi) for given pairs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?