Append K Integers With Minimal Sum
MedPrompt
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.
Return the sum of the k integers appended to nums.
Example 1:
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.
The resulting sum of nums is 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70, which is the minimum.
The sum of the two integers appended is 2 + 3 = 5, so we return 5.Example 2:
Input: nums = [5,6], k = 6
Output: 25
Explanation: The six unique positive integers that do not appear in nums which we append are 1, 2, 3, 4, 7, and 8.
The resulting sum of nums is 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36, which is the minimum.
The sum of the six integers appended is 1 + 2 + 3 + 4 + 7 + 8 = 25, so we return 25.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= 108
Approaches
3 approaches with complexity analysis and trade-offs.
This approach simulates the process directly. We want to find the k smallest positive integers not present in nums. We can use a HashSet for efficient lookups of numbers in nums. We then iterate upwards from 1, checking each number. If a number is not in the set, we add it to our sum and decrement k. We continue this until we have found k numbers.
Algorithm
- Create a
HashSetand populate it with all the numbers from the input arraynums. This allows for average O(1) time complexity for checking if a number exists. - Initialize a
longvariablesumto 0 to store the sum of the appended integers, and an integercountto 0. - Initialize a
longvariablecurrentNumto 1. This will be the candidate integer to append. - Start a loop that continues as long as
count < k. - Inside the loop, check if
currentNumis present in theHashSet. - If
currentNumis not in the set, it's a valid number to append. AddcurrentNumtosumand incrementcount. - Increment
currentNumin every iteration to check the next positive integer. - Once the loop finishes (i.e.,
countreachesk), return the totalsum.
Walkthrough
The core idea is to iterate through positive integers starting from 1 and, for each integer, check if it's already in the nums array. To make this check efficient, we first store all elements of nums in a HashSet. We maintain a running sum and a count of numbers we've decided to append. We keep checking and adding numbers until we have found k of them.
import java.util.HashSet;import java.util.Set; class Solution { public long minimalKSum(int[] nums, int k) { Set<Integer> numSet = new HashSet<>(); for (int num : nums) { numSet.add(num); } long sum = 0; int count = 0; long currentNum = 1; while (count < k) { if (!numSet.contains((int)currentNum)) { sum += currentNum; count++; } currentNum++; } return sum; }}Complexity
Time
O(n + k), where n is the length of `nums`. It takes O(n) to build the set. The `while` loop might run up to `n + k` times in the worst-case scenario (e.g., if `nums` contains `1, 2, ..., n`). Given `k` can be up to `10^8`, this will likely result in a Time Limit Exceeded (TLE) error.
Space
O(n), where n is the number of elements in `nums`. This space is used to store the `HashSet`.
Trade-offs
Pros
Simple to understand and implement.
Cons
Highly inefficient for large values of
k, as the main loop's iterations depend onk.
A more efficient approach is to sort the nums array first. By sorting, we can easily identify consecutive blocks of numbers (gaps) that are missing. We can then calculate the sum of numbers in these gaps efficiently using the arithmetic series sum formula, avoiding a one-by-one check up to k.
Algorithm
- Sort the
numsarray in non-decreasing order. - Initialize a
longvariablesumto 0, and alongvariablenextMissingto 1 (representing the next smallest positive integer we are looking for). - Iterate through the sorted
numsarray, skipping duplicates. - For each unique
numinnums:- If
num > nextMissing, there is a gap of missing numbers betweennextMissingandnum - 1. - Calculate how many numbers we can add from this gap, which is
min(k, num - nextMissing). - Calculate the sum of these numbers using the arithmetic series sum formula and add it to the total
sum. - Decrement
kby the count of numbers added. - If
kbecomes 0, break the loop.
- If
- Update
nextMissingto benum + 1. - After the loop, if
kis still positive, add the sum of the nextkintegers starting fromnextMissing. - Return the final
sum.
Walkthrough
Instead of checking every number from 1 upwards, we can leverage the structure of the input. By sorting nums, we can process the existing numbers in order. We keep track of the next positive integer we expect to add, let's call it nextMissing (initially 1). As we iterate through the sorted nums, if we encounter a number num that is greater than nextMissing, we know all integers in the range [nextMissing, num - 1] are available. We can add up to k of these numbers, calculate their sum in O(1) using the arithmetic series formula, and update k and nextMissing accordingly. If k is not yet zero after iterating through all of nums, we add the remaining required numbers, which will be consecutive integers starting from the final nextMissing value.
import java.util.Arrays; class Solution { public long minimalKSum(int[] nums, int k) { Arrays.sort(nums); long sum = 0; long k_long = k; long nextMissing = 1; for (int num : nums) { if (k_long == 0) { break; } // Skip numbers smaller than our current search point or duplicates if (num < nextMissing) { continue; } if (num == nextMissing) { nextMissing++; continue; } // Gap found: from nextMissing to num - 1 long countInGap = num - nextMissing; long canAdd = Math.min(k_long, countInGap); long start = nextMissing; long end = nextMissing + canAdd - 1; sum += (end + start) * canAdd / 2; k_long -= canAdd; nextMissing = (long)num + 1; } // If k is still not zero, add remaining numbers if (k_long > 0) { long start = nextMissing; long end = nextMissing + k_long - 1; sum += (end + start) * k_long / 2; } return sum; }}Complexity
Time
O(n log n), where n is the length of `nums`. The dominant operation is sorting the array. The subsequent loop runs in O(n).
Space
O(log n) or O(n), depending on the space complexity of the sorting algorithm used by the language's standard library.
Trade-offs
Pros
Significantly more efficient than the brute-force approach, especially for large
k.Avoids iterating up to
kby calculating sums of missing number ranges.
Cons
The sorting step has a time complexity of O(n log n), which is not as optimal as a linear time solution.
This is the most optimal approach. The idea is to assume we are adding the first k positive integers (1, 2, ..., k) and calculate their sum. Then, we correct this sum. For any number num from the input array nums that is less than or equal to k, we must have wrongly included it. So, we subtract num from our sum and add the next available integer greater than k that is not in nums.
Algorithm
- Calculate the ideal sum of the first
kpositive integers:sum = (long)k * (k + 1) / 2. - Create a
HashSetof the unique elements fromnumsfor O(1) average time lookups. - Initialize
nextAvailable = k + 1. This is the first candidate for a replacement number. - Iterate through the unique numbers (
num) in theHashSet. - If
num <= k, it conflicts with our initial assumption.- Subtract
numfromsum. - Find the next available replacement:
whiletheHashSetcontainsnextAvailable, incrementnextAvailable. - Add the found
nextAvailabletosum. - Increment
nextAvailableto prepare for the next potential replacement.
- Subtract
- Return the final
sum.
Walkthrough
This approach starts with a powerful assumption: the k integers to be added are 1, 2, ..., k. The sum is easily calculated as k*(k+1)/2. This assumption is only wrong if some of these numbers (from 1 to k) are already present in nums. We can identify these conflicting numbers by putting all nums into a HashSet. We then iterate through the unique numbers in nums. If a number num is less than or equal to k, we must remove it from our sum and add a substitute. The smallest possible substitute is the smallest integer greater than k that is not in nums. We find this by starting a search from k+1 and incrementing until we find a number not in the HashSet.
import java.util.HashSet;import java.util.Set; class Solution { public long minimalKSum(int[] nums, int k) { long sum = (long)k * (k + 1) / 2; Set<Integer> uniqueNums = new HashSet<>(); for (int num : nums) { uniqueNums.add(num); } long nextAvailable = k + 1; for (int num : uniqueNums) { if (num <= k) { sum -= num; while (uniqueNums.contains((int)nextAvailable)) { nextAvailable++; } sum += nextAvailable; nextAvailable++; } } return sum; }}Complexity
Time
O(n), where n is the length of `nums`. Building the `HashSet` takes O(n). The loop iterates through unique elements (at most n). The inner `while` loop's total work is bounded because `nextAvailable` only ever increases, making the overall complexity linear.
Space
O(n), where n is the number of unique elements in `nums`, for storing the `HashSet`.
Trade-offs
Pros
Achieves the best time complexity of O(n).
Conceptually elegant by starting with an ideal sum and making corrections.
Cons
Uses O(n) extra space for the HashSet, which might be a concern for very large inputs with strict memory limits.
Solutions
Solution
class Solution {public long minimalKSum(int[] nums, int k) { int[] arr = new int[nums.length + 2]; arr[arr.length - 1] = (int)2 e9; for (int i = 0; i < nums.length; ++i) { arr[i + 1] = nums[i]; } Arrays.sort(arr); long ans = 0; for (int i = 1; i < arr.length; ++i) { int a = arr[i - 1], b = arr[i]; int n = Math.min(k, b - a - 1); if (n <= 0) { continue; } k -= n; ans += (long)(a + 1 + a + n) * n / 2; if (k == 0) { break; } } return ans; }}class Solution: def minimalKSum(self, nums: List[int], k: int) -> int: nums . append(0) nums . append(2 * 10 ** 9) nums . sort() ans = 0 for a, b in pairwise(nums): n = min(k, b - a - 1) if n <= 0: continue k -= n ans += (a + 1 + a + n) * n // 2 if k == 0: break return ansclass Solution {public: long long minimalKSum(vector<int> &nums, int k) { nums.push_back(0); nums.push_back(2e9); sort(nums.begin(), nums.end()); long long ans = 0; for (int i = 1; i < nums.size(); ++i) { int a = nums[i - 1], b = nums[i]; int n = min(k, b - a - 1); if (n <= 0) continue; k -= n; ans += 1ll * (a + 1 + a + n) * n / 2; if (k == 0) break; } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.