algoadvance

Leetcode 2600. K Items With the Maximum Sum

Problem Statement

You are given three integers numOnes, numZeros, and numNegOnes. You are given an array consisting of numOnes ones, numZeros zeros, and numNegOnes negative ones.

You need to pick exactly k items from this array such that their sum is maximized.

Return the maximized sum.

Clarifying Questions

Strategy

  1. Prioritize Ones: Since 1 contributes positively to the sum, always pick as many 1s as possible first.
  2. Include Zeros: If there are leftover spots after picking all 1s, fill with 0s (which do not change the sum).
  3. Include Negative Ones: If there are still spots remaining, fill with -1s as a last resort (which will decrease the sum).

The goal is to maximize the sum by leveraging the positive values first.

Solution Code

public class Solution {
    public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        int sum = 0;

        // 1. Pick ones
        if (k > 0 && numOnes > 0) {
            int pickOnes = Math.min(k, numOnes);
            sum += pickOnes;
            k -= pickOnes;
        }
        
        // 2. Pick zeros (automatically included, no change in sum)
        if (k > 0 && numZeros > 0) {
            int pickZeros = Math.min(k, numZeros);
            // sum does not change with zeros
            k -= pickZeros;
        }
        
        // 3. Pick negative ones
        if (k > 0 && numNegOnes > 0) {
            int pickNegOnes = Math.min(k, numNegOnes);
            sum -= pickNegOnes;
            k -= pickNegOnes;
        }

        return sum;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.kItemsWithMaximumSum(3, 2, 0, 2)); // Output: 2
        System.out.println(sol.kItemsWithMaximumSum(3, 2, 0, 4)); // Output: 3
        System.out.println(sol.kItemsWithMaximumSum(3, 2, 5, 8)); // Output: 0
    }
}

Time Complexity

The time complexity of this solution is O(1) because we are performing a constant number of operations regardless of the input sizes. There are no loops dependent on the size of the inputs.

This guarantees an extremely efficient solution suitable for constraint limits given in the problem statement.

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