Append K Integers With Minimal Sum — LeetCode 2195 Python Solution

The problem

You are given an integer array nums and an integer k. Append k unique positive integers that do not appear in nums to nums such that the resulting total sum is minimum.

Example

Input

nums = [1,4,25,10,25], k = 2

Output

5

Explanation

The two unique positive integers that do not appear in nums which we append are 2 and 3.

Python solution

class Solution:
    def minimalKSum(self, nums: List[int], k: int) -> int:
        nums.extend([0, 2 * 10**9])
        nums.sort()
        ans = 0
        for a, b in pairwise(nums):
            m = max(0, min(k, b - a - 1))
            ans += (a + 1 + a + m) * m // 2
            k -= m
        return ans

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2195. Append K Integers With Minimal Sum is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems