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 <= 5001 <= nums[i] <= 100
Hints for Minimum Subsequence in Non-Increasing Order
Hint 1
To use as few elements as possible while making the sum as large as possible, take the biggest values first.
Hint 2
Sort descending, then keep adding until the running sum overtakes the remainder.
Hint 3
The remainder is
total - running, so the stop condition isrunning > 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
- Sort a copy of
numsin non-increasing order and computetotal. - Walk the sorted values, appending each to the answer and accumulating
acc. - Stop the moment
acc > total - acc. - 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 outJava
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