In this guide, you will get 561. Array Partition LeetCode Solution with the best time and space complexity. The solution to Array Partition problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.
Example 2:
1 <= n <= 104
nums.length == 2 * n
-104 <= nums[i] <= 104
Complexity Analysis
Time Complexity: O(n) \to O(\texttt{sort})
Space Complexity: O(1) \to O(\texttt{sort})
561. Array Partition LeetCode Solution in C++
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
int ans = 0;
ranges::sort(nums);
for (int i = 0; i < nums.size(); i += 2)
ans += nums[i];
return ans;
}
}; /* code provided by PROGIEZ */
561. Array Partition LeetCode Solution in Java
class Solution {
public int arrayPairSum(int[] nums) {
int ans = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length; i += 2)
ans += nums[i];
return ans;
}
} // code provided by PROGIEZ
561. Array Partition LeetCode Solution in Python
class Solution:
def arrayPairSum(self, nums: list[int]) -> int:
return sum(sorted(nums)[::2]) # code by PROGIEZ
