Watch 10 video solutions for Minimum Subsequence in Non-Increasing Order, a easy level problem involving Array, Greedy, Sorting. This walkthrough by code Explainer has 809 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the array nums, obtain a subsequence of the array whose sum of elements is strictly greater than the sum of the non included elements in such subsequence.
If there are multiple solutions, return the subsequence with minimum size and if there still exist multiple solutions, return the subsequence with the maximum total sum of all its elements. A subsequence of an array can be obtained by erasing some (possibly zero) elements from the array.
Note that the solution with the given constraints is guaranteed to be unique. Also return the answer sorted in non-increasing order.
Example 1:
Input: nums = [4,3,10,9,8] Output: [10,9] Explanation: The subsequences [10,9] and [10,8] are minimal such that the sum of their elements is strictly greater than the sum of elements not included. However, the subsequence [10,9] has the maximum total sum of its elements.
Example 2:
Input: nums = [4,4,7,6,7] Output: [7,7,6] Explanation: The subsequence [7,7] has the sum of its elements equal to 14 which is not strictly greater than the sum of elements not included (14 = 4 + 4 + 6). Therefore, the subsequence [7,6,7] is the minimal satisfying the conditions. Note the subsequence has to be returned in non-increasing order.
Constraints:
1 <= nums.length <= 5001 <= nums[i] <= 100Problem Overview: Given an integer array, return the smallest subsequence such that the sum of its elements is strictly greater than the sum of the remaining elements. The result must be returned in non-increasing order. If multiple answers exist, choose the one with the largest total sum.
Approach 1: Greedy Approach Using Sorting (Time: O(n log n), Space: O(1) or O(n) depending on sort)
This problem naturally fits a greedy strategy. Larger numbers contribute more to the subsequence sum, so selecting the largest elements first minimizes how many elements you need. Start by sorting the array in descending order using a standard sorting algorithm. Compute the total sum of the array, then iterate through the sorted numbers while accumulating a running subsequence sum. Stop as soon as the subsequence sum becomes strictly greater than the remaining sum (totalSum - currentSum). Because elements are taken from largest to smallest, the resulting subsequence automatically satisfies the non-increasing order requirement.
This method is straightforward to implement and works well for typical constraints. The only expensive operation is sorting, which takes O(n log n) time. The greedy choice is optimal because selecting smaller elements earlier would require more elements to surpass the remaining sum.
Approach 2: Bucket Sort Optimization (Time: O(n + k), Space: O(k))
If the value range is small (as in the original constraints where values are between 1 and 100), sorting can be optimized using bucket counting. Create a frequency array where the index represents the number and the value represents how many times it appears. Then iterate from the largest possible value down to the smallest, greedily adding numbers to the subsequence while updating the running sum.
This avoids comparison-based sorting entirely. Building the frequency array takes O(n), and iterating over the value range takes O(k), where k is the maximum possible value. This approach leverages counting techniques commonly used with arrays and works well when the value range is limited.
Recommended for interviews: The greedy solution with sorting is what most interviewers expect. It demonstrates understanding of greedy algorithms and problem simplification. Mentioning the bucket sort optimization shows deeper awareness of constraints and how to reduce O(n log n) sorting to near linear time when the value range is small.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) to O(n) | General case. Simple and reliable for any value range. |
| Bucket Sort Greedy | O(n + k) | O(k) | When element values fall within a small fixed range (e.g., 1–100). |