algoadvance

You are given an integer array nums of 2n integers. Your task is to:

• Partition the array into n pairs such that:
  • each pair consists of two integers,
  • for every pair (a_i, b_i), the result of min(a_i, b_i) is maximized.
• Return the sum of these minimum values from the pairs.

Example

• Input: nums = [1,4,3,2]
• Output: 4
• Explanation: One optimal partition is (1, 2) and (3, 4). The sum of minimums is 1 + 3 = 4.

Clarifying Questions

1. Q: Can the array nums contain both positive and negative integers? A: Yes, the array can contain both positive and negative integers.

2. Q: Is the number of elements in the list nums always even? A: Yes, the given problem guarantees that nums will have 2n elements, thus it will always have an even number of elements.

3. Q: Can there be duplicate elements in the array nums? A: Yes, duplicate elements are allowed.

Strategy

The strategy revolves around sorting the array first and then pairing the elements such that we maximize the sum of the smallest elements in each pair. By sorting the array, we can simply pair adjacent elements to achieve this:

1. Sort the array: This ensures that each pair (a, b) will be (nums[i], nums[i+1]) where nums[i] is always the smaller or equal member.
2. Sum the smallest elements of the pairs: The resulting sum is the sum of every second element in the sorted list.

Code

def arrayPairSum(nums: list) -> int:
    # Sort the array first
    nums.sort()
    # Initialize the sum
    result = 0
    # Sum the minimum of each pair
    for i in range(0, len(nums), 2):
        result += nums[i]
    return result

# Example Usage
nums = [1, 4, 3, 2]
print(arrayPairSum(nums))  # Output: 4

Explanation

• After sorting nums = [1, 2, 3, 4], the pairs will be (1, 2) and (3, 4).
• The minimum values of the pairs are 1 and 3.
• The sum of these minimum values is 1 + 3 = 4.

Time Complexity

• Sorting the array: (O(n \log n)) where (n) is the number of elements in nums.
• Summing elements after sorting: (O(n / 2) = O(n))

Thus, the overall time complexity is dominated by the sorting step and is (O(n \log n)).

Try our interview co-pilot at AlgoAdvance.com

• 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?