LeetCode Challenge #2 - Minimum Subsequence in Non-Increasing Order

Introduction

In this blog, we will look into solving one of the array problems in leetcode, namely the Minimum Subsequence in Non-Increasing Order problem.

Question

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.

Example :

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

Explanation: 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.

Constraints:

1 <= nums.length <= 500
1 <= nums[i] <= 100

Solution

We will now delve into one of the approaches to solving this problem. I'll be using Java language to code the solution.

Firstly we will need to Sort the given array "nums" in ascending order using the static method sort().

Arrays.sort(nums);

Next, we'll need an ArrayList, "result" to return the minimum subsequence, "sum" to store the array sum and a current array element variable, "currentSum". Now we can run a for loop to find the sum of all elements of given array "nums".

int sum=0;
int currentSum=0;
List<Integer> result=new ArrayList<Integer>();
for(int n:nums){
   sum+=n;
}

Now, we can create a loop where we iterate from the end of the array to the start. Here we first add the current element into the currentSum variable. Now we subtract the current loop element nums[i] from sum and store it into sum variable. Next, we'll add the current loop element to the result ArrayList.

for(int i=nums.length-1;i>=0;i--){
    result.add(nums[i]);
    sum=sum-nums[i];
    currentSum=currentSum+nums[i];

}

Here we put a condition where we check if the currentSum value is greater than the sum, then we return the result list.

for(int i=nums.length-1; i>=0; i--){
    result.add(nums[i]);
    sum-=nums[i];
    currentSum+=nums[i];
    if(currentSum>sum){
       return result;
    }
}

class Solution {
    public List<Integer> minSubsequence(int[] nums) {
        //Sort the Array nums
        Arrays.sort(nums);
        int sum=0;
        int currentSum=0;
        List<Integer> result=new ArrayList<Integer>();

        for(int n:nums){
            sum+=n;
        }

        for(int i=nums.length-1;i>=0;i--){
            result.add(nums[i]);
            sum-=nums[i];
            currentSum+=nums[i];
            if(currentSum>sum){
                return result;
            }
        }
        return result;
    }
}

The worst case time complexity for this approach will be O(n).

Conclusion

I hope you have learned a lot from this article and your suggestion/approaches are also highly welcomed as I believe in learning in Public and consistent practice to improve logic building.

Thank you for taking the time to read this blog and will meet next time with another challenge..✌️

LeetCode Challenge #2 - Minimum Subsequence in Non-Increasing Order

Table of contents

Introduction

Question

Solution

Conclusion