LeetCode 1403: Minimum Subsequence in Non-Increasing Order Solution

Master LeetCode problem 1403 (Minimum Subsequence in Non-Increasing Order), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1403. Minimum Subsequence in Non-Increasing Order

Easy

Array Greedy Sorting

Problem Explanation

Explanation

To solve this problem, we need to find a subsequence of the array nums such that the sum of elements in the subsequence is strictly greater than the sum of elements not included in the subsequence. We also need to return the subsequence with the minimum size and maximum total sum of its elements.

The steps to solve this problem are as follows:

Sort the array nums in non-increasing order.
Calculate the total sum of all elements in nums.
Start iterating from the largest elements in the sorted array. At each step, add the current element to the sum of the subsequence and subtract it from the total sum.
Check if the sum of the subsequence is greater than the remaining total sum. If true, return the subsequence.

Solution Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> minSubsequence(int[] nums) {
        Arrays.sort(nums);
        int totalSum = Arrays.stream(nums).sum();
        int sum = 0;
        List<Integer> result = new ArrayList<>();
        
        for (int i = nums.length - 1; i >= 0; i--) {
            sum += nums[i];
            totalSum -= nums[i];
            result.add(nums[i]);
            
            if (sum > totalSum) {
                break;
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1403 (Minimum Subsequence in Non-Increasing Order)?

This page provides optimized solutions for LeetCode problem 1403 (Minimum Subsequence in Non-Increasing Order) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1403 (Minimum Subsequence in Non-Increasing Order)?

The time complexity for LeetCode 1403 (Minimum Subsequence in Non-Increasing Order) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1403 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1403 in Java, C++, or Python.

Back to LeetCode Solutions