Minimum Subsequence in Non-Increasing Order solution and explanation
9 more videos on this problem
1403. Minimum Subsequence in Non-Increasing Order || leetcode weekly-contest-183 || [C++ SOLUTION]code Explainer · 4:17 · 814 views
Leetcode 1403. Minimum Subsequence in Non-Increasing Order [Java]if else statement · 5:29 · 656 views
1403 Minimum Subsequence in Non-Increasing Order | Leetcode Easy Level Questions Complete PlaylistEduEverybody · 8:02 · 334 views
Vol25 - Leetcode - Problem 1403 - Minimum subsequence in non-increasing order - Golang - Phỏng vấnYuh lập trình viên · 14:16 · 298 views
1403. Minimum Subsequence in Non Increasing Order || LeetCodeAccioCoder · 7:00 · 235 views
Greedy Algorithm Problem-4: LeetCode 1403. Minimum Subsequence in Non-Increasing OrderDhananjay Sharma Officials · 17:06 · 189 views
LeetCode 1403 | Minimum Subsequence in Non-Increasing Order | PriorityQueue | JavaSleepy Cracker · 5:40 · 168 views
Leetcode 1403 Minimum Subsequence in Non Increasing OrderAlgorithmicIQ · 27:37 · 149 views
Minimum Subsequence in Non Increasing OrderAmit K · 7:13 · 142 views
Minimum Subsequence in Non-Increasing Order | Leetcode 1403 | Approach + Code with explanation.Pirai's Academy · 9:25 · 99 views
The 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.
Example 1:
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.
Example 2:
Input: nums = [4,4,7,6,7] Output: [7,7,6] Explanation: The subsequence [7,7] has the sum of its elements equal to 14 which is not strictly greater than the sum of elements not included (14 = 4 + 4 + 6). Therefore, the subsequence [7,6,7] is the minimal satisfying the conditions. Note the subsequence has to be returned in non-increasing order.
Constraints:
1 <= nums.length <= 5001 <= nums[i] <= 100
Approach overview
Problem Overview: Given an integer array, return the smallest subsequence such that the sum of its elements is strictly greater than the sum of the remaining elements. The result must be returned in non-increasing order. If multiple answers exist, choose the one with the largest total sum.
Approach 1: Greedy Approach Using Sorting (Time: O(n log n), Space: O(1) or O(n) depending on sort)
This problem naturally fits a greedy strategy. Larger numbers contribute more to the subsequence sum, so selecting the largest elements first minimizes how many elements you need. Start by sorting the array in descending order using a standard sorting algorithm. Compute the total sum of the array, then iterate through the sorted numbers while accumulating a running subsequence sum. Stop as soon as the subsequence sum becomes strictly greater than the remaining sum (totalSum - currentSum). Because elements are taken from largest to smallest, the resulting subsequence automatically satisfies the non-increasing order requirement.
This method is straightforward to implement and works well for typical constraints. The only expensive operation is sorting, which takes O(n log n) time. The greedy choice is optimal because selecting smaller elements earlier would require more elements to surpass the remaining sum.
Approach 2: Bucket Sort Optimization (Time: O(n + k), Space: O(k))
If the value range is small (as in the original constraints where values are between 1 and 100), sorting can be optimized using bucket counting. Create a frequency array where the index represents the number and the value represents how many times it appears. Then iterate from the largest possible value down to the smallest, greedily adding numbers to the subsequence while updating the running sum.
This avoids comparison-based sorting entirely. Building the frequency array takes O(n), and iterating over the value range takes O(k), where k is the maximum possible value. This approach leverages counting techniques commonly used with arrays and works well when the value range is limited.
Recommended for interviews: The greedy solution with sorting is what most interviewers expect. It demonstrates understanding of greedy algorithms and problem simplification. Mentioning the bucket sort optimization shows deeper awareness of constraints and how to reduce O(n log n) sorting to near linear time when the value range is small.
Approach 1: Greedy Approach Using Sorting
This approach involves sorting the original array in non-increasing order. After sorting, iterate over the sorted array while maintaining a running sum. Add elements to the subsequence until the sum of the subsequence becomes greater than the sum of the remaining elements. This greedy approach ensures that you include the largest elements first, thus achieving a minimal size subsequence with maximum sum.
def minSubsequence(nums):
nums.sort(reverse=True)
total_sum = sum(nums)
subseq_sum = 0
result = []
for num in nums:
subseq_sum += num
result.append(num)
total_sum -= num
if subseq_sum > total_sum:
break
return result
nums = [4, 3, 10, 9, 8]
print(minSubsequence(nums)) # Output: [10, 9]import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
public static List<Integer> minSubsequence(int[] nums) {
Arrays.sort(nums);
int totalSum = Arrays.stream(nums).sum();
int subseqSum = 0;
List<Integer> result = new ArrayList<>();
for (int i = nums.length - 1; i >= 0; i--) {
subseqSum += nums[i];
result.add(nums[i]);
totalSum -= nums[i];
if (subseqSum > totalSum) {
break;
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {4, 3, 10, 9, 8};
List<Integer> result = minSubsequence(nums);
System.out.println(result);
}
}#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
std::vector<int> minSubsequence(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end(), std::greater<int>());
int totalSum = std::accumulate(nums.begin(), nums.end(), 0);
int subseqSum = 0;
std::vector<int> result;
for (int num : nums) {
subseqSum += num;
result.push_back(num);
totalSum -= num;
if (subseqSum > totalSum) break;
}
return result;
}
int main() {
std::vector<int> nums = {4, 3, 10, 9, 8};
std::vector<int> result = minSubsequence(nums);
std::cout << "[";
for (size_t i = 0; i < result.size(); ++i) {
std::cout << result[i];
if (i < result.size() - 1) std::cout << ", ";
}
std::cout << "]\n";
return 0;
}function minSubsequence(nums) {
nums.sort((a, b) => b - a);
let totalSum = nums.reduce((acc, curr) => acc + curr, 0);
let subseqSum = 0;
const result = [];
for (let num of nums) {
subseqSum += num;
result.push(num);
totalSum -= num;
if (subseqSum > totalSum) break;
}
return result;
}
const nums = [4, 3, 10, 9, 8];
console.log(minSubsequence(nums)); // Output: [10, 9]#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void *a, const void *b) {
return (*(int *)b - *(int *)a);
}
int* minSubsequence(int* nums, int numsSize, int* returnSize) {
qsort(nums, numsSize, sizeof(int), compare);
int totalSum = 0, subseqSum = 0, idx = 0;
for (int i = 0; i < numsSize; i++) totalSum += nums[i];
int* result = (int*) malloc(numsSize * sizeof(int));
for (int i = 0; i < numsSize; i++) {
subseqSum += nums[i];
totalSum -= nums[i];
result[idx++] = nums[i];
if (subseqSum > totalSum) break;
}
*returnSize = idx;
return result;
}
int main() {
int nums[] = {4, 3, 10, 9, 8};
int returnSize;
int* result = minSubsequence(nums, 5, &returnSize);
printf("[");
for (int i = 0; i < returnSize; i++) {
printf("%d", result[i]);
if (i < returnSize - 1) printf(", ");
}
printf("]\n");
free(result);
return 0;
}using System;
using System.Collections.Generic;
class Program {
static List<int> MinSubsequence(int[] nums) {
Array.Sort(nums, (a, b) => b.CompareTo(a));
int totalSum = 0;
int subseqSum = 0;
foreach (var num in nums) {
totalSum += num;
}
List<int> result = new List<int>();
foreach (var num in nums) {
subseqSum += num;
result.Add(num);
totalSum -= num;
if (subseqSum > totalSum) break;
}
return result;
}
static void Main() {
int[] nums = { 4, 3, 10, 9, 8 };
List<int> result = MinSubsequence(nums);
Console.WriteLine(string.Join(", ", result));
}
}The Python solution sorts the array in descending order and then iterates through it, adding elements to a new list until the sum of this new list is greater than the remaining elements' sum. This utilizes Python's built-in sort method and is efficient for the given constraints.
Time Complexity: O(n log n), for sorting the list.
Space Complexity: O(n) for the result list.
Approach 2: Alternative Approach Using Bucket Sort
This approach leverages the constraint that elements in the array are between 1 and 100. By using a frequency array (or bucket sort), we can count occurrences of each number. We iterate from the highest value downward, and construct a subsequence using the most frequent elements until the subsequence sum exceeds the sum of non-included elements. This reduces the time complexity associated with sorting large arrays.
def minSubsequence(nums):
buckets = [0] * 101
total_sum = sum(nums)
for num in nums:
buckets[num] += 1
subseq_sum = 0
result = []
for i in range(100, 0, -1):
while buckets[i] > 0:
subseq_sum += i
result.append(i)
if subseq_sum > total_sum - subseq_sum:
return result
buckets[i] -= 1
print(minSubsequence([4, 4, 7, 6, 7])) # Output: [7, 7, 6]import java.util.*;
public class Main {
public static List<Integer> minSubsequence(int[] nums) {
int[] count = new int[101];
int totalSum = 0;
for (int num : nums) {
count[num]++;
totalSum += num;
}
List<Integer> result = new ArrayList<>();
int subseqSum = 0;
for (int i = 100; i >= 1; i--) {
while (count[i]-- > 0) {
subseqSum += i;
result.add(i);
if (subseqSum > totalSum - subseqSum) return result;
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {4, 4, 7, 6, 7};
List<Integer> result = minSubsequence(nums);
System.out.println(result);
}
}#include <iostream>
#include <vector>
using namespace std;
vector<int> minSubsequence(vector<int>& nums) {
vector<int> count(101, 0);
int totalSum = 0;
for (int num : nums) {
count[num]++;
totalSum += num;
}
vector<int> result;
int subseqSum = 0;
for (int i = 100; i > 0; --i) {
while (count[i]-- > 0) {
subseqSum += i;
result.push_back(i);
if (subseqSum > totalSum - subseqSum) return result;
}
}
}
int main() {
vector<int> nums = {4, 4, 7, 6, 7};
vector<int> result = minSubsequence(nums);
for (int val : result) {
cout << val << " ";
}
cout << endl;
return 0;
}function minSubsequence(nums) {
let buckets = Array(101).fill(0);
let totalSum = nums.reduce((sum, num) => sum + num, 0);
nums.forEach(num => buckets[num]++);
let subseqSum = 0;
const result = [];
for (let i = 100; i > 0; i--) {
while (buckets[i] > 0) {
subseqSum += i;
result.push(i);
buckets[i]--;
if (subseqSum > totalSum - subseqSum) return result;
}
}
}
console.log(minSubsequence([4, 4, 7, 6, 7])); // Output: [7, 7, 6]#include <stdio.h>
#include <stdlib.h>
int* minSubsequence(int* nums, int numsSize, int* returnSize) {
int buckets[101] = {0};
int totalSum = 0;
for (int i = 0; i < numsSize; i++) {
buckets[nums[i]]++;
totalSum += nums[i];
}
int subseqSum = 0;
int* result = (int*) malloc(numsSize * sizeof(int));
int idx = 0;
for (int i = 100; i > 0; i--) {
while (buckets[i]-- > 0) {
subseqSum += i;
result[idx++] = i;
totalSum -= i;
if (subseqSum > totalSum) {
*returnSize = idx;
return result;
}
}
}
*returnSize = idx;
return result;
}
int main() {
int nums[] = {4, 4, 7, 6, 7};
int returnSize;
int* result = minSubsequence(nums, 5, &returnSize);
printf("[");
for (int i = 0; i < returnSize; i++) {
printf("%d", result[i]);
if (i < returnSize - 1) printf(", ");
}
printf("]\n");
free(result);
return 0;
}using System;
using System.Collections.Generic;
class Program {
static List<int> MinSubsequence(int[] nums) {
int[] count = new int[101];
int totalSum = 0;
foreach (var num in nums) {
count[num]++;
totalSum += num;
}
List<int> result = new List<int>();
int subseqSum = 0;
for (int i = 100; i >= 1; i--) {
while (count[i]-- > 0) {
subseqSum += i;
result.Add(i);
if (subseqSum > totalSum - subseqSum) return result;
}
}
return result;
}
static void Main() {
int[] nums = { 4, 4, 7, 6, 7 };
List<int> result = MinSubsequence(nums);
Console.WriteLine(string.Join(", ", result));
}
}The Python solution constructs buckets to count element frequencies, iterating backwards to assemble a subsequence from greatest frequencies first. This efficiently ensures the condition is satisfied while minimizing subsequence length.
Time Complexity: O(n + k), k being 100, the possible range values.
Space Complexity: O(n + k), needed for result and bucket storage.
Approach 3: Sorting
We can first sort the array nums in descending order, then add the elements to the array from largest to smallest. After each addition, we check whether the sum of the current elements is greater than the sum of the remaining elements. If it is, we return the current array.
The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array nums.
function minSubsequence(nums: number[]): number[] {
nums.sort((a, b) => b - a);
const s = nums.reduce((r, c) => r + c);
let t = 0;
for (let i = 0; ; ++i) {
t += nums[i];
if (t > s - t) {
return nums.slice(0, i + 1);
}
}
}func minSubsequence(nums []int) (ans []int) {
sort.Ints(nums)
s, t := 0, 0
for _, x := range nums {
s += x
}
for i := len(nums) - 1; ; i-- {
t += nums[i]
ans = append(ans, nums[i])
if t > s-t {
return
}
}
}impl Solution {
pub fn min_subsequence(mut nums: Vec<i32>) -> Vec<i32> {
nums.sort_by(|a, b| b.cmp(a));
let sum = nums.iter().sum::<i32>();
let mut res = vec![];
let mut t = 0;
for num in nums.into_iter() {
t += num;
res.push(num);
if t > sum - t {
break;
}
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach Using Sorting | Time Complexity: O(n log n), for sorting the list. |
| Alternative Approach Using Bucket Sort | Time Complexity: O(n + k), k being 100, the possible range values. |
| Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) to O(n) | General case. Simple and reliable for any value range. |
| Bucket Sort Greedy | O(n + k) | O(k) | When element values fall within a small fixed range (e.g., 1–100). |
Frequently asked questions
Is Minimum Subsequence in Non-Increasing Order easy or hard?
Minimum Subsequence in Non-Increasing Order is classified as an Easy problem. The key insight is recognizing that picking the largest elements first minimizes the subsequence length. Once that greedy idea is clear, the implementation becomes straightforward.
Minimum Subsequence in Non-Increasing Order Python/Java solution
In Python or Java, the typical implementation sorts the array in descending order, calculates the total sum, and iteratively adds elements to a result list until the subsequence sum exceeds the remaining sum. The logic is identical across languages and runs in O(n log n) time.
How to solve Minimum Subsequence in Non-Increasing Order in O(n)?
An O(n) style solution is possible using bucket sort when the value range is small. Count the frequency of each number, then iterate from the largest value down while accumulating the subsequence sum. This avoids comparison-based sorting and processes elements in linear time relative to the input size and value range.
What is the best approach for Minimum Subsequence in Non-Increasing Order?
The most common solution uses a greedy strategy combined with sorting. Sort the array in descending order and keep adding elements to the subsequence until its sum becomes strictly greater than the sum of the remaining elements. This approach runs in O(n log n) time due to sorting and guarantees the smallest valid subsequence.
Is Minimum Subsequence in Non-Increasing Order asked at Google/Amazon/Meta?
Greedy array problems like this frequently appear in interviews at companies such as Amazon and Google because they test reasoning about optimal choices and sorting strategies. Variations of subsequence and greedy selection problems are common in coding interviews.
What data structure is used in Minimum Subsequence in Non-Increasing Order?
The primary structure is an array. The greedy sorting approach relies on sorting the array and iterating through it. The optimized version additionally uses a frequency array (bucket) to count occurrences of each value before selecting elements in descending order.
What is the time complexity of Minimum Subsequence in Non-Increasing Order?
The standard greedy solution takes O(n log n) time because the array must be sorted before selecting elements. After sorting, a single linear scan builds the subsequence. If bucket counting is used with a limited value range, the complexity can be reduced to O(n + k).