Can this be solved in O(n) time (leetcode - 561. Array Partition)?

Question

Can this question be solved in O(n) time? (leetcode - 561. Array Partition)

Given an integer array nums of 2n integers, 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: All possible pairings (ignoring the ordering of elements) are:

• (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
• (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
• (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4 So the maximum possible sum is 4.

Example 2:

Input: nums = [6,2,6,5,1,2]

Output: 9

Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

Constraints:

• 1 <= n <= 104
• nums.length == 2 * n
• -104 <= nums[i] <= 104

This is my solution so far with O(nlog(n)) time:

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        for i in range(0,len(nums),2):
            ans+=nums[i]
        return ans

Answer 1

I think the best we can do here is O(sorting time) which is O(n log n) unless there's something special about your input.

1. Sort the array.
2. Pair adjacent elements.
3. Return the sum of the mins of each pair == sum of vals at even indices.