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 maximum sum.

Clarifying Questions

  1. What is the range of values for the integers in the array nums?
    • The values can be very large or small, but they are always within the range of standard integer values in C++.
  2. Can the array values be negative?
    • Yes, the array values can be negative, zero, or positive.
  3. Is n always guaranteed to be a positive integer?
    • Yes, n is always guaranteed to be a positive integer such that the length of nums is 2n.

Strategy

The key insight here is to recognize that to maximize the sum of min(ai, bi), we should try to make pairs with the smallest difference between ai and bi. Sorting the array will help us achieve this.

Detailed Steps:

  1. Sort the array. Once the array is sorted, pairs of neighboring numbers will give the most optimized result because it minimizes the difference between pairs.
  2. Sum up the first element of each pair. After sorting, we sum the elements at even indices (0, 2, 4, …) because those will contribute to the final result when paired optimally.

Example:

Suppose nums = [1, 4, 3, 2].

Time Complexity:

Code

#include <vector>
#include <algorithm>

class Solution {
public:
    int arrayPairSum(std::vector<int>& nums) {
        // Sort the array
        std::sort(nums.begin(), nums.end());
        
        int max_sum = 0;
        // Sum up the elements at even indices
        for (size_t i = 0; i < nums.size(); i += 2) {
            max_sum += nums[i];
        }
        
        return max_sum;
    }
};

This solution sorts the input array and then iterates through it to calculate the sum of the minimums of each pair, which efficiently maximizes the sum according to the problem’s requirement.

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