#1403

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Subsequence in Non-Increasing Order

Find the minimum subsequence in non-increasing order such that its sum exceeds the sum of non-included elements.

Problem Statement

Given an array of integers, find a subsequence whose sum is strictly greater than the sum of the elements not included in that subsequence. The subsequence should be as small as possible, and if there are multiple subsequences of equal size, choose the one with the maximum total sum of its elements. The result must be sorted in non-increasing order.

A subsequence of an array is formed by deleting some (or none) of its elements without changing the order of the remaining elements. This problem guarantees that there will be exactly one unique solution that satisfies the conditions.

Examples

Example 1

Input: nums = [4,3,10,9,8]

Output: [10,9]

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]

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

Solution Approach

Greedy Approach with Sorting

First, sort the array in non-increasing order. Then, iteratively pick elements from the sorted array, adding them to the subsequence, until the sum of the subsequence exceeds the sum of the remaining elements. This approach ensures that the subsequence is minimal and satisfies the sum condition.

Invariant Validation

At each step, maintain the sum of the selected subsequence and the sum of the remaining elements. Validate the condition by checking if the subsequence's sum is greater than the remaining elements. Once this condition is met, the subsequence is complete.

Optimality

This approach guarantees that the subsequence is minimal in size and has the maximum possible sum, as you are always choosing the largest available elements first. The sorting step ensures the elements are chosen in a non-increasing order, satisfying the problem's requirements.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is dominated by the sorting step, which is O(n log n), where n is the length of the array. The space complexity is O(n) due to the space needed for the sorted array and the subsequence.

What Interviewers Usually Probe

Did the candidate utilize sorting as part of their approach?
How well does the candidate handle greedy choice plus invariant validation?
Does the candidate explain the optimality of their solution in terms of both subsequence size and sum?

Common Pitfalls or Variants

Common pitfalls

Forgetting to sort the array in non-increasing order, which leads to incorrect subsequences.
Not maintaining the running sums of the subsequence and the remaining elements, which may result in an incorrect conclusion about when to stop.
Returning a subsequence that isn't sorted correctly in non-increasing order, which is a key requirement.

Follow-up variants

Consider the case where there are duplicate values in the array. Does the approach handle duplicates correctly?
What happens if there is only one element in the array? Ensure the solution works in edge cases.
Can this approach be modified for arrays with negative values or different constraints?

FAQ

What is the key pattern in the Minimum Subsequence in Non-Increasing Order problem?

The key pattern involves a greedy approach with sorting, where elements are selected from the largest to ensure the sum condition is met.

How do I ensure the subsequence is minimal and has the maximum sum?

By sorting the array in non-increasing order and greedily selecting the largest elements, you ensure the subsequence is minimal in size and has the maximum possible sum.

Can there be multiple valid subsequences in this problem?

Yes, but the problem guarantees a unique solution when considering subsequences that are minimal in size and sorted in non-increasing order.

What happens if the array contains duplicate elements?

The algorithm will still work correctly, as it selects the largest elements first, and duplicates can be part of the solution if they help meet the sum condition.

What is the time complexity of the solution?

The time complexity is O(n log n), dominated by the sorting step, where n is the length of the array.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        ans = []
        s, t = sum(nums), 0
        for x in sorted(nums, reverse=True):
            t += x
            ans.append(x)
            if t > s - t:
                break
        return ans

Continue Practicing

#1402 reducing dishes #1383 maximum performance of a team #1363 largest multiple of three