We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Subsequence in Non-Increasing Order

Number: 1519

Difficulty: Easy

Paid? No

Companies: Amazon, Mercari

Problem Description

Given an array nums, obtain a subsequence of the array such that the sum of its elements is strictly greater than the sum of the remaining elements. The chosen subsequence should have the minimum possible size; if there are multiple solutions with minimal size, return the one with the maximum total sum. The final subsequence must be returned in non-increasing order.

Key Insights

  • Sorting the array in descending order helps in greedily choosing the largest elements first.
  • Greedily adding the largest elements ensures that we minimize the number of elements needed and maximize the subsequence sum.
  • Keep track of the running sum of chosen elements and the remaining total to check when the subsequence sum becomes strictly greater.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing the sorted array and the resulting subsequence.

Solution

The approach involves:

  1. Sorting the input array in non-increasing order.
  2. Iterating through the sorted array and accumulating the sum of selected elements.
  3. After each selection, subtract the element’s value from the total remaining sum and check if the current subsequence sum exceeds it.
  4. Once the condition is met, the chosen elements form the required subsequence.

This greedy approach ensures the solution is minimal in size and, among minimal choices, has the maximum sum.

Code Solutions

# Python solution for "Minimum Subsequence in Non-Increasing Order"

def minSubsequence(nums):
    # Sort the array in descending order
    sorted_nums = sorted(nums, reverse=True)
    
    # Calculate the total sum of the array
    total_sum = sum(nums)
    
    subsequence = []
    subsequence_sum = 0
    
    # Iterate over sorted list and add numbers to subsequence until condition is met
    for num in sorted_nums:
        subsequence.append(num)
        subsequence_sum += num
        total_sum -= num  # update the sum of remaining elements
        if subsequence_sum > total_sum:
            break
    return subsequence

# Example usage:
print(minSubsequence([4, 3, 10, 9, 8]))  # Expected output: [10,9]
← Back to All Questions