Minimum Subsequence in Non-Increasing Order

Easy
493.

Minimum Subsequence in Non-Increasing Order

Minimum Subsequence in Non-Increasing Order is an easy coding problem on arrays, sorting and greedy, asked in Amazon interviews.

Given an array of positive integers nums, pick a subsequence whose sum is strictly greater than the sum of the elements you leave behind.

Among all such subsequences choose the one with the fewest elements; if several tie, choose the one with the largest sum. The answer is unique — return it sorted in non-increasing order.

Example 1

Input
nums = [4,3,10,9,8]
Output
[10,9]
Explanation
10 + 9 = 19 beats 4 + 3 + 8 = 15, and no single element can.

Example 2

Input
nums = [4,4,7,6,7]
Output
[7,7,6]
Explanation
20 > 8. Two elements would give at most 14, which does not beat 14.

Example 3

Input
nums = [6]
Output
[6]

Constraints

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var minSubsequence = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Subsequence in Non-Increasing Order — Solution

Minimum Subsequence in Non-Increasing Order solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Subsequence in Non-Increasing Order is an easy coding problem on arrays, sorting and greedy, asked in Amazon interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting, Greedy
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array of positive integers nums, pick a subsequence whose sum is strictly greater than the sum of the elements you leave behind.

Among all such subsequences choose the one with the fewest elements; if several tie, choose the one with the largest sum. The answer is unique — return it sorted in non-increasing order.

Example 1

Input: nums = [4,3,10,9,8]
Output: [10,9]
Explanation: 10 + 9 = 19 beats 4 + 3 + 8 = 15, and no single element can.

Example 2

Input: nums = [4,4,7,6,7]
Output: [7,7,6]
Explanation: 20 > 8. Two elements would give at most 14, which does not beat 14.

Example 3

Input: nums = [6]
Output: [6]

Constraints

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

Hints for Minimum Subsequence in Non-Increasing Order

  1. Hint 1

    To use as few elements as possible while making the sum as large as possible, take the biggest values first.

  2. Hint 2

    Sort descending, then keep adding until the running sum overtakes the remainder.

  3. Hint 3

    The remainder is total - running, so the stop condition is running > total - running.

How to solve Minimum Subsequence in Non-Increasing Order

Sorting descending and taking a greedy prefix is optimal on both criteria at once: for any fixed count, the largest-k prefix has the maximum possible sum, so it is the first count at which the condition can be met.

Approach

  1. Sort a copy of nums in non-increasing order and compute total.
  2. Walk the sorted values, appending each to the answer and accumulating acc.
  3. Stop the moment acc > total - acc.
  4. The collected prefix is already non-increasing, so return it as is.

Why it works

If a subsequence of size k satisfies the condition, so does the top-k prefix, because its sum is at least as large. Hence the smallest feasible k is found by the greedy scan, and at that k the top-k prefix is the maximum-sum choice — exactly the tie-break the problem asks for.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • The comparison must be strict — equal halves do not qualify, as [4,4,7,6,7] shows.
  • Sorting ascending and taking from the end works but you must reverse the result.
  • Returning the answer in the array's original order fails the exact judge.

Reference solution

Python

from typing import List

def minSubsequence(nums: List[int]) -> List[int]:
    s = sorted(nums, reverse=True)
    total = sum(s)
    out = []
    acc = 0
    for x in s:
        out.append(x)
        acc += x
        if acc > total - acc:
            break
    return out

Java

public static int[] minSubsequence(int[] nums) {
    int[] s = nums.clone();
    Arrays.sort(s);
    int n = s.length;
    int[] desc = new int[n];
    for (int i = 0; i < n; i++) desc[i] = s[n - 1 - i];
    long total = 0;
    for (int x : desc) total += x;
    long acc = 0;
    int take = 0;
    for (int i = 0; i < n; i++) {
        acc += desc[i];
        take++;
        if (acc > total - acc) break;
    }
    int[] out = new int[take];
    for (int i = 0; i < take; i++) out[i] = desc[i];
    return out;
}

C++

vector<int> minSubsequence(vector<int>& nums) {
    vector<int> s = nums;
    sort(s.begin(), s.end(), greater<int>());
    long long total = 0;
    for (int x : s) total += x;
    vector<int> out;
    long long acc = 0;
    for (int x : s) {
        out.push_back(x);
        acc += x;
        if (acc > total - acc) break;
    }
    return out;
}

JavaScript

var minSubsequence = function(nums) {
    const s = nums.slice().sort(function(a, b) { return b - a; });
    let total = 0;
    for (let i = 0; i < s.length; i++) total += s[i];
    const out = [];
    let acc = 0;
    for (let i = 0; i < s.length; i++) {
        out.push(s[i]);
        acc += s[i];
        if (acc > total - acc) break;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms