1403. Minimum Subsequence in Non-Increasing Order

EasyGreedyArraySorting
Leetcode Link

Problem Description

The task is to find a subsequence from a given array nums such that the sum of this subsequence's elements is strictly greater than the sum of the elements that are not included in the subsequence. A subsequence is defined as a sequence that can be derived from the array by removing some or no elements without changing the order of the remaining elements.

The constraints for the solution are:

  • If there are multiple subsequences that satisfy the condition, the one with the smallest number of elements should be returned.
  • If there is still more than one subsequence with the minimum number of elements, the subsequence among them with the maximum total sum should be returned.
  • The returned subsequence should be sorted in non-increasing order (from the largest to the smallest element).
  • It is guaranteed that a unique solution exists for the given constraints.

Intuition

To arrive at the solution, we should understand the following points:

  • A subsequence with the largest possible elements will contribute more towards making its sum greater than the rest of the elements.
  • Sorting the array in non-increasing order helps in picking out the subsequence with the maximum possible sum in the smallest size.
  • Accumulating the items from the sorted array until the running total sum (t) of these items is greater than the sum of the remaining items (s - t) gives a subsequence that fulfills the condition.

Now, considering these points, the algorithm follows these steps:

  1. Sort the array in non-increasing order.
  2. Iterate over the sorted array, adding each element to a running total (t) and storing the element in a subsequence result (ans).
  3. After each addition, check if the sum of elements in this subsequence result (t) is strictly greater than the sum of the remaining elements in the original array (s - t).
  4. Continue accumulating elements until the condition is met.

Once the condition is met, the current subsequence result (ans) contains the minimum number of elements with the maximum sum, sorted in non-increasing order. This is the desired subsequence to be returned.

Learn more about Greedy and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Solution Approach

The solution approach takes advantage of the sorting algorithm and a greedy strategy to create the desired subsequence. Here's a walkthrough of the implementation based on the reference solution provided:

  1. First, we need to know the sum of all elements in the given array nums. This is calculated with the expression sum(nums) and stored in the variable s.

  2. We then define a variable t to keep track of the total sum of the selected subsequence as we build it. Initially, t is set to 0 since we haven't selected any elements yet.

  3. The input array nums is then sorted in non-increasing order using sorted(nums, reverse=True). Sorting the array allows us to consider larger elements first, aligning with the greedy approach of maximizing the sum of the subsequence.

  4. We initialize an empty list ans to store the elements of the subsequence.

  5. Next, we iterate over the sorted array. For each element x in the array:

    • We add the element x to the total t and also append x to our answer list ans.
    • After each addition, we check if the sum t is strictly greater than the sum of the remaining elements in the original array (s - t).
    • If this condition is true, it means the selected elements in ans now have a sum greater than that of the remaining elements of nums, fulfilling our requirement.

  6. The iteration is terminated immediately once our condition is met (i.e., when t > s - t). Since we are iterating over the array in non-increasing order, the first time this condition is met, we have the smallest subsequence with the greatest total sum.

  7. Lastly, the subsequence stored in ans is returned. This is the subsequence with the minimum size and maximum total sum, sorted in non-increasing order – as dictated by our sorting of nums.

By utilizing a greedy algorithmic approach along with elementary data structures like lists and performing array sorting, we have an efficient implementation that ensures the strict constraints of the problem are met and a unique solution is returned.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

Example Walkthrough

Let's use a small example to illustrate the solution approach. Consider the array nums = [4, 3, 1, 2]. We need to find a subsequence such that its sum is greater than the sum of the elements not included in it.

  1. Calculate the sum of all elements in nums: s = 4 + 3 + 1 + 2 = 10.

  2. Initialize t to 0, which will represent the total sum of our subsequence.

  3. Sort the array in non-increasing order: sorted_nums = [4, 3, 2, 1].

  4. Initialize an empty list ans to store our subsequence.

  5. Start iterating over the sorted array. We pick elements one by one and add to both t and ans.

    • First element x = 4: t = 0 + 4 = 4, ans = [4], and remaining sum s - t = 6. The sum of ans is not yet greater than the remaining sum.
    • Second element x = 3: t = 4 + 3 = 7, ans = [4, 3], and remaining sum s - t = 3. Now, the sum of ans is greater than the remaining sum (7 > 3).

  6. The condition t > s - t is met, so we stop iterating.

  7. The resulting subsequence ans = [4, 3] is already sorted in non-increasing order, which is also the subsequence with the smallest number of elements and the maximum total sum out of all valid subsequences.

We return ans = [4, 3] as our final answer. This subsequence has a sum of 7, which is greater than the sum of the non-included elements (2 + 1 = 3). It's the smallest such subsequence with the largest sum, fulfilling all the problem's requirements.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minSubsequence(self, nums: List[int]) -> List[int]:
5        # Initialize the variable to store the resulting subsequence
6        result_subsequence = []
7      
8        # Calculate the total sum of the elements in nums
9        total_sum = sum(nums)
10      
11        # Initialize the variable to track the running total of the subsequence
12        subsequence_sum = 0
13      
14        # Sort the nums array in decreasing order
15        for num in sorted(nums, reverse=True):
16            # Add the current number to the running total
17            subsequence_sum += num
18          
19            # Append the current number to the result subsequence
20            result_subsequence.append(num)
21          
22            # Check if the sum of the subsequence is greater than the remaining elements
23            if subsequence_sum > total_sum - subsequence_sum:
24                # If true, break out of the loop
25                break
26      
27        # Return the result subsequence
28        return result_subsequence
29
1import java.util.Arrays;  // Import Arrays utility for sorting and streaming
2import java.util.List;    // Import List interface
3import java.util.ArrayList;  // Import ArrayList class for dynamic arrays
4
5class Solution {
6    public List<Integer> minSubsequence(int[] nums) {
7        // Sort the array in non-decreasing order
8        Arrays.sort(nums);
9      
10        // Prepare a list to store the result
11        List<Integer> result = new ArrayList<>();
12      
13        // Calculate the sum of all elements in the array
14        int totalSum = Arrays.stream(nums).sum();
15      
16        // Initialize a variable to keep track of the running sum of the subsequence
17        int subsequenceSum = 0;
18      
19        // Iterate over the array from the last element to the first
20        for (int i = nums.length - 1; i >= 0; i--) {
21            // Add the current element to the subsequence sum
22            subsequenceSum += nums[i];
23            // Add the current element to the result list
24            result.add(nums[i]);
25            // Check if the subsequence sum is greater than the remaining elements' sum
26            if (subsequenceSum > totalSum - subsequenceSum) {
27                // Break the loop if the subsequence sum is greater as we have the minimum subsequence
28                break;
29            }
30        }
31      
32        // Return the result list which now contains the minimum subsequence
33        return result;
34    }
35}
36
1#include <vector>
2#include <numeric> // For accumulate
3#include <algorithm> // For sort
4
5class Solution {
6public:
7    // Function to find the smallest subsequence with a sum greater than the sum of the remaining elements.
8    vector<int> minSubsequence(vector<int>& nums) {
9        // Sort the input vector in non-increasing order.
10        sort(nums.rbegin(), nums.rend());
11
12        // Calculate the total sum of all elements in the vector.
13        int totalSum = accumulate(nums.begin(), nums.end(), 0);
14        // This will keep track of the sum of the current subsequence.
15        int subsequenceSum = 0;
16        // This vector will store the elements of the smallest subsequence.
17        vector<int> answer;
18
19        // Iterate over the sorted array to accumulate a sum greater than the half of total sum.
20        for (int num : nums) { // Using num instead of x for clarity.
21            subsequenceSum += num; // Add the current element to the subsequence sum.
22            answer.push_back(num); // Add the current element to the subsequence.
23            // Check if the current subsequence sum is greater than the sum of the remaining elements.
24            if (subsequenceSum > totalSum - subsequenceSum) {
25                break; // Terminate the loop if the condition is true.
26            }
27        }
28
29        // Return the resulting subsequence.
30        return answer;
31    }
32};
33
1function minSubsequence(nums: number[]): number[] {
2    // Sort the array in non-increasing order (largest to smallest)
3    nums.sort((a, b) => b - a);
4
5    // Calculate the sum of all elements in the array
6    const totalSum = nums.reduce((sum, current) => sum + current, 0);
7
8    let subsequenceSum = 0;
9
10    // Iterate through the sorted array
11    for (let i = 0; i < nums.length; i++) {
12        // Add the current element to the subsequence sum
13        subsequenceSum += nums[i];
14
15        // Check if the sum of the elements of the subsequence is greater than
16        // the sum of the remaining elements in the array
17        if (subsequenceSum > totalSum - subsequenceSum) {
18            // If the condition is met, return the subsequence from the start
19            // up to the current element
20            return nums.slice(0, i + 1);
21        }
22    }
23  
24    // In case no subsequence is found that satisfies the condition
25    // Though this case won't occur as per the problem's constraints,
26    // we need to return something to satisfy TypeScript's return type.
27    // An empty subsequence signifies failure to find the desired subset.
28    return [];
29}
30
Not Sure What to Study? Take the 2-min Quiz：

How many ways can you arrange the three letters A, B and C?

Time and Space Complexity

Time Complexity

The time complexity of the given code is primarily determined by the sorting operation. Here, sorted(nums, reverse=True) sorts the input list nums in descending order. The sorting algorithm used in Python's sorted function is Timsort, which has a time complexity of O(n log n) for the average and worst case, where n is the number of elements in the input list.

After sorting, the code iterates through the sorted list once. This single pass through the list has a time complexity of O(n).

Therefore, the overall time complexity of the code is dominated by the sorting operation and is O(n log n).

Space Complexity

The space complexity of the code involves the space needed for the output list ans and the temporary space used by the sorting operation.

The output list ans grows proportionally with the number of elements it includes, which in the worst case, can be all the elements of the input list nums. Hence, the space complexity for ans is O(n).

The sorting operation may require additional space for its internal workings (temp arrays for mergesort or hybrid sorts like Timsort). In Python, the sorted function does not sort in-place; instead, it returns a new sorted list. However, since this sorted list is not stored in an additional variable and is used in the same loop for iteration, the dominant additional space is the same as for ans, which has already been accounted for as O(n).

Therefore, the overall space complexity of the code is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫