Minimum Subsequence in Non-Increasing Order

Minimum Subsequence in Non-Increasing Order - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: [10,9]

💡 Note: Total sum = 26. We need subsequence sum > remaining sum. Taking [10,9] gives sum=19 > remaining sum=7. This is minimum size (2) and already sorted in non-increasing order.

Example 2 — Single Element

$ Input: nums = [4,4,7,6,7]

› Output: [7,7,6]

💡 Note: Total sum = 28. Need sum > 14. Taking largest elements [7,7,6] gives sum=20 > remaining sum=8. This achieves the required condition with minimum size.

Example 3 — Edge Case

$ Input: nums = [6]

› Output: [6]

💡 Note: With only one element, we must take it. Sum=6 > remaining sum=0, so [6] is the answer.

Constraints

1 ≤ nums.length ≤ 500
1 ≤ nums[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with total sum calculation

Find Dominant Subsequence

Select minimum elements whose sum > remaining sum

Output

Return subsequence sorted in non-increasing order

Key Takeaway

🎯 Key Insight: Greedily pick the largest elements first to minimize subsequence size while maximizing sum

Asked in

a Amazon 15 M Microsoft 8

The key insight is to use a greedy approach: sort elements in descending order and pick the largest ones until the subsequence sum dominates. This naturally gives the minimum size solution with maximum sum. Best approach is Greedy with Sorting. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Sorting	O(n log n)	O(1)	Sort elements in descending order and greedily pick largest elements until sum dominates
Brute Force - Try All Subsequences	O(n × 2ⁿ)	O(n)	Generate all possible subsequences and find the valid one with minimum size and maximum sum

Greedy with Sorting — Algorithm Steps

Step 1: Sort the array in descending order
Step 2: Calculate total sum of all elements
Step 3: Greedily add largest elements until subsequence sum > remaining sum
Step 4: Return the subsequence (already sorted in non-increasing order)

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Descending

Arrange elements from largest to smallest

Greedy Selection

Add largest elements until sum dominates

Optimal Result

Minimum size subsequence in non-increasing order

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)b - *(int*)a); // Descending order
}

int* solution(int* nums, int numsSize, int* returnSize) {
    // Sort in descending order
    int* sortedNums = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        sortedNums[i] = nums[i];
    }
    qsort(sortedNums, numsSize, sizeof(int), compare);
    
    int totalSum = 0;
    for (int i = 0; i < numsSize; i++) {
        totalSum += nums[i];
    }
    
    int subsequenceSum = 0;
    int* result = (int*)malloc(numsSize * sizeof(int));
    *returnSize = 0;
    
    // Greedily pick largest elements
    for (int i = 0; i < numsSize; i++) {
        subsequenceSum += sortedNums[i];
        result[*returnSize] = sortedNums[i];
        (*returnSize)++;
        
        // Check if subsequence sum > remaining sum
        int remainingSum = totalSum - subsequenceSum;
        if (subsequenceSum > remainingSum) {
            break;
        }
    }
    
    free(sortedNums);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int numsSize = 0;
    char *token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), greedy selection takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using variables for sums and result array

✓ Linear Space

28.5K Views

Medium Frequency

~12 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Sorting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler