LeetCode 1403 - Minimum Subsequence in Non-Increasing Order

The problem gives an integer array nums and asks us to build a subsequence whose sum is strictly greater than the sum of

leetcodeeasyarraygreedysorting

LeetCode Problem 1403

Difficulty: 🟢 Easy
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem gives an integer array nums and asks us to build a subsequence whose sum is strictly greater than the sum of all elements that are not included in the subsequence.

A subsequence means we are allowed to remove elements from the array while preserving the remaining elements. However, the final answer must be returned in non-increasing order, so we are effectively free to sort the selected values before returning them.

The problem introduces two optimization requirements:

  1. The subsequence must have the minimum possible size.
  2. If multiple subsequences have the same minimum size, we must choose the one with the maximum total sum.

The input size is relatively small:

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 100

These constraints tell us several important things:

  • The array is small enough that sorting is completely acceptable.
  • Values are positive integers only, which is extremely important.
  • Because all numbers are positive, taking larger numbers first always increases the subsequence sum as quickly as possible.
  • The problem guarantees that the final answer is unique.

The core condition can be rewritten mathematically.

If:

  • selected_sum is the sum of the chosen subsequence
  • total_sum is the sum of the entire array

then the requirement becomes:

selected_sum > total_sum - selected_sum

which simplifies to:

2 * selected_sum > total_sum

So our goal is to pick as few numbers as possible so that their sum exceeds half of the total array sum.

Several edge cases are important:

  • Arrays with only one element, where that element alone automatically satisfies the condition.
  • Arrays where multiple large elements are equal.
  • Arrays where the subsequence sum becomes exactly equal to the remaining sum, which is not sufficient because the condition is strictly greater.
  • Arrays already sorted in increasing or decreasing order.
  • Arrays where many small numbers require selecting several elements before crossing half the total sum.

Approaches

Brute Force Approach

A brute force solution would generate every possible subsequence of the array and test whether it satisfies the required condition.

For each subsequence:

  1. Compute the sum of selected elements.
  2. Compute the sum of unselected elements.
  3. Check whether the selected sum is strictly greater.
  4. Among all valid subsequences, choose:
  • the one with minimum size
  • then the one with maximum sum if sizes tie

This approach is correct because it exhaustively examines every possible subsequence, guaranteeing that the optimal answer will eventually be found.

However, the number of subsequences of an array with n elements is:

2^n

With n = 500, this becomes astronomically large and completely infeasible.

Optimal Greedy Approach

The key observation is that all numbers are positive.

If we want the subsequence to exceed half of the total sum while using the fewest elements possible, we should always choose the largest available numbers first.

Why does this work?

  • Larger numbers increase the subsequence sum faster.
  • Using larger values minimizes how many elements we need.
  • If two subsequences have the same size, choosing larger numbers naturally produces the larger total sum.

This leads to a simple greedy strategy:

  1. Sort the array in descending order.
  2. Keep taking numbers from largest to smallest.
  3. Stop as soon as the selected sum becomes strictly greater than the remaining sum.

Because the numbers are processed from largest to smallest, the resulting subsequence is automatically in non-increasing order.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Generates and checks all subsequences
Optimal O(n log n) O(n) Sort descending and greedily select largest values

Algorithm Walkthrough

  1. Compute the total sum of the array.

We need this to compare the subsequence sum against the remaining elements. Since the remaining sum equals total_sum - selected_sum, knowing the total allows constant-time comparisons. 2. Sort the array in descending order.

The greedy insight is that larger numbers help us reach the target condition faster. Sorting descending ensures we always consider the largest available element first. 3. Initialize:

  • current_sum = 0
  • an empty result list

current_sum tracks the sum of the chosen subsequence. 4. Iterate through the sorted array.

For each number:

  • add it to the result
  • add its value to current_sum
  1. After each addition, check whether:
current_sum > total_sum - current_sum

If true, we have found a valid subsequence. 6. Immediately return the result.

Because we processed numbers from largest to smallest:

  • we used the fewest possible elements
  • among equal-sized solutions, we achieved the maximum possible sum

Why it works

The greedy strategy is optimal because every number is positive. Choosing a larger number always contributes more toward exceeding half the total sum than choosing a smaller number.

Suppose there were a better solution using fewer elements than the greedy approach. That would mean smaller numbers somehow achieved the target faster than larger numbers, which is impossible with strictly positive values.

Additionally, if two solutions use the same number of elements, taking the largest available numbers guarantees the maximum subsequence sum.

Therefore, sorting descending and greedily selecting elements produces the unique optimal answer.

Python Solution

from typing import List

class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        total_sum = sum(nums)

        nums.sort(reverse=True)

        result = []
        current_sum = 0

        for num in nums:
            result.append(num)
            current_sum += num

            if current_sum > total_sum - current_sum:
                return result

        return result

The implementation begins by computing the total array sum. This allows us to determine the remaining sum at any moment without repeatedly recalculating it.

Next, the array is sorted in descending order. This is the core greedy step because we want to take the largest numbers first.

The result list stores the chosen subsequence, while current_sum tracks the sum of selected elements.

During iteration, each number is added to both the subsequence and the running sum. After every addition, we check whether the selected sum is strictly greater than the remaining sum.

The moment the condition becomes true, we immediately return the result because:

  • we have used the fewest elements possible
  • the chosen elements are the largest available ones
  • the subsequence is already in non-increasing order

The final return result is technically unnecessary under the problem guarantees, but including it makes the function complete and safe.

Go Solution

package main

import "sort"

func minSubsequence(nums []int) []int {
	totalSum := 0

	for _, num := range nums {
		totalSum += num
	}

	sort.Slice(nums, func(i, j int) bool {
		return nums[i] > nums[j]
	})

	result := []int{}
	currentSum := 0

	for _, num := range nums {
		result = append(result, num)
		currentSum += num

		if currentSum > totalSum-currentSum {
			return result
		}
	}

	return result
}

The Go implementation follows exactly the same greedy strategy as the Python version.

The main difference is sorting syntax. Go uses sort.Slice with a custom comparator function to sort the array in descending order.

The result subsequence is stored in a slice. As numbers are appended, the running sum is updated and checked against the remaining sum.

Integer overflow is not a concern because the constraints are very small. The maximum possible total sum is:

500 * 100 = 50000

which easily fits inside Go's int type.

Worked Examples

Example 1

Input:

nums = [4,3,10,9,8]

First compute the total sum:

total_sum = 34

Sort descending:

[10,9,8,4,3]

Now iterate greedily.

Step Picked Number Result Current Sum Remaining Sum Condition
1 10 [10] 10 24 10 > 24, false
2 9 [10,9] 19 15 19 > 15, true

We stop immediately.

Final answer:

[10,9]

Example 2

Input:

nums = [4,4,7,6,7]

Compute total sum:

total_sum = 28

Sort descending:

[7,7,6,4,4]

Iterate greedily.

Step Picked Number Result Current Sum Remaining Sum Condition
1 7 [7] 7 21 7 > 21, false
2 7 [7,7] 14 14 14 > 14, false
3 6 [7,7,6] 20 8 20 > 8, true

We stop after selecting three numbers.

Final answer:

[7,7,6]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(n) Result list may store all elements

The sorting operation is the most expensive part of the algorithm, requiring O(n log n) time.

The iteration afterward is linear, so it does not change the overall complexity.

The extra space comes primarily from the output subsequence. In the worst case, all elements may need to be included.

Test Cases

from typing import List

class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        total_sum = sum(nums)

        nums.sort(reverse=True)

        result = []
        current_sum = 0

        for num in nums:
            result.append(num)
            current_sum += num

            if current_sum > total_sum - current_sum:
                return result

        return result

solution = Solution()

assert solution.minSubsequence([4, 3, 10, 9, 8]) == [10, 9]  # Example 1
assert solution.minSubsequence([4, 4, 7, 6, 7]) == [7, 7, 6]  # Example 2

assert solution.minSubsequence([1]) == [1]  # Single element array

assert solution.minSubsequence([2, 1]) == [2]  # Largest element alone works

assert solution.minSubsequence([1, 1, 1, 1]) == [1, 1, 1]  # Need more than half

assert solution.minSubsequence([5, 5, 5, 5]) == [5, 5, 5]  # Equality is not enough

assert solution.minSubsequence([10, 1, 1, 1]) == [10]  # One dominant element

assert solution.minSubsequence([6, 6, 6, 6, 6]) == [6, 6, 6]  # Multiple equal values

assert solution.minSubsequence([9, 8, 7, 6]) == [9, 8]  # Already descending

assert solution.minSubsequence([1, 2, 3, 4, 5]) == [5, 4]  # Increasing order input

assert solution.minSubsequence([100] * 500) == [100] * 251  # Maximum size stress test
Test Why
[4,3,10,9,8] Validates the first provided example
[4,4,7,6,7] Validates strict inequality handling
[1] Smallest possible input
[2,1] Largest element alone satisfies condition
[1,1,1,1] Requires selecting multiple small values
[5,5,5,5] Ensures equality does not count
[10,1,1,1] Tests dominant large value
[6,6,6,6,6] Handles repeated equal values
[9,8,7,6] Input already sorted descending
[1,2,3,4,5] Input sorted ascending
[100] * 500 Stress test with maximum constraints

Edge Cases

One important edge case occurs when the array contains only a single element. Since all numbers are positive, that single element is automatically greater than the sum of the remaining elements, which is zero. The implementation handles this naturally because the first iteration immediately satisfies the condition.

Another subtle case is when the selected sum becomes exactly equal to the remaining sum. The problem requires the selected sum to be strictly greater, not greater than or equal. For example, in [4,4,7,6,7], selecting [7,7] produces sums of 14 and 14, which is invalid. The implementation correctly uses the > operator instead of >=.

A third important case involves many identical values. For arrays like [5,5,5,5], selecting two elements gives 10 versus 10, which still fails the condition. The algorithm continues selecting values until the inequality becomes strictly true, ensuring correctness even when many values are equal.

Another edge case appears when one value dominates the entire array, such as [10,1,1,1]. In this situation, the optimal subsequence contains only one element. Because the algorithm processes numbers in descending order, it immediately identifies this minimal solution.

Finally, arrays already sorted in ascending or descending order should still work correctly. Since the algorithm explicitly sorts the array before processing, the original ordering does not affect correctness.