Minimum Subsequence in Non-Increasing Order

Difficulty: Easy | Acceptance: 73.70% | Paid: No Topics: Array, Greedy, Sorting

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 is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

• Examples
• Constraints
• Greedy Sorting
• Counting Sort

Examples

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 <= 500
1 <= nums[i] <= 100

Greedy Sorting

Intuition To minimize the size of the subsequence while ensuring its sum is strictly greater than the sum of the remaining elements, we should prioritize picking the largest numbers available. This greedy strategy ensures that we reach the required sum threshold with the fewest number of elements.

Steps

• Calculate the total sum of all elements in the array.
• Sort the array in non-increasing (descending) order.
• Iterate through the sorted array, accumulating the sum of the selected elements into a running total.
• Add each element to the result list.
• Stop the iteration as soon as the running total of the selected elements is strictly greater than the sum of the remaining elements (total sum - running total).
• Return the result list.

class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        nums.sort(reverse=True)
        total_sum = sum(nums)
        sub_sum = 0
        res = []
        for num in nums:
            sub_sum += num
            res.append(num)
            if sub_sum > total_sum - sub_sum:
                break
        return res

Complexity

• Time: O(N log N) due to the sorting step, where N is the number of elements in the array.
• Space: O(1) or O(N) depending on the sorting algorithm’s implementation (e.g., heapsort uses O(1), quicksort uses O(log N), Timsort uses O(N)). The result list uses O(N) space in the worst case.
• Notes: This is the most standard and intuitive approach for this problem.

Counting Sort

Intuition Since the problem constraints specify that nums[i] is between 1 and 100, we can optimize the sorting step using Counting Sort. Instead of comparing elements, we can count the frequency of each number and iterate from the largest number down to the smallest. This reduces the time complexity from O(N log N) to O(N).

Steps

• Initialize a frequency array (or bucket) of size 101 (indices 0 to 100) with zeros.
• Iterate through the input array to populate the frequency array and calculate the total sum of all elements.
• Initialize an empty result list and a variable sub_sum to 0.
• Iterate from the largest possible value (100) down to 1.
• For each value, if its frequency is greater than 0, add that value to the result list and increment sub_sum by that value. Decrement the frequency.
• Repeat this process for the current value until its frequency is 0 or the condition sub_sum > total_sum - sub_sum is met.
• If the condition is met, return the result immediately.

class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        count = [0] * 101
        total_sum = 0
        for num in nums:
            count[num] += 1
            total_sum += num
        
        res = []
        sub_sum = 0
        for i in range(100, 0, -1):
            while count[i] > 0:
                res.append(i)
                sub_sum += i
                count[i] -= 1
                if sub_sum > total_sum - sub_sum:
                    return res
        return res

Complexity

• Time: O(N + K), where N is the length of the array and K is the range of values (100). Since K is constant, this is effectively O(N).
• Space: O(K) for the frequency array, which is constant space O(1) as K=101.
• Notes: This approach is more efficient than standard sorting when the range of input values is small and fixed.