2098. Subsequence of Size K With the Largest Even Sum

Problem Description

In this problem, you are provided with an array of integers named nums and an integer k. The task is to find the largest even sum of any subsequence of the array that is exactly k elements long. If no such sum exists, the function should return -1.

A subsequence is a sequence that can be derived from another sequence by deleting some or none of the elements without changing the order of the remaining elements. The challenge is to ensure the sum of the selected subsequence is the largest possible even number.

Intuition

To solve this problem, we can follow a series of logical steps:

1. Sort the array so we can work with the elements in an ordered manner, which is helpful for both finding the largest elements and managing even and odd sums.

2. Calculate the sum of the last k elements following the sort (which are the k largest elements). This sum represents the largest sum we could obtain from a subsequence of size k. If this sum is even, it's the answer we're looking for.

3. If the initial sum is odd, we need to adjust the subsequence such that the sum becomes even. This is done by either replacing the smallest odd element in the chosen subsequence with the largest odd element outside of it, or by replacing the smallest even element in the chosen subsequence with the largest even element outside of it.

4. Comparing these two options allows us to ensure we're choosing the substitution that results in the largest even sum. If neither replacement leads to an even sum or if replacements aren't available, we return -1 as no such subsequence sum exists.

5. Finally, we have to check whether our modified sum is even or not, as the replacements could potentially result in another odd sum. If it's even, we have our result; otherwise, we return -1.

This approach leverages sorting and evaluating even/odd sums to strategically build the correct subsequence with the largest even sum possible, ensuring an efficient solution.

Learn more about Greedy and Sorting patterns.

Solution Approach

The provided Python code implements a solution to the problem by using sorting and a little bit of greedy strategy to find the desired sum. Here's a step-by-step breakdown of how it works:

1. Sort the input array: The nums array is sorted in ascending order to facilitate the process of finding the largest elements and managing the sums.

   1nums.sort()

2. Find the initial sum: The sum of the last k elements from the sorted array is calculated. These are the largest k elements from nums.

   1ans = sum(nums[-k:])

3. Check if initial sum is even: If ans % 2 == 0, the initial sum is even, and we return it as our answer.

   1if ans % 2 == 0:
   2    return ans

4. Initialize variables: Variables mx1 and mx2 are initialized to -inf to store the largest odd and even numbers found before the subsequence. Variables mi1 and mi2 are initialized to inf to store the smallest odd and even numbers within the subsequence.

   1mx1 = mx2 = -inf
   2mi1 = mi2 = inf

5. Find potential replacements: Iterate over the array before kth last positions to find the largest odd (mx1) and even (mx2) numbers and similarly iterate over the k elements of the subsequence to find the smallest odd (mi2) and even (mi1) numbers.

   1for x in nums[: n - k]:
   2    if x & 1:
   3        mx1 = x
   4    else:
   5        mx2 = x
   6for x in nums[-k:][::-1]:
   7    if x & 1:
   8        mi2 = x
   9    else:
   10        mi1 = x

6. Attempt to adjust sum: Replace the smallest odd number from the subsequence with the largest odd number from outside it, or replace the smallest even number from the subsequence with the largest even number from outside it, and take the maximum of these two operations.

   1ans = max(ans - mi1 + mx1, ans - mi2 + mx2, -1)

7. Ensure the sum is even: If our new sum ans after replacement is still even, we return it; otherwise, we return -1 as no even-sum subsequence exists.

   1return -1 if ans % 2 else ans

The above steps use simple strategies of sorting and choosing the right combinations to make the sum even, while trying to ensure that the sum is maximized at every choice point.

Example Walkthrough

Let's illustrate the solution approach using a small example. Suppose we are given the following array of integers nums and an integer k.

1nums = [5, 3, 2, 4, 1]
2k = 3

The task is to find the largest even sum of any subsequence of the array that is k elements long.

Step 1: Sort the input array

First, we sort the nums array in ascending order:

1nums.sort()  # nums becomes [1, 2, 3, 4, 5]

Step 2: Find the initial sum

Next, we calculate the sum of the last k elements, which are the largest k elements in the sorted array:

1ans = sum(nums[-k:])  # ans is the sum of [3, 4, 5], which equals 12

Step 3: Check if initial sum is even

We check if the initial sum ans is even:

1if ans % 2 == 0:  # 12 % 2 equals 0, so ans is even
2    return ans  # We would return 12 as the answer

Since ans is even, in our example, we can return it directly as the answer. However, let's proceed to demonstrate the adjustment steps in case the sum had been odd.

Step 4: Initialize variables

We would initialize the variables to prepare for potential replacements:

1mx1 = mx2 = -inf  # Initialize to negative infinity for comparison
2mi1 = mi2 = inf   # Initialize to infinity for comparison

Step 5: Find potential replacements

We'd iterate to find potential replacements. In the nums array [1, 2, 3, 4, 5], we search before the last k = 3 elements:

1For the elements [1, 2], mx1 and mx2 would be updated:
2mx1 = 1 (largest odd number)
3mx2 = 2 (largest even number)
4
5For the subsequence [3, 4, 5], mi1 and mi2 would be updated:
6mi1 = 4 (smallest even number)
7mi2 = 3 (smallest odd number)

Step 6: Attempt to adjust sum

If we needed to adjust the sum to make it even, we would carry out replacements:

1We replace mi1 with mx1: ans becomes 12 - 4 + 1 = 9 (odd sum, not valid)
2Or we replace mi2 with mx2: ans becomes 12 - 3 + 2 = 11 (also odd, not valid)
3Since neither replacement results in an even sum, we would move to the next step.

In this case, both options give us an odd sum, which means we cannot use them.

Step 7: Ensure the sum is even

Finally, we check if there exists a valid replacement that results in an even sum, if we hadn't already found an even sum in step 3:

1Since both options from step 6 resulted in odd sums and we have no other replacements, we would return -1.

In our original case, since ans was already even, we would have returned 12 at step 3 without needing these adjustments. But this walkthrough demonstrates what would happen if the initial sum was odd. In such a case, if no even sum can be found, the final result would be -1, indicating no valid subsequence exists with the desired properties.

Solution Implementation

Time and Space Complexity

Time Complexity

The function involves sorting the list of numbers, which has a time complexity of O(n log n), where n is the length of the list. After sorting, the function performs a constant amount of work that includes summing the last k numbers and a couple of linear scans over the n - k and k elements respectively. These scans contribute a O(n) time complexity. As a result, the overall time complexity of the function is dominated by the sorting step, giving us a time complexity of O(n log n).

Space Complexity

The space complexity of the function is O(1) since it only uses a constant amount of extra space for variables such as ans, mx1, mx2, mi1, mi2, and the iteration variables within the loops. The sorting is done in-place, and no additional data structures are used that scale with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.