Domain 1EasyCORE

Minimum Subsequence in Non-Increasing Order

The problem requires us to find a subsequence from the given array `nums` such that the sum of its elements is strictly greater than the sum of the remaining elements in the array. If there are multiple subsequences that satisfy this condition, we need to return the one with the minimum size. If there are still ties, we should return the subsequence with the maximum total sum. The final subsequence must be sorted in non-increasing order.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Greedy#Sort

1403. Minimum Subsequence in Non-Increasing Order

Model: qwen2.5-coder:14b
Topics: Greedy,Sort
FAANG asked: 0
Acceptance rate: 71.9%


Problem Breakdown

The problem requires us to find a subsequence from the given array nums such that the sum of its elements is strictly greater than the sum of the remaining elements in the array. If there are multiple subsequences that satisfy this condition, we need to return the one with the minimum size. If there are still ties, we should return the subsequence with the maximum total sum. The final subsequence must be sorted in non-increasing order.

Inputs:

  • An array of integers nums where each element is between 1 and 100 inclusive.
  • The length of nums is between 1 and 500 inclusive.

Outputs:

  • A subsequence of nums that meets the criteria above, sorted in non-increasing order.

Implicit Constraints or Tricky Edge Cases:

  • If the array has only one element, that element itself is the answer.
  • The solution is guaranteed to be unique, so we don’t need to handle multiple solutions.

Intuition

A brute-force approach would involve generating all possible subsequences and checking each one to see if it meets the criteria. However, this approach is computationally expensive with a time complexity of O(2^n), which is infeasible given the constraints (n <= 500).

The key insight is that we can achieve the desired subsequence by always picking the largest available element first. This greedy strategy ensures that we maximize the sum of the chosen elements quickly, thus minimizing the size of the subsequence.

Approach

  1. Sort the Array in Non-Increasing Order: By sorting the array in descending order, we ensure that we can pick the largest elements first.
  2. Initialize Variables:
    • total_sum to store the sum of all elements in the array.
    • subseq_sum to keep track of the sum of the chosen subsequence.
    • result list to store the elements of the subsequence.
  3. Iterate Through the Sorted Array: For each element, add it to subseq_sum and append it to result. If at any point subseq_sum becomes greater than half of total_sum, break out of the loop as we have found the minimal subsequence that meets the criteria.
  4. Return the Result: The result list will contain the elements of the subsequence in non-increasing order.

Complexity Analysis

  • Time Complexity: O(n log n) due to the sorting step, where n is the length of the array.
  • Space Complexity: O(n) for storing the sorted array and the result list.

Solution

def minSubsequence(nums):
    # Step 1: Sort the array in non-increasing order
    nums.sort(reverse=True)
    
    # Step 2: Initialize variables
    total_sum = sum(nums)
    subseq_sum = 0
    result = []
    
    # Step 3: Iterate through the sorted array
    for num in nums:
        subseq_sum += num
        result.append(num)
        if subseq_sum > total_sum / 2:
            break
    
    # Step 4: Return the result
    return result

# Example usage:
print(minSubsequence([4,3,10,9,8]))  # Output: [10, 9]
print(minSubsequence([4,4,7,6,7]))  # Output: [7, 7, 6]
print(minSubsequence([6]))          # Output: [6]

Edge Cases Handled

  • Single Element Array: If the array has only one element, it is returned as the result since it trivially satisfies the condition.
  • All Elements Equal: The greedy approach will correctly handle cases where all elements are equal by selecting the maximum number of elements needed to exceed half the total sum.