Minimum Subsequence in Non-Increasing Order

You are given an array nums. Return the subsequence of minimum length such that the sum of the subsequence is strictly greater than the sum of the remaining elements. If there are multiple solutions, return the one with the fewest elements. The result should be sorted in non-increasing order.

This is LeetCode 1403: Minimum Subsequence in Non-Increasing Order, an easy problem that teaches a clean greedy pattern. The core idea is that taking the largest elements first always minimizes the number of elements you need.

Why this problem matters

This problem is a clean introduction to the "greedy selection after sorting" pattern. You sort the array, then greedily pick elements in a specific order until a condition is met. The same skeleton appears in problems like Assign Cookies, where you sort both arrays and greedily match, and in partition problems where you need to split elements based on cumulative sums.

The key lesson here is recognizing when sorting transforms a problem from "which elements should I pick?" into "how many elements do I need from the front?" That shift from selection to counting is what makes the greedy approach work.

The brute force approach

A brute force solution would enumerate all possible subsequences, compute the sum of each, and check whether it exceeds the sum of the remaining elements. For each valid subsequence, you would track the one with the minimum size. With n elements, there are 2^n possible subsequences, making this approach O(2^n) in time.

def min_subsequence_brute(nums):
    from itertools import combinations
    total = sum(nums)
    best = None
    for size in range(1, len(nums) + 1):
        for combo in combinations(nums, size):
            s = sum(combo)
            if s > total - s:
                candidate = sorted(combo, reverse=True)
                if best is None or len(candidate) < len(best):
                    best = candidate
        if best is not None:
            break
    return best

This works but is far too slow for any reasonable input size. We need a way to avoid checking every combination.

The key insight: sort and take greedily

If you sort the array in descending order, the optimal subsequence is always a prefix of the sorted array. Why? Because taking the largest elements first maximizes the sum you accumulate per element. No other selection of the same size can produce a larger sum.

So the algorithm is:

1. Sort nums in descending order.
2. Compute the total sum.
3. Walk through the sorted array, accumulating a running sum.
4. Stop as soon as the running sum exceeds the remaining sum (total minus running sum).
5. Return the elements you have taken so far.

Walking through it step by step

Let's trace through nums = [4, 3, 10, 9, 8]. The total sum is 34.

We only needed two elements. If we had taken smaller elements first (say 3 and 4), their sum of 7 would not exceed the remaining 27, and we would need more elements. Sorting descending and taking greedily guarantees the minimum count.

The greedy solution

def min_subsequence(nums):
    nums.sort(reverse=True)
    total = sum(nums)
    result = []
    current = 0
    for num in nums:
        current += num
        result.append(num)
        if current > total - current:
            break
    return result

Here is what each piece does:

1. nums.sort(reverse=True) puts the largest elements first so we can take them greedily from the front.
2. total = sum(nums) computes the full array sum. We need this to compare our taken sum against the remaining sum.
3. As we iterate, current tracks the sum of elements we have taken so far. The remaining sum is total - current.
4. The condition current > total - current checks whether the taken sum strictly exceeds the remaining sum. As soon as it does, we stop.
5. The result is already in non-increasing order because we iterate through a descending-sorted array.

Complexity analysis

The sort is the bottleneck. The single pass through the sorted array is O(n). Since we must sort to enable the greedy strategy, O(n log n) is optimal for this approach.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Sort then greedily select

The pattern of sorting the input to create a predictable order, then walking through it with a simple rule:

items.sort(key=some_criteria)
collected = []
for item in items:
    collected.append(item)
    if goal_reached(collected):
        break

In Minimum Subsequence, you sort descending and stop when the partial sum exceeds the remainder. In Assign Cookies, you sort both arrays and greedily match. In problems like Task Scheduler, sorting by frequency determines the greedy order. The skeleton is the same: sort to create the right order, then walk forward and stop early.

2. Running sum with threshold

The pattern of maintaining a cumulative sum and stopping when it crosses a boundary:

running = 0
for value in sequence:
    running += value
    if running > threshold:
        return result

In Minimum Subsequence, the threshold is half the total sum. In problems like Minimum Size Subarray Sum, the threshold is a target value. In prefix sum problems, the running sum enables range queries. The idea is always the same: accumulate and compare.

Edge cases

Before submitting, make sure your solution handles these:

• Single element [1]: the only subsequence is [1], which has sum 1. The remaining sum is 0. Since 1 > 0, return [1].
• All elements equal [5, 5, 5, 5]: total is 20. You need to take elements until the taken sum exceeds 10. Taking three 5s gives sum 15 > 5. Return [5, 5, 5].
• Already sorted descending [10, 5, 3, 1]: the sort is a no-op. Take 10, current = 10, remaining = 9. 10 > 9, so return [10].
• Two elements [1, 2]: sorted gives [2, 1]. Take 2, remaining = 1. 2 > 1, return [2].
• Need all elements [1, 1, 1, 1, 1]: total is 5. Taking four gives 4 vs 1, which works. Return [1, 1, 1, 1].

The greedy solution handles all of these without special-case logic.

Common mistakes

1. Forgetting to sort descending. If you iterate through the unsorted array, you might take small elements first and need more elements than necessary. The result would still be valid (sum exceeds remainder) but would not be the minimum length subsequence.

2. Using >= instead of >. The problem requires the sum to be strictly greater than the remaining sum. Using >= would stop too early when the sums are equal, producing an incorrect result.

3. Sorting ascending instead of descending. If you sort ascending and take from the end, you need to be careful about building the result in the right order. Sorting descending and appending naturally produces the non-increasing result.

4. Not returning the result in non-increasing order. The problem explicitly requires the output to be sorted in non-increasing order. Since we iterate through a descending-sorted array, this comes for free.

From understanding to recall

You have read the greedy solution and it makes sense. Sort descending, accumulate, stop when the sum exceeds the remainder. Clean. But can you write it from scratch in an interview without looking at it?

The details matter: remembering to use strict inequality (>), knowing that total - current gives the remaining sum, and recognizing that the sorted order gives you the result format for free. These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the sort-then-greedily-select loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "find minimum elements whose sum exceeds a threshold" and the code flows out without hesitation.

The greedy selection pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Assign Cookies - Another greedy problem where sorting both inputs enables a simple matching strategy
• Sort Colors - Sorting-based problem that uses a different technique (Dutch National Flag) but shares the idea of putting elements in the right order
• Majority Element - A different approach to finding dominant elements in an array, using Boyer-Moore voting

CodeBricks breaks the minimum subsequence problem into its sort-then-greedily-select and running sum building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy selection question shows up in your interview, you do not think about it. You just write it.