LeetCode Solutions Blog

Subsequence of Size K With the Largest Even Sum

Number: 2242

Difficulty: Medium

Paid? Yes

Problem Description

Given an integer array nums and an integer k, the objective is to find a subsequence (maintaining original order) of size k whose sum is as large as possible while remaining even. If no k-length subsequence with an even sum exists, return -1.

Key Insights

The problem is about selecting k elements from the array so that the total sum is maximized and even.
A greedy method suggests selecting the k largest numbers; however, the parity (even/odd) of the sum must be adjusted.
The sum of selected numbers is even if and only if the count of odd numbers in the selection is even.
If the sum of the k selected largest numbers is odd, then a minimal swap can be attempted:
- Swap a small odd number from the selected set with a large even number from the remaining elements.
- Alternatively, swap a small even number from the selected set with a large odd number from the remaining elements.
The challenge is in finding these candidate elements to perform the swap, if possible, to achieve an even sum.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(n) for storing the sorted array (or O(1) extra space if sorting in-place).

Solution

The approach begins by sorting the array in descending order so that the k largest elements are considered first. Compute the sum of these k elements. If the sum is even, return it immediately as it is the maximum possible sum under the constraints.

If the sum is odd, we attempt to correct the parity by swapping:

Identify the smallest odd number in the selected subset and the largest even number in the remaining elements.
Also, identify the smallest even number in the selected subset and the largest odd number in the remaining elements.
Perform the swap that yields the highest resulting even sum.
If neither swap is possible, return -1.

This method uses sorting combined with a greedy swap approach to adjust the parity minimally while preserving the maximal sum property.

Code Solutions

# Python solution for "Subsequence of Size K With the Largest Even Sum"

def largestEvenSum(nums, k):
    # Sort the numbers in descending order to prioritize larger elements
    nums_sorted = sorted(nums, reverse=True)
    
    # Select the first k elements which are candidates for the maximum sum
    selected = nums_sorted[:k]
    current_sum = sum(selected)
    
    # If the current selected sum is already even, return it
    if current_sum % 2 == 0:
        return current_sum
    
    # Initialize candidate variables for swapping
    candidate_odd_in_sel = None  # smallest odd in the selected k elements
    candidate_even_in_sel = None # smallest even in the selected k elements
    
    # Find smallest odd and even in the selected part
    for num in selected:
        if num % 2 == 1:
            if candidate_odd_in_sel is None or num < candidate_odd_in_sel:
                candidate_odd_in_sel = num
        else:
            if candidate_even_in_sel is None or num < candidate_even_in_sel:
                candidate_even_in_sel = num
    
    # In the rest of the array (not selected) find the largest even and largest odd candidates
    candidate_even_out = None  # largest even in the remaining numbers
    candidate_odd_out = None   # largest odd in the remaining numbers
    
    for num in nums_sorted[k:]:
        if num % 2 == 0 and candidate_even_out is None:
            candidate_even_out = num
        if num % 2 == 1 and candidate_odd_out is None:
            candidate_odd_out = num
        # Since list is sorted descending, the first encountered candidate is the best
    
    # Attempt both swapping scenarios to achieve an even sum:
    candidate_a = -1  # Swap candidate: odd from selected with even from the rest.
    candidate_b = -1  # Swap candidate: even from selected with odd from the rest.
    
    # Option 1: Remove a smallest odd from selection and add a largest even from outside.
    if candidate_odd_in_sel is not None and candidate_even_out is not None:
        candidate_a = current_sum - candidate_odd_in_sel + candidate_even_out
        # Check evenness: the swap guarantees an even sum.
    
    # Option 2: Remove a smallest even from selection and add a largest odd from outside.
    if candidate_even_in_sel is not None and candidate_odd_out is not None:
        candidate_b = current_sum - candidate_even_in_sel + candidate_odd_out
    
    # Choose the best even sum resulting from either candidate
    best_sum = max(candidate_a, candidate_b)
    return best_sum if best_sum % 2 == 0 and best_sum > 0 else -1

# Example usage:
print(largestEvenSum([4,1,5,3,1], 3))  # Expected output: 12
print(largestEvenSum([4,6,2], 3))      # Expected output: 12
print(largestEvenSum([1,3,5], 1))      # Expected output: -1