Skip to main content
Talentd

Maximum Median Sum of Subsequences of Size 3 - Solution & Explanation

MediumArrayMathGreedySorting6 min readAsked at: Amazon, IBM
Practice this problem

Problem Statement

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:

  • In the first step, select elements at indices 2, 4, and 5, which have a median 3. After removing these elements, nums becomes [2, 1, 2].
  • In the second step, select elements at indices 0, 1, and 2, which have a median 2. After removing these elements, 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:

  • In the first step, select elements at indices 0, 2, and 3, which have a median 10. After removing these elements, nums becomes [1, 10, 10].
  • In the second step, select elements at indices 0, 1, and 2, which have a median 10. After removing these elements, nums becomes empty.

Hence, the sum of the medians is 10 + 10 = 20.

 

Constraints:

  • 1 <= nums.length <= 5 * 105
  • nums.length % 3 == 0
  • 1 <= nums[i] <= 109

Approach Overview

Problem 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.

Solution

To maximize the sum of medians, we need to select larger elements as medians whenever possible. Since each operation can only select three elements, we can sort the array and then start from index n / 3, selecting every other element (skipping one) until the end of the array. This ensures that we select the largest possible medians.

The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n^3)O(1)Useful for understanding how medians are computed in triples or for very small inputs
Greedy + SortingO(n log n)O(1)Optimal approach for large arrays; sorting enables selecting the best possible medians

Video Solution

Maximum Median Sum of Subsequences of Size 3 | Weekly Contest 460 | Java Code | Developer Coder • Developer Coder • 543 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Median Sum of Subsequences of Size 3 easy or hard?
The problem is typically classified as Medium difficulty. The implementation is straightforward once you recognize the greedy insight that the median should come from the largest available values after sorting. The challenge is identifying why pairing large numbers with small ones preserves future medians.
Maximum Median Sum of Subsequences of Size 3 Python/Java solution
Implement the greedy strategy by sorting the array and using two pointers. After sorting, repeatedly add the second largest remaining element to the answer, then move the right pointer by two and the left pointer by one. The same logic translates directly to Python, Java, C++, Go, or TypeScript with O(n log n) complexity.
How to solve Maximum Median Sum of Subsequences of Size 3 in O(n)?
A pure O(n) solution is generally not feasible because ordering the elements is required to consistently choose the largest candidates for median positions. Sorting ensures the correct greedy grouping. Therefore the practical optimal complexity is O(n log n) using a sorting step followed by linear pointer traversal.
What is the best approach for Maximum Median Sum of Subsequences of Size 3?
The optimal solution uses a greedy strategy combined with sorting. Sort the array, then repeatedly form triples using the largest element as the maximum, the second largest as the median, and the smallest remaining element as the minimum. This maximizes each median contribution while preserving larger values for future groups. The approach runs in O(n log n) time and O(1) extra space.
Is Maximum Median Sum of Subsequences of Size 3 asked at Google/Amazon/Meta?
Greedy grouping and median‑based optimization problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants involving sorting and role assignment within groups (min, median, max) are common in array and greedy interview rounds.
What data structure is used in Maximum Median Sum of Subsequences of Size 3?
The solution primarily uses arrays along with sorting and a two‑pointer traversal technique. No complex data structures are required. The key idea is ordering the array and greedily assigning elements to the min, median, and max positions within each triple.
What is the time complexity of Maximum Median Sum of Subsequences of Size 3?
The optimal greedy solution runs in O(n log n) time due to the sorting step. After sorting, forming the triples and summing the medians takes O(n) time. Space complexity is O(1) if the sorting algorithm operates in place.

Ready to solve this problem?

Practice Maximum Median Sum of Subsequences of Size 3 with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays