Medium

Maximum Sum With At Most K Elements

LAB

Repeatedly take the largest value, add it to the score, then replace it with ceil(value/3). Return score after k operations.

EXAMPLES

Example 1

Input
{
  "nums": [
    10,
    10,
    10
  ],
  "k": 3
}

Output
30

FUNCTION SHAPE

nums: intArrayk: int→int

SOLUTION NOTE

We use a max heap (negate values), storing pairs of (-value, row_index). Greedily take the max value every time unless we've hit the limit for that row.

Reveal reference solution +

pythonREFERENCE

def maxSum(self, grid: List[List[int]], limits: List[int], k: int) -> int:
    m, n = len(grid), len(grid[0])
    heap = [(-grid[i][j], i) for i in range(m) for j in range(n)]
    heapify(heap)
    res = 0

    while k:
        val, row = heappop(heap)
        if limits[row] == 0:
            continue
        limits[row] -= 1
        res += -val
        k -= 1

    return res

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗