LeetCode Problem 3627

Difficulty: 🟡 Medium
Topics: Array, Math, Greedy, Sorting, Game Theory

Solution

LeetCode 3627 - Maximum Median Sum of Subsequences of Size 3

Problem Understanding

We are given an array nums whose length is always divisible by 3.

The array must be emptied by repeatedly selecting exactly three elements. For each selected triple, we compute its median, add that median to our answer, and remove all three elements from the array. After repeating this process n / 3 times, every element will have been used exactly once.

The goal is to maximize the total sum of all medians obtained from the chosen triples.

For a sorted triple:

[a, b, c]

where:

a <= b <= c

the median is b, the middle element.

Therefore, every group contributes its second-largest element to the final answer.

The input size is very large:

• nums.length can be as large as 5 * 10^5
• Values can be as large as 10^9

These constraints immediately rule out any exponential or combinatorial search over possible groupings.

An important observation is that the median of a triple is the second-largest element. Since we want to maximize the sum of medians, we want as many large numbers as possible to serve as medians rather than being "wasted" as the largest element of a group or as the smallest filler element.

Some edge cases worth keeping in mind:

• All values are equal.
• The array contains only one triple.
• Very large values mixed with very small values.
• Many duplicates.
• Strictly increasing or strictly decreasing arrays.

The problem guarantees:

• The length is at least 1.
• The length is divisible by 3.
• Every element is positive.

These guarantees simplify implementation because we never need to handle incomplete groups.

Approaches

Brute Force

A brute-force solution would try every possible way to partition the array into groups of three.

For each partition:

1. Compute the median of every triple.
2. Sum the medians.
3. Keep the maximum result.

This approach is correct because it explicitly evaluates every possible grouping.

However, it is completely impractical. Even for relatively small arrays, the number of ways to partition elements into triples grows explosively. The complexity is super-exponential, making it unusable for n = 5 * 10^5.

Key Insight

Suppose the array is sorted:

a0 <= a1 <= a2 <= ... <= a(n-1)

Let:

k = n / 3

be the number of triples.

To maximize the sum of medians, we should maximize the values chosen as medians.

Each median requires:

• One element larger than or equal to it in its triple.
• One element smaller than or equal to it in its triple.

Think about constructing groups from the largest numbers.

For every median we choose, we must spend:

• One even larger element as the maximum of that group.
• One small element as filler.

Therefore, among the largest 2k elements, every other element becomes a median.

After sorting, the optimal medians are:

nums[n-2],
nums[n-4],
nums[n-6],
...

taking exactly k values.

Another way to see this:

• Use the largest element as a group's maximum.
• Use the second-largest element as that group's median.
• Repeat.
• The smallest remaining elements serve as fillers.

This arrangement allows the largest possible values to occupy median positions.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Enumerates all possible partitions into triples
Optimal	O(n log n)	O(1) extra, excluding sort	Sort and take every second element from the end

Algorithm Walkthrough

1. Let n be the length of the array and let k = n / 3, the number of triples that must be formed.
2. Sort the array in non-decreasing order.
3. Start from index n - 2.

This position corresponds to the second-largest value in the entire array. In an optimal grouping, this value can be used as a median while the largest value serves as the maximum of the same triple. 4. Add the value at index n - 2 to the answer. 5. Move two positions left to index n - 4.

The element at n - 3 is effectively consumed as the maximum of another group, so the next candidate median is two positions away. 6. Continue taking every second element from the end. 7. Stop after selecting exactly k medians. 8. Return the accumulated sum.

Why it works

After sorting, every median must have one larger element paired with it. Thus, for each median selected from the large end of the array, we must reserve one even larger element as the group's maximum. The smallest elements can always be used