Skip to main content
Talentd

Subsequence of Size K With the Largest Even Sum - Solution & Explanation

MediumPremiumFree on FleetCodeArrayGreedySorting10 min readAsked at: Microsoft, Drw, Retailmenot
Practice this problem

Problem Statement

You are given an integer array nums and an integer k. Find the largest even sum of any subsequence of nums that has a length of k.

Return this sum, or -1 if such a sum does not exist.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

 

Example 1:

Input: nums = [4,1,5,3,1], k = 3
Output: 12
Explanation:
The subsequence with the largest possible even sum is [4,5,3]. It has a sum of 4 + 5 + 3 = 12.

Example 2:

Input: nums = [4,6,2], k = 3
Output: 12
Explanation:
The subsequence with the largest possible even sum is [4,6,2]. It has a sum of 4 + 6 + 2 = 12.

Example 3:

Input: nums = [1,3,5], k = 1
Output: -1
Explanation:
No subsequence of nums with length 1 has an even sum.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105
  • 1 <= k <= nums.length

Approach Overview

Problem Overview: You are given an integer array and an integer k. Select a subsequence of exactly k elements such that their total sum is even and as large as possible. If no such subsequence exists, return -1.

Approach 1: Brute Force Enumeration (Exponential Time)

Generate every subsequence of size k, compute its sum, and track the largest sum that is even. This can be implemented using recursion or bitmask enumeration. The method checks C(n, k) combinations, giving O(C(n,k) * k) time complexity and O(k) auxiliary space for the current subset. It works only for very small arrays and is mainly useful for validating logic or understanding the constraint that the final sum must be even.

Approach 2: Greedy + Sorting (O(n log n))

The optimal strategy starts by sorting the array in descending order so the largest values are considered first. Select the top k numbers and compute their sum. If the sum is already even, this is the best possible result because replacing any element would reduce the total. If the sum is odd, adjust the selection using parity swaps.

Track the smallest odd and smallest even number inside the chosen k elements, and the largest odd and largest even number outside the selection. To fix an odd sum, perform one of two swaps: replace a chosen odd with an outside even, or replace a chosen even with an outside odd. Both swaps flip the parity of the total sum. Compute the resulting sums for both options and choose the larger valid even sum. Sorting dominates the runtime, giving O(n log n) time and O(1) extra space beyond the sort.

This approach works because parity is the only constraint preventing the maximum sum. By keeping the best candidates for odd-even swaps, you adjust the parity with the smallest possible loss in value.

Recommended for interviews: Interviewers expect the Greedy + Sorting solution. The brute force explanation shows you understand the constraint space, but recognizing that parity can be fixed with a minimal swap demonstrates strong reasoning with arrays, greedy algorithms, and sorting. The final solution runs in O(n log n) and handles all edge cases cleanly.

Solution

We notice that the problem involves selecting a subsequence, so we can consider sorting the array first.

Next, we greedily select the largest k numbers. If the sum of these numbers is even, we directly return this sum ans.

Otherwise, we have two greedy strategies:

  1. Among the largest k numbers, find the smallest even number mi1, and then among the remaining n - k numbers, find the largest odd number mx1. Replace mi1 with mx1. If such a replacement exists, then the sum after replacement ans - mi1 + mx1 is guaranteed to be even;
  2. Among the largest k numbers, find the smallest odd number mi2, and then among the remaining n - k numbers, find the largest even number mx2. Replace mi2 with mx2. If such a replacement exists, then the sum after replacement ans - mi2 + mx2 is guaranteed to be even.

We take the largest even sum as the answer. If no even sum exists, return -1.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subsequence EnumerationO(C(n,k) * k)O(k)Useful for understanding the constraint or verifying small inputs
Greedy + SortingO(n log n)O(1)General optimal solution; handles parity adjustments efficiently

Video Solution

2098. Subsequence of Size K With the Largest Even Sum (Leetcode Medium) • Programming Live with Larry • 600 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Subsequence of Size K With the Largest Even Sum easy or hard?
The problem is rated Medium because the main difficulty is recognizing how to fix parity without sacrificing too much sum. Once you realize that a single odd-even swap can flip the parity, the greedy + sorting solution becomes straightforward.
Subsequence of Size K With the Largest Even Sum Python/Java solution
Most implementations follow the same greedy logic: sort the array in descending order, compute the sum of the first k elements, and adjust parity using a single swap if needed. The code is straightforward to implement in Python, Java, C++, Go, or TypeScript with O(n log n) complexity.
How to solve Subsequence of Size K With the Largest Even Sum in O(n)?
Pure O(n) solutions are difficult because you typically need ordering to guarantee the largest sum. However, you can approximate linear time using selection algorithms (like partial selection or heaps) to find the top k elements and track candidate odd/even swaps. The standard interview solution remains the simpler O(n log n) greedy + sorting approach.
What is the best approach for Subsequence of Size K With the Largest Even Sum?
The most effective solution uses a greedy strategy combined with sorting. Sort the array in descending order and select the largest k numbers. If their sum is odd, swap the smallest odd or even element inside the selection with a compatible element outside to make the total even. This runs in O(n log n) time and O(1) extra space.
Is Subsequence of Size K With the Largest Even Sum asked at Google/Amazon/Meta?
This problem reflects common interview themes used by companies such as Amazon, Google, and Meta: greedy selection, parity reasoning, and array optimization. Variants involving selecting k elements with constraints appear frequently in coding interviews.
What data structure is used in Subsequence of Size K With the Largest Even Sum?
The solution mainly relies on arrays and sorting. While scanning the sorted list, you track candidate odd and even values to perform parity swaps. No complex data structures are required beyond the sorted array.
What is the time complexity of Subsequence of Size K With the Largest Even Sum?
The optimal greedy solution runs in O(n log n) time because the array must be sorted. After sorting, selecting the first k elements and evaluating parity swaps takes O(n) time. Space complexity is O(1) beyond the sorting operation.

Ready to solve this problem?

Practice Subsequence of Size K With the Largest Even Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Sub-arrays With Odd Sum

Next

Partition Array for Maximum Sum