Skip to content

1403. Minimum Subsequence in Non-Increasing Order

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  vector<int> minSubsequence(vector<int>& nums) {
    vector<int> ans;
    priority_queue<int> maxHeap(nums.begin(), nums.end());
    int half = accumulate(nums.begin(), nums.end(), 0) / 2;

    while (half >= 0) {
      ans.push_back(maxHeap.top());
      half -= maxHeap.top(), maxHeap.pop();
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public List<Integer> minSubsequence(int[] nums) {
    List<Integer> ans = new ArrayList<>();
    Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    for (final int num : nums)
      maxHeap.offer(num);
    int half = Arrays.stream(nums).sum() / 2;

    while (half >= 0) {
      ans.add(maxHeap.peek());
      half -= maxHeap.poll();
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def minSubsequence(self, nums: list[int]) -> list[int]:
    ans = []
    maxHeap = [-num for num in nums]
    heapq.heapify(maxHeap)
    half = sum(nums) // 2

    while half >= 0:
      ans.append(-maxHeap[0])
      half += heapq.heappop(maxHeap)

    return ans