Array Partition Problem in Java

Last Updated : 6 Apr 2026

The array partition problem is a common algorithmic challenge where an array is divided into two or more parts based on specific constraints such as equal sum, minimum difference, fixed size, or maximum pairs. Given an integer array nums consisting of 2n integers, your task is to group these integers into n pairs such that:

(a₁, b₁), (a₂, b₂), …, (a_n, b_n)

For each pair (a_i, b_i), take the minimum value from the pair.

Our objective is to maximize the total sum of these minimum values.

Return the maximum possible sum of:

Example 1:

Input: int nums = [1, 4, 3, 2]

Output: 4

Explanation: All possible pairings (ignoring the ordering of elements) are:

(1, 4), (2, 3) → 1 + 2 = 3

(1, 3), (2, 4) → 1 + 2 = 3

(1, 2), (3, 4) → 1 + 3 = 4

The maximum possible sum is 4.

Example 2:

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

Output: 9

Explanation: After optimal pairing: (1, 2), (2, 5), (6, 6).

Sum = 1 + 2 + 6 = 9.

Example 3:

Input: int nums = [7, 3, 1, 0, 0, 6]

Output: 7

Explanation:

Sorted array becomes [0, 0, 1, 3, 6, 7].

Pairs: (0, 0), (1, 3), (6, 7).

Sum = 0 + 1 + 6 = 7.

Example 4:

Input: int nums = [5, 5, 5, 5]

Output: 10

Explanation:

Sorted array = [5, 5, 5, 5].

Pairs: (5, 5), (5, 5).

Sum = 5 + 5 = 10.

Example 5:

Input: int nums = [-1, -2, -3, -4]

Output: -6

Explanation:

Sorted array = [-4, -3, -2, -1].

Pairs: (-4, -3), (-2, -1).

Sum = -4 + (-2) = -6.

Approach 1: Sorting + Greedy (Optimal Approach)

A Dual-Pivot Quicksort is used by the Arrays.sort() method to reorder elements in ascending order (for primitives). The smallest element in each pair naturally appears at even indices after sorting. Without explicitly creating pairs, the loop directly accesses these minimal values by increasing by 2. After sorting, these values are effectively combined in linear time using the accumulation variable sum.

Example

import java.util.Arrays;
public class Main {
    public static int arrayPairSum(int[] nums) {
        // Sort the array in ascending order
        Arrays.sort(nums);
        int sum = 0;
        // Add elements at even indices
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];  // minimum element in each pair
        }
        return sum;
    }
    public static void main(String[] args) {
        int[] nums = {1,4,3,2};
        System.out.println(arrayPairSum(nums));
    }
}

Compile and Run

Output:

Complexity Analysis

The time complexity of the above code is O(N log N) and the space complexity is O(1), where 'N' represents the number of elements in the array.

Approach 2: Counting Sort Optimization

This method simulates sorting in linear time using a frequency array. Negative numbers are handled via the offset +10000. In order to simulate selecting even-indexed components from a sorted structure, the boolean flag add ensures alternate selection. We use frequency traversal to implicitly recreate sorted order rather than sorting explicitly.

Example

import java.io.*;
import java.util.*;
public class Main {
    public static int arrayPairSum(int[] nums) {
        int[] count = new int[20001];  // Range from -10000 to 10000
        // Step 1: Store frequency
        for (int num : nums) {
            count[num + 10000]++;
        }
        int sum = 0;
        boolean add = true;
        // Step 2: Traverse frequency array
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                if (add) {
                    sum += (i - 10000);
                }
                add = !add;  // alternate picking
                count[i]--;
            }
        }
        return sum;
    }
    public static void main(String[] args) {
        int[] nums = {1, 4, 3, 2};
        int result = arrayPairSum(nums);
        System.out.println(arrayPairSum(nums));
    }
}

Compile and Run

Output:

Complexity Analysis

The time complexity of the above code is O(N + k) (where k = 20001) and the space complexity is O(1), where 'N' represents the number of elements in the array.

Approach 3: Using Priority Queue (Min Heap)

In Java, a binary heap is used to implement a priority queue. It takes O(log n) for every insertion and delete. We replicate sorted pairing by repeatedly polling the smallest element and deleting the subsequent one. The heap property guarantees efficient minimal retrieval without requiring complete sorting up front.

Example

import java.util.PriorityQueue;
public class Main {
    // Method to calculate the maximum sum of min elements in pairs
    public static int arrayPairSum(int[] nums) {
        // Create a Min Heap using PriorityQueue
        // By default, Java PriorityQueue works as a Min Heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // Insert all elements of the array into the heap
        for (int num : nums) {
            minHeap.add(num);
        }
        // Variable to store the final sum
        int sum = 0;
        // Remove elements from heap in pairs
        while (!minHeap.isEmpty()) {
            // Extract the smallest element from the heap
            int first = minHeap.poll();
            // Remove the next smallest element but do not use it
            // This simulates pairing (a,b) and selecting min(a,b)
            minHeap.poll();
            // Add the smaller element of the pair to the sum
            sum += first;
        }
        // Return the calculated sum
        return sum;
    }
    public static void main(String[] args) {
        int[] nums = {1, 4, 3, 2};
        // Call the method to calculate the result
        int result = arrayPairSum(nums);
        System.out.println(result);
    }
}

Compile and Run

Output:

Complexity Analysis

The time complexity of the above code is O(N log N) and the space complexity is O(N), where 'N' represents the number of elements in the array.

Approach 4: Manual Sorting (Bubble Sort)

Using Bubble Sort, the array is manually sorted in this method. If adjacent items are out of order, it pushes larger elements to the end by frequently switching them. The argument for choosing an even index is unchanged after sorting. Although it is ineffective for huge inputs, this approach illustrates the principles of algorithms.

Example

public class Main {
    // Method to calculate the maximum sum of minimum values in pairs
    public static int arrayPairSum(int[] nums) {
        // ----------- STEP 1: Sort the array using Bubble Sort -----------
        // Bubble sort repeatedly compares adjacent elements
        // and swaps them if they are in the wrong order
        for (int i = 0; i < nums.length - 1; i++) {
            // After every iteration, the largest element
            // moves to the end of the array
            for (int j = 0; j < nums.length - i - 1; j++) {
                // Compare adjacent elements
                if (nums[j] > nums[j + 1]) {
                    // Swap the elements
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        // ----------- STEP 2: Calculate the sum of elements at even indices -----------
        // After sorting, elements are paired as:
        // (nums[0], nums[1]), (nums[2], nums[3]), ...
        int sum = 0;
        // Traverse the array with step size 2
        for (int i = 0; i < nums.length; i += 2) {
            // Add the first element of each pair (minimum element)
            sum += nums[i];
        }
        // Return the final sum
        return sum;
    }
    public static void main(String[] args) {
        int[] nums = {1, 4, 3, 2};
        int result = arrayPairSum(nums);
        System.out.println(result);
    }
}

Compile and Run

Output:

Complexity Analysis

The time complexity of the above code is O(N²) (where k = 20001) and the space complexity is O(1), where 'N' represents the number of elements in the array.

Advantages of Array Partition

Simple Greedy Logic: The Array Partition problem follows a very simple greedy strategy. After sorting the array, selecting the elements at even indices directly gives the optimal solution, making the logic easy to understand and implement.
Efficient Implementation: The optimal solution can be implemented using sorting with a time complexity of O(n log n), which is efficient for most practical applications and large datasets.
Improves Algorithmic Thinking: This problem helps developers understand important concepts like greedy algorithms, array manipulation, and pairing strategies, which are commonly used in technical interviews and competitive programming.
Multiple Solution Approaches: The problem can be solved using different approaches such as sorting, counting sort, priority queue (heap), and brute-force methods. This allows programmers to practice various algorithmic techniques.
Handles Negative and Positive Numbers: The algorithm works correctly even when the array contains negative numbers, positive numbers, or a mixture of both.
Low Memory Requirement: The most common solution uses in-place sorting and requires only constant extra space, making it memory efficient.

Disadvantages of Array Partition

Required an Even-Length Array: The input array is assumed to have 2n elements in this case. The algorithm cannot create full pairs without changing the problem if there are odd numbers of elements.
Overhead in Sorting: The array must be sorted in order to find the best solution, which adds an O(n log n) time complexity. This could result in some computing cost for really big datasets.
Unsuitable for Data Streaming in Real Time: This method is less appropriate in situations where the data is continuously arriving (streaming data) because it is impractical to sort the complete array each time.
Restricted Useful Applications: Compared to other array problems, the problem has less clear real-world applications, despite being a great way to master algorithmic fundamentals.
Utilizing Memory in Different Methods: Certain strategies, such as heap-based or counting sort algorithms, could need more RAM, which might not always be the best option given the limitations.
Dependence on Constraints: The value range of the items has a significant impact on some optimized methods (like counting sort). These methods become ineffective when the range is quite large.

Conclusion

The Array Partition Problem is a simple yet powerful example of how greedy strategies and sorting techniques can be used to achieve an optimal solution efficiently. We can maximize the total sum of the pair minimums by sorting the items and choosing the minimum element in each pair.

The significance of comprehending array manipulation, pairing logic, and algorithm optimization methods including sorting, counting sort, and heap structures is illustrated by this problem. Because of its simplicity, effectiveness, and ease of Java implementation, the sorting-based greedy method continues to be the most practical and popular of all the approaches.

Overall, mastering this problem helps strengthen problem-solving skills and builds a strong foundation for tackling more complex array and greedy algorithm problems in coding interviews and real-world applications.

Next TopicAtomic vs volatile in java

← prev next →

We deliver comprehensive tutorials, interview question-answers, MCQs, study materials on leading programming languages and web technologies like Data Science, MEAN/MERN full stack development, Python, Java, C++, C, HTML, React, Angular, PHP and much more to support your learning and career growth.