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.

Description Hints 3 Solution Video 11:19

2098. Subsequence of Size K With the Largest Even Sum

Medium35.5% acceptance3 companiesPremium elsewhere, free here

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 <= 10⁵
0 <= nums[i] <= 10⁵
1 <= k <= nums.length

Asked at 3 companies

Drw Retailmenot Microsoft

Topics

Hints open one at a time

Hint 1

Is the sum of two even numbers even or odd? How about two odd numbers? One odd number and one even number?

Hint 2

If there is an even number of odd numbers, the sum will be even and vice versa.

Hint 3

Create an integer array to store all the even numbers in nums and another array to store all the odd numbers in nums. Sort both arrays.

11:19

Still stuck?Read the written solution, or watch a walkthrough.

Open solution