algoadvance

Leetcode 1403. Minimum Subsequence in Non

Problem Statement

Given an array nums of integers, you need to return the minimum subsequence such that the sum of the subsequence is strictly greater than the sum of the remaining elements of the array. If there are multiple solutions, return the subsequence with the maximum sum. If there still are multiple solutions, return the subsequence with the minimum size. It can be assumed that there is always a solution.

Clarifying Questions

  1. What should be the return type?
    • The function should return a vector of integers.
  2. Are negative numbers allowed in the array?
    • Yes, according to the problem statement, the array can contain negative integers as well.
  3. Does the subsequence need to maintain the order from the original array?
    • No, the subsequence should be returned in non-increasing order.

Strategy

  1. Sum Calculation:
    • Compute the total sum of the array first.
  2. Sorting:
    • Sort the array in non-increasing order.
  3. Subsequence Selection:
    • Start selecting elements from the beginning of the sorted array until the sum of the selected elements is greater than half the total sum.
  4. Return Result:
    • The selected elements form the required subsequence.

Code

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> minSubsequence(std::vector<int>& nums) {
    // Calculate total sum of the array
    int totalSum = 0;
    for (int num : nums) {
        totalSum += num;
    }
    
    // Sort the array in non-increasing order
    std::sort(nums.begin(), nums.end(), std::greater<int>());
    
    // Select elements until their sum is greater than half of totalSum
    std::vector<int> result;
    int subsequenceSum = 0;
    
    for (int num : nums) {
        subsequenceSum += num;
        result.push_back(num);
        
        if (subsequenceSum > totalSum / 2) {
            break;
        }
    }
    
    return result;
}

int main() {
    std::vector<int> nums = {4, 3, 10, 9, 8};
    std::vector<int> result = minSubsequence(nums);
    
    std::cout << "Minimum Subsequence: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Time Complexity

The overall time complexity is dominated by the sorting step, so the final time complexity is O(n log n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI