algoadvance

Leetcode 2656. Maximum Sum With Exactly K Elements

Problem Statement

You are given a 0-indexed integer array nums and an integer k. Your task is to find the maximum sum you can achieve by selecting exactly k elements from the array. If it is impossible to select k elements, return 0.

The sum should be calculated after adding 1 to each of the selected elements.

Clarifying Questions

  1. Can nums contain negative numbers?
    • Yes, nums can contain negative numbers.
  2. Can the number of elements in nums be smaller than k?
    • Yes, in such cases, the function should return 0 as it is impossible to select k elements.
  3. Do we have any constraints on the values within nums or the range of k?
    • There are no additional constraints provided beyond standard integer limits.

Strategy

  1. Check Feasibility: First, we need to check if the length of nums is smaller than k. If it is smaller, we return 0 since it’s not possible to select k elements.
  2. Sort the Array: Sort the array in descending order to easily pick the largest k elements.
  3. Sum the Largest Elements: Add the largest k elements from the sorted array after incrementing each by 1.

Pseudocode

  1. Check if nums.length < k. If true, return 0.
  2. Sort nums in descending order.
  3. Initialize maxSum to 0.
  4. Iterate over the first k elements of the sorted array and add element + 1 to maxSum.
  5. Return maxSum.

Code

import java.util.Arrays;
import java.util.Collections;

public class MaximumSumWithKElements {
    public int maxSum(int[] nums, int k) {
        int n = nums.length;
        if (n < k) {
            return 0;  // Impossible to select k elements
        }

        // Use boxed integers to allow sorting with Collections.reverseOrder()
        Integer[] numsBoxed = Arrays.stream(nums).boxed().toArray(Integer[]::new);
        Arrays.sort(numsBoxed, Collections.reverseOrder());

        int maxSum = 0;
        for (int i = 0; i < k; i++) {
            maxSum += numsBoxed[i] + 1;  // Add 1 to each selected element
        }

        return maxSum;
    }

    public static void main(String[] args) {
        MaximumSumWithKElements solution = new MaximumSumWithKElements();
        int[] nums = {1, 2, 3, 4, 5};
        int k = 3;
        System.out.println(solution.maxSum(nums, k));  // Output: 15 (5+1 + 4+1 + 3+1)
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI