Watch 10 video solutions for Maximum Median Sum of Subsequences of Size 3, a medium level problem involving Array, Math, Greedy. This walkthrough by Developer Coder has 537 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums with a length divisible by 3.
You want to make the array empty in steps. In each step, you can select any three elements from the array, compute their median, and remove the selected elements from the array.
The median of an odd-length sequence is defined as the middle element of the sequence when it is sorted in non-decreasing order.
Return the maximum possible sum of the medians computed from the selected elements.
Example 1:
Input: nums = [2,1,3,2,1,3]
Output: 5
Explanation:
nums becomes [2, 1, 2].nums becomes empty.Hence, the sum of the medians is 3 + 2 = 5.
Example 2:
Input: nums = [1,1,10,10,10,10]
Output: 20
Explanation:
nums becomes [1, 10, 10].nums becomes empty.Hence, the sum of the medians is 10 + 10 = 20.
Constraints:
1 <= nums.length <= 5 * 105nums.length % 3 == 01 <= nums[i] <= 109Problem Overview: You are given an array and must form subsequences of size 3. The median of each subsequence contributes to the score. The goal is to arrange elements so the total sum of all medians is maximized.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
Generate every possible combination of three elements and compute its median. If the problem allows selecting multiple disjoint subsequences, you would need additional bookkeeping to avoid reusing elements. This approach relies on nested loops or combination generation over the array. While straightforward, the O(n^3) time complexity becomes infeasible even for moderate input sizes. The only benefit is conceptual clarity: it directly shows how the median contributes to the objective.
Approach 2: Greedy + Sorting (O(n log n) time, O(1) space)
The key observation is that the median of a triple becomes large when both the median and the maximum element are large. Sort the array using a standard sorting algorithm. After sorting, use two pointers: one at the start and one at the end. For each subsequence, pick the largest element as the maximum, the next largest element as the median, and pair them with the smallest remaining element as the minimum. Add the median to the result.
This greedy construction works because the smallest element in the triple does not influence the median value. Assigning the smallest numbers as the "minimum" preserves larger numbers for future medians. Each step consumes three elements: nums[right] (max), nums[right-1] (median), and nums[left] (min). Move right left by two and left right by one until all triples are formed.
The greedy decision is locally optimal and globally optimal because any attempt to use a smaller value as the median would reduce the total sum. Sorting ensures the largest candidates are always available for median positions. This pattern frequently appears in greedy interview problems where roles inside groups (min/median/max) affect the score differently.
Recommended for interviews: Start by explaining the brute force idea to show you understand the definition of the median and the grouping constraint. Then pivot quickly to the greedy + sorting strategy. Interviewers typically expect the O(n log n) solution because it demonstrates pattern recognition and the ability to reason about how ordering impacts medians.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(1) | Useful for understanding how medians are computed in triples or for very small inputs |
| Greedy + Sorting | O(n log n) | O(1) | Optimal approach for large arrays; sorting enables selecting the best possible medians |