LeetCode 2098 - Subsequence of Size K With the Largest Even Sum

LeetCode Problem 2098

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to find the largest possible even sum of a subsequence of length k from a given integer array nums. A subsequence is a sequence that can be obtained by deleting some elements from the array without changing the relative order of the remaining elements. The input consists of an array of integers nums and an integer k, which specifies the required length of the subsequence. The output is either the largest even sum obtainable or -1 if no such sum exists.

The constraints indicate that the array can be very large, up to 10^5 elements, and the values in the array can be up to 10^5. This rules out any brute-force solution that tries all possible subsequences of length k, since there are C(n, k) possible subsequences, which is infeasible for large n.

Edge cases to consider include arrays where all numbers are odd or all numbers are even, arrays where k equals nums.length, arrays with zeros, and cases where no even sum of length k exists.

Approaches

The brute-force approach would generate all subsequences of length k, compute their sums, and track the largest sum that is even. This guarantees correctness but is computationally infeasible due to the combinatorial explosion of possible subsequences. Specifically, generating C(n, k) subsequences has exponential time complexity.

The optimal approach leverages sorting and a greedy strategy. The main insight is that to maximize the sum, we generally want the largest k numbers. If the sum of these k largest numbers is even, we are done. If it is odd, we need to swap one element in this subsequence with an element outside it to make the sum even, selecting swaps that minimize the loss in total sum. Specifically, we consider replacing the smallest odd number in the selected subsequence with the largest even number outside it, or replacing the smallest even number with the largest odd number outside it. This approach works because sorting allows us to identify candidates for swaps efficiently.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(C(n, k) * k)	O(k)	Generate all subsequences of length k and compute sums
Optimal	O(n log n)	O(n)	Sort array and use greedy swaps to ensure largest even sum

Algorithm Walkthrough

Sort the array in descending order so the largest numbers are first.
Select the first k elements as the initial candidate subsequence and compute its sum.
If the sum is even, return it immediately, since it is the largest possible sum of k numbers.
If the sum is odd, identify candidates for swapping:

The smallest odd number in the selected subsequence.
The smallest even number in the selected subsequence.
The largest even number outside the subsequence.
The largest odd number outside the subsequence.

Attempt swaps:

Replace the smallest odd number in the subsequence with the largest even number outside it.
Replace the smallest even number in the subsequence with the largest odd number outside it.

Compute the resulting sums from both swaps (if possible) and return the maximum even sum among them.
If no swap results in an even sum, return -1.

Why it works: By sorting, we ensure the initial sum is maximized. Swaps are carefully chosen to minimally reduce the sum while correcting parity, guaranteeing the largest possible even sum.

Python Solution

from typing import List

class Solution:
    def largestEvenSum(self, nums: List[int], k: int) -> int:
        nums.sort(reverse=True)
        selected = nums[:k]
        sum_selected = sum(selected)
        
        if sum_selected % 2 == 0:
            return sum_selected
        
        smallest_odd_in = None
        smallest_even_in = None
        for num in selected[::-1]:
            if num % 2 == 0 and smallest_even_in is None:
                smallest_even_in = num
            if num % 2 == 1 and smallest_odd_in is None:
                smallest_odd_in = num
        
        largest_even_out = None
        largest_odd_out = None
        for num in nums[k:]:
            if num % 2 == 0 and largest_even_out is None:
                largest_even_out = num
            if num % 2 == 1 and largest_odd_out is None:
                largest_odd_out = num
            if largest_even_out is not None and largest_odd_out is not None:
                break
        
        candidates = []
        if smallest_odd_in is not None and largest_even_out is not None:
            candidates.append(sum_selected - smallest_odd_in + largest_even_out)
        if smallest_even_in is not None and largest_odd_out is not None:
            candidates.append(sum_selected - smallest_even_in + largest_odd_out)
        
        return max(candidates) if candidates else -1

The Python implementation follows the algorithm exactly. Sorting identifies the largest k elements. We then check parity and attempt swaps to fix an odd sum. Using variables for the smallest and largest elements ensures minimal loss when swapping, maximizing the sum.

Go Solution

import "sort"

func largestEvenSum(nums []int, k int) int64 {
    sort.Sort(sort.Reverse(sort.IntSlice(nums)))
    selected := nums[:k]
    var sumSelected int64 = 0
    for _, num := range selected {
        sumSelected += int64(num)
    }
    
    if sumSelected%2 == 0 {
        return sumSelected
    }
    
    var smallestOddIn, smallestEvenIn *int
    for i := k - 1; i >= 0; i-- {
        if selected[i]%2 == 0 && smallestEvenIn == nil {
            smallestEvenIn = &selected[i]
        }
        if selected[i]%2 == 1 && smallestOddIn == nil {
            smallestOddIn = &selected[i]
        }
    }
    
    var largestEvenOut, largestOddOut *int
    for i := k; i < len(nums); i++ {
        if nums[i]%2 == 0 && largestEvenOut == nil {
            largestEvenOut = &nums[i]
        }
        if nums[i]%2 == 1 && largestOddOut == nil {
            largestOddOut = &nums[i]
        }
        if largestEvenOut != nil && largestOddOut != nil {
            break
        }
    }
    
    var candidates []int64
    if smallestOddIn != nil && largestEvenOut != nil {
        candidates = append(candidates, sumSelected-int64(*smallestOddIn)+int64(*largestEvenOut))
    }
    if smallestEvenIn != nil && largestOddOut != nil {
        candidates = append(candidates, sumSelected-int64(*smallestEvenIn)+int64(*largestOddOut))
    }
    
    if len(candidates) == 0 {
        return -1
    }
    
    var max int64 = candidates[0]
    if len(candidates) == 2 && candidates[1] > max {
        max = candidates[1]
    }
    return max
}

In Go, we handle pointers to track the smallest and largest candidates for swaps. We also use int64 to prevent overflow when summing potentially large numbers. The logic mirrors Python exactly.

Worked Examples

Example 1: nums = [4,1,5,3,1], k = 3

Sort: [5,4,3,1,1]
Select first 3: [5,4,3], sum = 12 (even) → return 12

Example 2: nums = [4,6,2], k = 3

Sort: [6,4,2]
Select first 3: [6,4,2], sum = 12 (even) → return 12

Example 3: nums = [1,3,5], k = 1

Sort: [5,3,1]
Select first 1: [5], sum = 5 (odd)
No even outside → return -1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates; scanning for swap candidates is O(n)
Space	O(n)	For storing sorted array and candidate subsequence

Sorting drives the time complexity. All other operations are linear in n and constant in space beyond the input.

Test Cases

# Provided examples
assert Solution().largestEvenSum([4,1,5,3,1], 3) == 12  # largest even sum exists
assert Solution().largestEvenSum([4,6,2], 3) == 12     # all numbers selected
assert Solution().largestEvenSum([1,3,5], 1) == -1     # no even sum possible

# Boundary cases
assert Solution().largestEvenSum([2], 1) == 2          # single even number
assert Solution().largestEvenSum([1], 1) == -1         # single odd number
assert Solution().largestEvenSum([0,0,0], 2) == 0      # zeros handled correctly
assert Solution().largestEvenSum([1,2,3,4,5,6], 6) == 21 - 1  # sum of