2600. K Items With the Maximum Sum Solution

The problem

There is a bag that consists of items, each item has a number 1, 0, or -1 written on it.

You are given four non-negative integers numOnes, numZeros, numNegOnes, and k.

The bag initially contains:

numOnes items with 1s written on them.
numZeroes items with 0s written on them.
numNegOnes items with -1s written on them.

We want to pick exactly k items among the available items. Return the maximum possible sum of numbers written on the items.

Example 1:

Input: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
Output: 2
Explanation: We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 2 items with 1 written on them and get a sum in a total of 2.
It can be proven that 2 is the maximum possible sum.

Example 2:

Input: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
Output: 3
Explanation: We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 3 items with 1 written on them, and 1 item with 0 written on it, and get a sum in a total of 3.
It can be proven that 3 is the maximum possible sum.

Constraints:

0 <= numOnes, numZeros, numNegOnes <= 50
0 <= k <= numOnes + numZeros + numNegOnes

Approach overview

Problem Overview: You are given counts of items with values 1, 0, and -1. You must pick exactly k items to maximize the total sum. Since the values are fixed and limited to three types, the goal is simply choosing the best combination in the right order.

Approach 1: Simulation Approach (O(k) time, O(1) space)

This method simulates the selection process step by step. Always pick from the most valuable items first: 1, then 0, and finally -1. Iterate up to k selections, decreasing the available count of each category while adding its value to the running sum. This approach mirrors how you would manually choose items and works well when explaining the logic during interviews.

The algorithm checks if a 1 is still available and selects it because it increases the sum. When no ones remain, it chooses 0 since it keeps the sum unchanged. Only when both 1 and 0 are exhausted do you select -1. The logic follows a straightforward greedy preference but performs explicit iteration for each pick.

Approach 2: Greedy Approach (O(1) time, O(1) space)

The optimal solution uses a direct greedy calculation instead of simulating each pick. Since 1 > 0 > -1, the maximum sum is obtained by taking as many 1s as possible first. If k is less than or equal to the count of ones, the result is simply k. Otherwise, take all ones and reduce k accordingly.

Next, consume zeros if they exist. They do not change the sum but help reach the required k. Only when both ones and zeros are exhausted do negative values contribute to the result. The final adjustment subtracts the remaining selections because each -1 decreases the sum by one.

This approach works because the value set is small and ordered. A greedy choice is always optimal since taking a higher value earlier never blocks a better future choice. The reasoning aligns with common patterns in greedy algorithms and simple counting problems often seen in math-based interview questions.

Recommended for interviews: The greedy approach is what interviewers expect. It reduces the problem to simple arithmetic and runs in constant time. Showing the simulation first demonstrates understanding of the selection order, but deriving the direct greedy formula shows stronger problem-solving skills.

Approach 1: Greedy Approach

This approach is based on a greedy algorithm that maximizes the sum by prioritizing the selection of items with '1' over '0' and '-1'.

Steps:

First, select all '1' items, up to a maximum of 'k'.
If there's a remainder of 'k' after '1's, fill the remaining with '0's from the total available.
If '0's are exhausted and there is still a remainder, use '-1's for the rest.

Python

def max_sum(numOnes, numZeros, numNegOnes, k):
    if k <= numOnes:
        return k
    elif k <= numOnes + numZeros:
        return numOnes
    else:
        return numOnes - (k - numOnes - numZeros)

numOnes, numZeros, numNegOnes, k = 3, 2, 0, 4
print(max_sum(numOnes, numZeros, numNegOnes, k))

Java

public class Solution {
    public static int maxSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (k <= numOnes) {
            return k;
        } else if (k <= numOnes + numZeros) {
            return numOnes;
        } else {
            return numOnes - (k - numOnes - numZeros);
        }
    }

    public static void main(String[] args) {
        int numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4;
        System.out.println(maxSum(numOnes, numZeros, numNegOnes, k));
    }
}

C++

#include <iostream>

int maxSum(int numOnes, int numZeros, int numNegOnes, int k) {
    if (k <= numOnes) {
        return k;
    } else if (k <= numOnes + numZeros) {
        return numOnes;
    } else {
        return numOnes - (k - numOnes - numZeros);
    }
}

int main() {
    int numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4;
    std::cout << maxSum(numOnes, numZeros, numNegOnes, k) << std::endl;
    return 0;
}

JavaScript

function maxSum(numOnes, numZeros, numNegOnes, k) {
    if (k <= numOnes) {
        return k;
    } else if (k <= numOnes + numZeros) {
        return numOnes;
    } else {
        return numOnes - (k - numOnes - numZeros);
    }
}

let numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4;
console.log(maxSum(numOnes, numZeros, numNegOnes, k));

#include <stdio.h>

int maxSum(int numOnes, int numZeros, int numNegOnes, int k) {
    if (k <= numOnes) {
        return k;
    } else if (k <= numOnes + numZeros) {
        return numOnes;
    } else {
        return numOnes - (k - numOnes - numZeros);
    }
}

int main() {
    int numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4;
    printf("%d\n", maxSum(numOnes, numZeros, numNegOnes, k));
    return 0;
}

using System;

public class Solution {
    public static int MaxSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (k <= numOnes) {
            return k;
        } else if (k <= numOnes + numZeros) {
            return numOnes;
        } else {
            return numOnes - (k - numOnes - numZeros);
        }
    }

    public static void Main() {
        int numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4;
        Console.WriteLine(MaxSum(numOnes, numZeros, numNegOnes, k));
    }
}

A simple function in Python that uses conditionals to foresee if it can use '1' or will need '-1' to fill in after using all possible '1's.

Complexity

Time Complexity: O(1) based on constant-time logic checks.
Space Complexity: O(1) since it's a function with no extra data structures.

Try this approach in the editor

Approach 2: Simulation Approach

This approach uses simulation by creating an array representation of the items and sorts them. It then picks the first 'k' elements to maximize the sum.

Steps:

Create an array containing 'numOnes', 'numZeros', and 'numNegOnes'.
Sort the array in descending order.
Select the first 'k' items and compute their sum.

Python

def max_sum(numOnes, numZeros, numNegOnes, k):
    items = [1] * numOnes + [0] * numZeros + [-1] * numNegOnes
    items.sort(reverse=True)
    return sum(items[:k])

numOnes, numZeros, numNegOnes, k = 3, 2, 0, 4
print(max_sum(numOnes, numZeros, numNegOnes, k))

Java

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    public static int maxSum(int numOnes, int numZeros, int numNegOnes, int k) {
        ArrayList<Integer> items = new ArrayList<>();
        for (int i = 0; i < numOnes; i++) items.add(1);
        for (int i = 0; i < numZeros; i++) items.add(0);
        for (int i = 0; i < numNegOnes; i++) items.add(-1);

        Collections.sort(items, Collections.reverseOrder());

        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += items.get(i);
        }
        return sum;
    }

    public static void main(String[] args) {
        int numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4;
        System.out.println(maxSum(numOnes, numZeros, numNegOnes, k));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int maxSum(int numOnes, int numZeros, int numNegOnes, int k) {
    std::vector<int> items;
    items.insert(items.end(), numOnes, 1);
    items.insert(items.end(), numZeros, 0);
    items.insert(items.end(), numNegOnes, -1);

    std::sort(items.begin(), items.end(), std::greater<int>());

    int sum = 0;
    for (int i = 0; i < k; ++i) {
        sum += items[i];
    }
    return sum;
}

int main() {
    int numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4;
    std::cout << maxSum(numOnes, numZeros, numNegOnes, k) << std::endl;
    return 0;
}

JavaScript

function maxSum(numOnes, numZeros, numNegOnes, k) {
    let items = Array(numOnes).fill(1).concat(Array(numZeros).fill(0), Array(numNegOnes).fill(-1));
    items.sort((a, b) => b - a);
    return items.slice(0, k).reduce((a, b) => a + b, 0);
}

let numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4;
console.log(maxSum(numOnes, numZeros, numNegOnes, k));

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)b - *(int *)a);
}

int maxSum(int numOnes, int numZeros, int numNegOnes, int k) {
    int totalItems = numOnes + numZeros + numNegOnes;
    int items[totalItems];
    for (int i = 0; i < numOnes; ++i) {
        items[i] = 1;
    }
    for (int i = 0; i < numZeros; ++i) {
        items[numOnes + i] = 0;
    }
    for (int i = 0; i < numNegOnes; ++i) {
        items[numOnes + numZeros + i] = -1;
    }

    qsort(items, totalItems, sizeof(int), compare);

    int sum = 0;
    for (int i = 0; i < k; ++i) {
        sum += items[i];
    }
    return sum;
}

int main() {
    int numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4;
    printf("%d\n", maxSum(numOnes, numZeros, numNegOnes, k));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public static int MaxSum(int numOnes, int numZeros, int numNegOnes, int k) {
        List<int> items = new List<int>();
        for (int i = 0; i < numOnes; i++) items.Add(1);
        for (int i = 0; i < numZeros; i++) items.Add(0);
        for (int i = 0; i < numNegOnes; i++) items.Add(-1);

        items.Sort((a, b) => b.CompareTo(a));

        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += items[i];
        }
        return sum;
    }

    public static void Main() {
        int numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4;
        Console.WriteLine(MaxSum(numOnes, numZeros, numNegOnes, k));
    }
}

In Python, we create a list of items, sort it, and sum the top 'k' items to achieve the maximum sum. It demonstrates the power of Python's list manipulation and sorting capabilities.

Complexity

Time Complexity: O(n log n) from the sorting process.
Space Complexity: O(n), necessitated by the list representation.

Try this approach in the editor

Approach 3: Greedy

According to the problem description, we should take as many items marked as 1 as possible, then take items marked as 0, and finally take items marked as -1.

Thus:

If the number of items marked as 1 in the bag is greater than or equal to k, we take k items, and the sum of the numbers is k.
If the number of items marked as 1 is less than k, we take numOnes items, resulting in a sum of numOnes. If the number of items marked as 0 is greater than or equal to k - numOnes, we take k - numOnes more items, keeping the sum at numOnes.
Otherwise, we take k - numOnes - numZeros items from those marked as -1, resulting in a sum of numOnes - (k - numOnes - numZeros).

The time complexity is O(1), and the space complexity is O(1).

TypeScript

function kItemsWithMaximumSum(
    numOnes: number,
    numZeros: number,
    numNegOnes: number,
    k: number,
): number {
    if (numOnes >= k) {
        return k;
    }
    if (numZeros >= k - numOnes) {
        return numOnes;
    }
    return numOnes - (k - numOnes - numZeros);
}

func kItemsWithMaximumSum(numOnes int, numZeros int, numNegOnes int, k int) int {
	if numOnes >= k {
		return k
	}
	if numZeros >= k-numOnes {
		return numOnes
	}
	return numOnes - (k - numOnes - numZeros)
}

Rust

impl Solution {
    pub fn k_items_with_maximum_sum(
        num_ones: i32,
        num_zeros: i32,
        num_neg_ones: i32,
        k: i32,
    ) -> i32 {
        if num_ones > k {
            return k;
        }

        if num_ones + num_zeros > k {
            return num_ones;
        }

        num_ones - (k - num_ones - num_zeros)
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach	Time Complexity: O(1) based on constant-time logic checks. Space Complexity: O(1) since it's a function with no extra data structures.
Simulation Approach	Time Complexity: O(n log n) from the sorting process. Space Complexity: O(n), necessitated by the list representation.
Greedy	–

Complexity analysis

Approach	Time	Space	When to Use
Simulation	O(k)	O(1)	Useful for explaining the step-by-step selection logic or when teaching greedy reasoning.
Greedy Calculation	O(1)	O(1)	Best for interviews and production code. Direct arithmetic avoids iteration.

Frequently asked questions

Is K Items With the Maximum Sum easy or hard?

K Items With the Maximum Sum is classified as an Easy problem with about a 60% acceptance rate. The challenge lies in recognizing that a greedy selection order (1, then 0, then -1) guarantees the optimal sum.

K Items With the Maximum Sum Python/Java solution

In Python or Java, the greedy solution calculates how many 1s can be taken, adjusts k, skips zeros if available, and subtracts the remaining picks if -1 values are required. The implementation is a few lines of arithmetic and conditional checks.

How to solve K Items With the Maximum Sum in O(1)?

Take the minimum of k and the number of items with value 1 and add that to the result. Reduce k accordingly. If selections remain, consume zeros which do not change the sum. Any remaining picks must be -1 values, so subtract the remaining count from the total.

What is the best approach for K Items With the Maximum Sum?

The greedy approach is the optimal solution. Always select items with value 1 first, then 0, and finally -1 until k selections are made. Because the values are strictly ordered, this greedy strategy always produces the maximum possible sum in O(1) time and O(1) space.

Is K Items With the Maximum Sum asked at Google/Amazon/Meta?

Problems of this style frequently appear in interviews at large tech companies because they test greedy reasoning and edge case handling. While this exact question is categorized as Easy, similar counting and greedy optimization problems are common in screening rounds.

What data structure is used in K Items With the Maximum Sum?

No complex data structure is required. The problem only relies on integer counters representing the number of 1s, 0s, and -1s. The solution is based on greedy ordering rather than arrays, hash maps, or trees.

What is the time complexity of K Items With the Maximum Sum?

The optimal greedy solution runs in O(1) time and uses O(1) space because the result can be computed directly using counts of 1s, 0s, and -1s. A simple simulation alternative takes O(k) time since it iterates for each selection.

K Items With the Maximum Sum solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Simulation Approach

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

K Items With the Maximum Sum solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Simulation Approach

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems