Minimum Subsequence in Non-Increasing Order - Solution & Explanation
Problem Statement
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] <= 100
Approach Overview
Problem 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 1: Greedy Approach Using Sorting
This approach involves sorting the original array in non-increasing order. After sorting, iterate over the sorted array while maintaining a running sum. Add elements to the subsequence until the sum of the subsequence becomes greater than the sum of the remaining elements. This greedy approach ensures that you include the largest elements first, thus achieving a minimal size subsequence with maximum sum.
The solution begins by sorting the array in descending order. Using a greedy algorithm, it accumulates a running total of the elements into a new subsequence array until this new subsequence's sum is greater than the remaining elements' sum. At each step, it checks and updates the total to break out of the loop at the correct time. The resulting subsequence array is returned.
Complexity
Time Complexity: O(n log n), where n is the number of elements in the array, due to sorting.
Space Complexity: O(n) for the storage of the result subsequence.
Approach 2: Alternative Approach Using Bucket Sort
This approach leverages the constraint that elements in the array are between 1 and 100. By using a frequency array (or bucket sort), we can count occurrences of each number. We iterate from the highest value downward, and construct a subsequence using the most frequent elements until the subsequence sum exceeds the sum of non-included elements. This reduces the time complexity associated with sorting large arrays.
The C implementation utilizes a fixed size bucket array (to hold counts from 1 to 100). As we populate the bucket, we simultaneously maintain a total. We then traverse the bucket in reverse, constructing our result subsequence from the largest possible numbers downwards, ensuring minimal subsequence length.
Complexity
Time Complexity: O(n + k), where k is the range of the number (100 here).
Space Complexity: O(n + k), due to storage of result and buckets.
Approach 3: Sorting
We can first sort the array nums in descending order, then add the elements to the array from largest to smallest. After each addition, we check whether the sum of the current elements is greater than the sum of the remaining elements. If it is, we return the current array.
The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array nums.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach Using Sorting | Time Complexity: O(n log n), where n is the number of elements in the array, due to sorting. |
| Alternative Approach Using Bucket Sort | Time Complexity: O(n + k), where k is the range of the number (100 here). |
| Sorting | — |
Detailed Complexity Analysis
| 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). |
Video Solution
1403. Minimum Subsequence in Non-Increasing Order || leetcode weekly-contest-183 || [C++ SOLUTION] • code Explainer • 814 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Subsequence in Non-Increasing Order easy or hard?
Minimum Subsequence in Non-Increasing Order Python/Java solution
How to solve Minimum Subsequence in Non-Increasing Order in O(n)?
What is the best approach for Minimum Subsequence in Non-Increasing Order?
Is Minimum Subsequence in Non-Increasing Order asked at Google/Amazon/Meta?
What data structure is used in Minimum Subsequence in Non-Increasing Order?
What is the time complexity of Minimum Subsequence in Non-Increasing Order?
Ready to solve this problem?
Practice Minimum Subsequence in Non-Increasing Order with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor