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:

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.
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.
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.
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.
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:

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.
```
nums.sort()
```
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.
```
ans = sum(nums[-k:])
```

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

if ans % 2 == 0:
    return ans

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.
```
mx1 = mx2 = -inf
mi1 = mi2 = inf
```

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.

for x in nums[: n - k]:
    if x & 1:
        mx1 = x
    else:
        mx2 = x
for x in nums[-k:][::-1]:
    if x & 1:
        mi2 = x
    else:
        mi1 = x

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.
```
ans = max(ans - mi1 + mx1, ans - mi2 + mx2, -1)
```
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.
```
return -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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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.

nums = [5, 3, 2, 4, 1]
k = 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:

nums.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:

ans = 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:

if ans % 2 == 0:  # 12 % 2 equals 0, so ans is even
    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:

mx1 = mx2 = -inf  # Initialize to negative infinity for comparison
mi1 = 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:

For the elements [1, 2], mx1 and mx2 would be updated:
mx1 = 1 (largest odd number)
mx2 = 2 (largest even number)

For the subsequence [3, 4, 5], mi1 and mi2 would be updated:
mi1 = 4 (smallest even number)
mi2 = 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:

We replace mi1 with mx1: ans becomes 12 - 4 + 1 = 9 (odd sum, not valid)
Or we replace mi2 with mx2: ans becomes 12 - 3 + 2 = 11 (also odd, not valid)
Since 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:

Since 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

1class Solution:
2    def largest_even_sum(self, nums: List[int], k: int) -> int:
3        # Sort the array to organize numbers for processing
4        nums.sort()
5
6        # Calculate the initial sum of the largest k numbers
7        largest_sum = sum(nums[-k:])
8
9        # If the sum is even, return it as the largest even sum
10        if largest_sum % 2 == 0:
11            return largest_sum
12      
13        # To find a candidate for swapping, initialize max odd and max even among the excluded numbers
14        max_odd_excluded = float('-inf')   # Represents negative infinity
15        max_even_excluded = float('-inf')  # Represents negative infinity
16
17        # Find the largest odd and even numbers in the excluded part of the sorted array
18        for num in nums[:-k]:
19            if num % 2:
20                max_odd_excluded = num
21            else:
22                max_even_excluded = num
23
24        # Initialize min odd and min even among the included largest k numbers
25        min_odd_included = float('inf')   # Represents positive infinity
26        min_even_included = float('inf')  # Represents positive infinity
27
28        # Find the smallest odd and even numbers in the included largest k numbers
29        for num in nums[-k:][::-1]:
30            if num % 2:
31                min_odd_included = num
32            else:
33                min_even_included = num
34
35        # Try to replace an included even number with an excluded odd number,
36        # or an included odd number with an excluded even number to make the sum even
37        sum_after_swap_1 = largest_sum - min_even_included + max_odd_excluded
38        sum_after_swap_2 = largest_sum - min_odd_included + max_even_excluded
39        largest_even_sum = max(sum_after_swap_1, sum_after_swap_2, -1)
40      
41        # Return -1 if we couldn't achieve an even sum; otherwise, return the largest even sum
42        return -1 if largest_even_sum % 2 else largest_even_sum
43

1import java.util.Arrays;
2
3class Solution {
4
5    // Method to calculate the largest even sum of k elements from the array nums
6    public long largestEvenSum(int[] nums, int k) {
7        // Sort the array in ascending order
8        Arrays.sort(nums);
9      
10        // Initialize answer to 0
11        long answer = 0;
12        int n = nums.length;
13      
14        // Sum the largest k elements
15        for (int i = 0; i < k; ++i) {
16            answer += nums[n - 1 - i];
17        }
18      
19        // Check if the sum is already even
20        if (answer % 2 == 0) {
21            return answer;
22        }
23      
24        // Define a large number to represent infinity
25        final int INFINITY = 1 << 29;
26      
27        // initialize variables to find the maximum odd and even
28        // numbers before the k largest items
29        int maxOddBeforeK = -INFINITY;
30        int maxEvenBeforeK = -INFINITY;
31      
32        // Find the maximum odd and even values before the k largest items
33        for (int i = 0; i < n - k; ++i) {
34            if (nums[i] % 2 == 1) { // If the number is odd
35                maxOddBeforeK = nums[i];
36            } else { // If the number is even
37                maxEvenBeforeK = nums[i];
38            }
39        }
40      
41        // initialize variables to find the minimum odd and even
42        // numbers from the k largest items
43        int minOddInK = INFINITY;
44        int minEvenInK = INFINITY;
45      
46        // Find the minimum odd and even values among the k largest items
47        for (int i = n - 1; i >= n - k; --i) {
48            if (nums[i] % 2 == 1) { // If the number is odd
49                minOddInK = nums[i];
50            } else { // If the number is even
51                minEvenInK = nums[i];
52            }
53        }
54      
55        // Calculate the potential answers by either:
56        // Replacing the minimum odd in K with the maximum even before K
57        // or
58        // Replacing the minimum even in K with the maximum odd before K
59        // Select the maximum from these potential answers
60        long replaceMinEvenWithMaxOdd = answer - minEvenInK + maxOddBeforeK;
61        long replaceMinOddWithMaxEven = answer - minOddInK + maxEvenBeforeK;
62        answer = Math.max(-1, Math.max(replaceMinEvenWithMaxOdd, replaceMinOddWithMaxEven));
63      
64        // Final check for even-ness and return the answer,
65        // otherwise return -1 if no even sum can be formed
66        return (answer % 2 == 0) ? answer : -1;
67    }
68}
69

1#include <algorithm> // For sorting
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7    // Function to return the largest even sum of 'k' numbers from the 'nums' vector
8    long long largestEvenSum(vector<int>& nums, int k) {
9        // Sort the vector in non-decreasing order
10        sort(nums.begin(), nums.end());
11
12        // Initial answer is set to zero
13        long long answer = 0;
14        // Number of elements in 'nums'
15        int n = nums.size();
16      
17        // Summing up the largest 'k' numbers
18        for (int i = 0; i < k; ++i) {
19            answer += nums[n - i - 1];
20        }
21
22        // If the sum is even, we can return the current sum
23        if (answer % 2 == 0) {
24            return answer;
25        }
26
27        // Initialize variables to find the smallest difference when swapping
28        const int INF = 1 << 29; // A large value representing infinity
29        int largestOddBelowK = -INF, largestEvenBelowK = -INF;
30
31        // Find the largest odd and even numbers below the top 'k' elements
32        for (int i = 0; i < n - k; ++i) {
33            if (nums[i] % 2) { // Odd
34                largestOddBelowK = nums[i];
35            } else { // Even
36                largestEvenBelowK = nums[i];
37            }
38        }
39
40        // Initialize the smallest odd and even elements within the top 'k'
41        int smallestOddWithinK = INF, smallestEvenWithinK = INF;
42
43        // Find the smallest odd and even numbers within the top 'k' elements
44        for (int i = n - 1; i >= n - k; --i) {
45            if (nums[i] % 2) { // Odd
46                smallestOddWithinK = nums[i];
47            } else { // Even
48                smallestEvenWithinK = nums[i];
49            }
50        }
51
52        // We want to swap an odd number with an even number or vice-versa
53        // so that the sum becomes even. We choose the swap which maximizes the sum.
54        // We do this by either swapping:
55        // 1. The smallest odd number within the top 'k' elements with
56        //    the largest even number below the top 'k' elements
57        // 2. The smallest even number within the top 'k' elements with
58        //    the largest odd number below the top 'k' elements
59        answer = max(answer - smallestOddWithinK + largestEvenBelowK,
60                     answer - smallestEvenWithinK + largestOddBelowK);
61
62        // Finally, we check if our new sum is positive and even;
63        // if not, return -1 to indicate no solution found
64        return (answer % 2 == 0 && answer >= 0) ? answer : -1;
65    }
66};
67

1// Function to sort an array in non-decreasing order
2function sortArray(nums: number[]): number[] {
3    return nums.sort((a, b) => a - b);
4}
5
6// Function to return the largest even sum of 'k' numbers from the 'nums' array
7function largestEvenSum(nums: number[], k: number): number {
8    // Sort the array in non-decreasing order
9    const sortedNums = sortArray(nums);
10
11    // Initial answer is set to zero
12    let answer: number = 0;
13    // Number of elements in 'nums'
14    const n = nums.length;
15  
16    // Summing up the largest 'k' numbers
17    for (let i = 0; i < k; ++i) {
18        answer += sortedNums[n - i - 1];
19    }
20
21    // If the current sum is even, return it
22    if (answer % 2 === 0) {
23        return answer;
24    }
25
26    // Initialize variables to find the smallest difference when swapping
27    const INF = Number.MAX_SAFE_INTEGER; // A large value representing infinity
28    let largestOddBelowK: number = -INF, largestEvenBelowK: number = -INF;
29
30    // Find the largest odd and even numbers below the top 'k' elements
31    for (let i = 0; i < n - k; ++i) {
32        if (sortedNums[i] % 2 === 1) { // Odd
33            largestOddBelowK = sortedNums[i];
34        } else { // Even
35            largestEvenBelowK = sortedNums[i];
36        }
37    }
38
39    // Initialize the smallest odd and even elements within the top 'k'
40    let smallestOddWithinK: number = INF, smallestEvenWithinK: number = INF;
41
42    // Find the smallest odd and even numbers within the top 'k' elements
43    for (let i = n - 1; i >= n - k; --i) {
44        if (sortedNums[i] % 2 === 1) { // Odd
45            smallestOddWithinK = sortedNums[i];
46        } else { // Even
47            smallestEvenWithinK = sortedNums[i];
48        }
49    }
50
51    // Attempt to swap an odd number with an even number (or vice versa) to make the sum even
52    // Choose the swap that maximizes the sum
53    answer = Math.max(
54        answer - smallestOddWithinK + largestEvenBelowK,
55        answer - smallestEvenWithinK + largestOddBelowK
56    );
57
58    // Check if the new sum is positive and even; if not, return -1 indicating no solution
59    return (answer % 2 === 0 && answer >= 0) ? answer : -1;
60}
61

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don’t know