LeetCode 2195 - Append K Integers With Minimal Sum

The problem asks us to append k unique positive integers to an existing array nums such that none of the integers we add are already in nums, and the sum of the numbers we append is minimized.

leetcodemediumarraymathgreedysorting

LeetCode Problem 2195

Difficulty: 🟡 Medium
Topics: Array, Math, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to append k unique positive integers to an existing array nums such that none of the integers we add are already in nums, and the sum of the numbers we append is minimized. In other words, we want to pick the smallest k positive integers that are missing from nums. The input nums is an array of positive integers up to 10^9, and k can be as large as 10^8, which means a naive solution that checks every integer sequentially will be far too slow. The output is the sum of the k integers that we append. Edge cases include when nums already contains consecutive numbers starting from 1, or when nums has very large gaps between numbers.

Approaches

A brute-force approach would be to iterate through all positive integers starting from 1, skipping numbers already in nums, until we have appended k numbers. This works in principle, but it is far too slow when nums has up to 10^5 elements and k is up to 10^8, as iterating and checking membership would be very costly.

The optimal approach relies on sorting nums and using a greedy method. We sort nums and iterate through the numbers, keeping track of the smallest missing positive integers before each number. For each gap between consecutive numbers in the sorted array, we can compute how many numbers are missing in the gap and add them efficiently using the arithmetic sum formula. If there are still numbers to append after processing all elements in nums, we append the smallest missing numbers after the largest number in nums.

Approach Time Complexity Space Complexity Notes
Brute Force O(max(n, k) * n) O(n) Iterate through integers from 1 upwards, checking membership in nums
Optimal O(n log n) O(n) Sort nums and greedily add missing numbers using arithmetic sum formula

Algorithm Walkthrough

  1. Sort nums and remove duplicates to simplify processing, because duplicates do not contribute additional constraints for minimal missing numbers.
  2. Initialize a variable prev to 0 to track the last number considered, and total_sum to 0 to accumulate the sum of appended numbers.
  3. Iterate through each number num in the sorted nums.
  4. For each number, calculate the number of missing numbers between prev + 1 and num - 1. Let this count be gap_count.
  5. If gap_count is less than or equal to the remaining k, append all numbers in the gap to the sum using the arithmetic series formula. Subtract gap_count from k.
  6. If gap_count exceeds the remaining k, append only the first k numbers in the gap using the arithmetic series formula, then break, as we have appended k numbers.
  7. After iterating through all elements, if k is still positive, append the next k consecutive numbers starting from the last element plus one, again using the arithmetic series formula.
  8. Return the total sum of appended numbers.

Why it works: The algorithm guarantees minimal sum because at each step it appends the smallest missing numbers available, filling gaps between existing numbers first and continuing sequentially after the largest number. Using arithmetic sum ensures we calculate the sum efficiently without iterating explicitly through all numbers.

Python Solution

from typing import List

class Solution:
    def minimalKSum(self, nums: List[int], k: int) -> int:
        nums = sorted(set(nums))
        total_sum = 0
        prev = 0
        
        for num in nums:
            gap_count = num - prev - 1
            if gap_count > 0:
                if gap_count <= k:
                    total_sum += (prev + 1 + num - 1) * gap_count // 2
                    k -= gap_count
                else:
                    total_sum += (prev + 1 + prev + k) * k // 2
                    k = 0
                    break
            prev = num
        
        if k > 0:
            total_sum += (prev + 1 + prev + k) * k // 2
        
        return total_sum

The Python implementation first removes duplicates and sorts the array. It tracks missing numbers between consecutive elements, using the arithmetic sum formula to efficiently calculate the sum of missing numbers. It updates k as numbers are appended. Any remaining k numbers are appended after the largest element.

Go Solution

import "sort"

func minimalKSum(nums []int, k int) int64 {
    numMap := make(map[int]struct{})
    for _, num := range nums {
        numMap[num] = struct{}{}
    }
    
    uniqueNums := make([]int, 0, len(numMap))
    for num := range numMap {
        uniqueNums = append(uniqueNums, num)
    }
    
    sort.Ints(uniqueNums)
    
    var totalSum int64 = 0
    prev := 0
    
    for _, num := range uniqueNums {
        gapCount := num - prev - 1
        if gapCount > 0 {
            if gapCount <= k {
                totalSum += int64(prev+1+num-1) * int64(gapCount) / 2
                k -= gapCount
            } else {
                totalSum += int64(prev+1+prev+k) * int64(k) / 2
                k = 0
                break
            }
        }
        prev = num
    }
    
    if k > 0 {
        totalSum += int64(prev+1+prev+k) * int64(k) / 2
    }
    
    return totalSum
}

In Go, we explicitly handle duplicates using a map and sort the unique numbers. We use int64 for totalSum to avoid integer overflow since the sum can be large. The logic mirrors the Python version, iterating through sorted numbers and using arithmetic sums.

Worked Examples

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

Sorted unique nums: [1, 4, 10, 25]

prev = 0, total_sum = 0

Iteration num gap_count k total_sum
1 1 0 2 0
2 4 2 2 2+3=5

k = 0, done. Output = 5

Example 2: nums = [5,6], k = 6

Sorted unique nums: [5, 6]

prev = 0, total_sum = 0

Iteration num gap_count k total_sum
1 5 4 6 1+2+3+4=10
2 6 0 2 10

Remaining k=2, append 7,8: sum += 15, total_sum = 25

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting the unique numbers dominates the runtime
Space O(n) Storing unique numbers in a set/array

Sorting ensures we can efficiently find gaps, and using arithmetic sum prevents iterating through large ranges.

Test Cases

# Provided examples
assert Solution().minimalKSum([1,4,25,10,25], 2) == 5  # minimal sum of missing 2 numbers
assert Solution().minimalKSum([5,6], 6) == 25         # append first 6 missing positive numbers
assert Solution().minimalKSum([1,2,2,2], 3) == 9      # append 3 missing numbers: 3+4+5=12

# Edge cases
assert Solution().minimalKSum([1,2,3], 1) == 4        # append next missing number after consecutive sequence
assert Solution().minimalKSum([1000000000], 1) == 1  # first missing positive number is 1
assert Solution().minimalKSum([], 5) == 15           # append first 5 positive integers 1+2+3+4+5=15
Test Why
[1,4,25,10,25], 2 Normal case with gaps
[5,6], 6 Case with multiple missing numbers and small nums
[1,2,2,2], 3 Duplicates in input
[1,2,3], 1 Consecutive numbers starting from 1
[1000000000], 1 Very large number, small k
[], 5 Empty array edge case

Edge Cases

The first edge case is when nums contains consecutive numbers starting from 1. The algorithm must correctly append numbers after the largest number to satisfy k. This is handled by tracking prev and adding remaining k numbers after the last element.

The second edge case occurs when nums contains very large numbers but k is small. We need to correctly append the smallest missing numbers starting from 1. Using prev=0 initially ensures that the arithmetic