Append K Integers With Minimal Sum solution and explanation
Google
4 more videos on this problem
2195. Append K Integers With Minimal Sum || Leetcode Weekly Contest 283 || Leetcode 2195Bro Coders · 8:35 · 3K views
2195. Append K Integers With Minimal Sum (Leetcode Medium)Programming Live with Larry · 23:58 · 608 views
Append K Integers With Minimal SumNot A Boring Developer · 9:45 · 540 views
LeetCode 2195: Append K Integers With Minimal SumAlitaCode · 26:08 · 14 views
Leetcode : Append K Integer With Minimal SumCoding For Dummies · 18:06 · 331 views
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.
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
Approach overview
Problem Overview: You are given an integer array nums and an integer k. You must append k positive integers that do not already exist in the array such that the total sum of the appended numbers is as small as possible. The challenge is choosing the smallest missing integers efficiently without repeatedly checking every value.
Approach 1: Set-Based Unique Identifier (O(n + k) time, O(n) space)
Insert all elements of nums into a hash set for constant-time membership checks. Start from integer 1 and keep incrementing. If the number is not present in the set, append it and add it to the running sum. Continue until you append k integers. This approach relies on fast hash lookups and sequential iteration. It works well when k is small, but if k is very large you may scan many integers before finishing. The method mainly uses a hash set from Array data and constant-time membership checks.
Approach 2: Greedy Approach with Sorting (O(n log n) time, O(1) extra space)
Sort the array first, then greedily fill the gaps between numbers. Maintain a pointer cur representing the smallest candidate integer you can append. When you encounter a number num in the sorted array that is greater than cur, the range [cur, num - 1] contains missing integers. Append as many as possible from this range without exceeding k. Instead of adding numbers one by one, compute their sum using the arithmetic series formula (first + last) * count / 2. This reduces repeated work and keeps the algorithm efficient. After processing the array, if k values are still needed, append the next sequence starting from cur.
The key insight is recognizing that the smallest missing numbers always produce the minimal sum. Sorting helps you detect missing ranges quickly, and the arithmetic progression formula from Math avoids iterating over every integer individually. This makes the solution clean and scalable even when k is large.
This technique combines Greedy reasoning with Sorting. The greedy decision is always selecting the smallest available integers first because any larger choice would increase the sum.
Recommended for interviews: The greedy sorting approach is the expected solution. It demonstrates that you recognize the "smallest missing numbers" pattern and optimize summation using arithmetic series. A brute-force or set-based scan shows basic problem understanding, but the sorted greedy solution shows stronger algorithmic thinking and typically impresses interviewers.
Approach 1: Greedy Approach with Sorting
Sort the array to streamline the process of identifying missing positive integers. Begin appending integers starting from 1 and continue to check the sorted array to skip numbers already present. This ensures the smallest integers are appended.
def appendKIntegersWithMinimalSum(nums, k):
nums.sort()
sum_ = 0
current = 1
index = 0
while k > 0:
if index < len(nums) and nums[index] == current:
index += 1
else:
sum_ += current
k -= 1
current += 1
return sum_
# Example Usage
nums = [1, 4, 25, 10, 25]
k = 2
print(appendKIntegersWithMinimalSum(nums, k)) # Outputs 5import java.util.Arrays;
public class Main {
public static long appendKIntegersWithMinimalSum(int[] nums, int k) {
Arrays.sort(nums);
long sum = 0;
int current = 1;
int index = 0;
while (k > 0) {
if (index < nums.length && nums[index] == current) {
index++;
} else {
sum += current;
k--;
}
current++;
}
return sum;
}
public static void main(String[] args) {
int[] nums = {1, 4, 25, 10, 25};
int k = 2;
System.out.println(appendKIntegersWithMinimalSum(nums, k)); // Outputs 5
}
}#include <iostream>
#include <vector>
#include <algorithm>
long appendKIntegersWithMinimalSum(std::vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
long sum = 0;
int current = 1;
auto it = nums.begin();
while (k > 0) {
if (it != nums.end() && *it == current) {
++it;
} else {
sum += current;
--k;
}
++current;
}
return sum;
}
int main() {
std::vector<int> nums = {1, 4, 25, 10, 25};
int k = 2;
std::cout << appendKIntegersWithMinimalSum(nums, k) << std::endl; // Outputs 5
return 0;
}function appendKIntegersWithMinimalSum(nums, k) {
nums.sort((a, b) => a - b);
let sum = 0;
let current = 1;
let index = 0;
while (k > 0) {
if (index < nums.length && nums[index] === current) {
index++;
} else {
sum += current;
k--;
}
current++;
}
return sum;
}
// Example usage
const nums = [1, 4, 25, 10, 25];
const k = 2;
console.log(appendKIntegersWithMinimalSum(nums, k)); // Outputs 5#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
long appendKIntegersWithMinimalSum(int* nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), compare);
long sum = 0;
int current = 1;
int index = 0;
while (k > 0) {
if (index < numsSize && nums[index] == current) {
index++;
} else {
sum += current;
k--;
}
current++;
}
return sum;
}
int main() {
int nums[] = {1, 4, 25, 10, 25};
int k = 2;
printf("%ld\n", appendKIntegersWithMinimalSum(nums, 5, k)); // Outputs 5
return 0;
}using System;
class Program {
public static long AppendKIntegersWithMinimalSum(int[] nums, int k) {
Array.Sort(nums);
long sum = 0;
int current = 1;
int index = 0;
while (k > 0) {
if (index < nums.Length && nums[index] == current) {
index++;
} else {
sum += current;
k--;
}
current++;
}
return sum;
}
static void Main() {
int[] nums = {1, 4, 25, 10, 25};
int k = 2;
Console.WriteLine(AppendKIntegersWithMinimalSum(nums, k)); // Outputs 5
}
}The Python code sorts the input list 'nums' and iterates from 1, appending missing integers not in 'nums' which produces the minimal additional sum due to starting from the smallest integers.
Time Complexity: O(n log n) due to sorting, then O(k + n) for processing.
Space Complexity: O(1), as the additional space use is minimal outside input storage.
Approach 2: Set Based Unique Identifier Approach
Use a hash set to track elements in 'nums', quickly determining whether a number should be appended. Starting from 1, add numbers not in the set until 'k' numbers are added. This method efficiently checks membership, offering optimal traversal time.
def appendKIntegersWithMinimalSum(nums, k):
num_set = set(nums)
sum_ = 0
current = 1
while k > 0:
if current not in num_set:
sum_ += current
k -= 1
current += 1
return sum_
# Example Usage
nums = [1, 4, 25, 10, 25]
k = 2
print(appendKIntegersWithMinimalSum(nums, k)) # Outputs 5import java.util.HashSet;
import java.util.Set;
public class Main {
public static long appendKIntegersWithMinimalSum(int[] nums, int k) {
Set<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
long sum = 0;
int current = 1;
while (k > 0) {
if (!numSet.contains(current)) {
sum += current;
k--;
}
current++;
}
return sum;
}
public static void main(String[] args) {
int[] nums = {1, 4, 25, 10, 25};
int k = 2;
System.out.println(appendKIntegersWithMinimalSum(nums, k)); // Outputs 5
}
}#include <iostream>
#include <unordered_set>
#include <vector>
long appendKIntegersWithMinimalSum(std::vector<int>& nums, int k) {
std::unordered_set<int> numSet(nums.begin(), nums.end());
long sum = 0;
int current = 1;
while (k > 0) {
if (numSet.find(current) == numSet.end()) {
sum += current;
k--;
}
current++;
}
return sum;
}
int main() {
std::vector<int> nums = {1, 4, 25, 10, 25};
int k = 2;
std::cout << appendKIntegersWithMinimalSum(nums, k) << std::endl; // Outputs 5
return 0;
}function appendKIntegersWithMinimalSum(nums, k) {
const numSet = new Set(nums);
let sum = 0;
let current = 1;
while (k > 0) {
if (!numSet.has(current)) {
sum += current;
k--;
}
current++;
}
return sum;
}
// Example usage
const nums = [1, 4, 25, 10, 25];
const k = 2;
console.log(appendKIntegersWithMinimalSum(nums, k)); // Outputs 5#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 1000000
bool exists[MAX] = { false };
long appendKIntegersWithMinimalSum(int* nums, int numsSize, int k) {
for (int i = 0; i < numsSize; i++) {
if (nums[i] <= MAX) {
exists[nums[i]] = true;
}
}
long sum = 0;
for (int num = 1; k > 0; num++) {
if (num <= MAX && !exists[num]) {
sum += num;
k--;
}
}
return sum;
}
int main() {
int nums[] = {1, 4, 25, 10, 25};
int k = 2;
printf("%ld\n", appendKIntegersWithMinimalSum(nums, 5, k)); // Outputs 5
return 0;
}using System;
using System.Collections.Generic;
class Program {
public static long AppendKIntegersWithMinimalSum(int[] nums, int k) {
HashSet<int> numSet = new HashSet<int>(nums);
long sum = 0;
int current = 1;
while (k > 0) {
if (!numSet.Contains(current)) {
sum += current;
k--;
}
current++;
}
return sum;
}
static void Main() {
int[] nums = {1, 4, 25, 10, 25};
int k = 2;
Console.WriteLine(AppendKIntegersWithMinimalSum(nums, k)); // Outputs 5
}
}This Python code employs a set to efficiently check the presence of numbers, iterating to append the smallest absent numbers to achieve the least sum, ensuring minimal computation overlap.
Time Complexity: O(n + k), since checking and adding to a set is O(1) average, and iteration seeks the missing integers.
Space Complexity: O(n), primarily due to storage necessitated by the set.
Approach 3: Sorting + Greedy + Mathematics
We can add two sentinel nodes to the array, which are 0 and 2 times 10^9.
Then we sort the array. For any two adjacent elements a and b in the array, the integers in the interval [a+1, b-1] do not appear in the array, and we can add these integers to the array.
Therefore, we traverse the adjacent element pairs (a, b) in the array from small to large. For each adjacent element pair, we calculate the number of integers m in the interval [a+1, b-1]. The sum of these m integers is \frac{m times (a+1 + a+m)}{2}. We add this sum to the answer and subtract m from k. If k is reduced to 0, we can stop the traversal and return the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array.
function minimalKSum(nums: number[], k: number): number {
nums.push(...[0, 2 * 10 ** 9]);
nums.sort((a, b) => a - b);
let ans = 0;
for (let i = 0; i < nums.length - 1; ++i) {
const m = Math.max(0, Math.min(k, nums[i + 1] - nums[i] - 1));
ans += Number((BigInt(nums[i] + 1 + nums[i] + m) * BigInt(m)) / BigInt(2));
k -= m;
}
return ans;
}func minimalKSum(nums []int, k int) (ans int64) {
nums = append(nums, []int{0, 2e9}...)
sort.Ints(nums)
for i, b := range nums[1:] {
a := nums[i]
m := max(0, min(k, b-a-1))
ans += int64(a+1+a+m) * int64(m) / 2
k -= m
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to sorting, then O(k + n) for processing. |
| Set Based Unique Identifier Approach | Time Complexity: O(n + k), since checking and adding to a set is O(1) average, and iteration seeks the missing integers. |
| Sorting + Greedy + Mathematics | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Set-Based Unique Identifier | O(n + k) | O(n) | Simple implementation when k is relatively small and memory for a hash set is acceptable |
| Greedy with Sorting | O(n log n) | O(1) extra | Optimal interview solution; efficiently processes gaps and handles large k using arithmetic series |
Frequently asked questions
Is Append K Integers With Minimal Sum easy or hard?
The problem is rated Medium on LeetCode. The difficulty comes from recognizing that missing ranges can be summed mathematically instead of enumerating each number, which significantly reduces the number of operations.
Append K Integers With Minimal Sum Python/Java solution
Most implementations follow the same greedy pattern: sort the array, iterate through gaps, and compute range sums using an arithmetic progression formula. This logic translates directly into Python, Java, C++, or JavaScript with identical O(n log n) complexity.
How to solve Append K Integers With Minimal Sum in O(n)?
An O(n + k) approach uses a hash set. Insert all array values into the set, then iterate integers starting from 1 and append numbers not found in the set until k values are chosen. Each lookup is O(1) on average, but the scan may extend to n + k integers.
What is the best approach for Append K Integers With Minimal Sum?
The greedy approach with sorting is considered the best solution. Sort the array, track the smallest candidate integer, and fill missing ranges before each element. Instead of inserting numbers individually, compute sums using the arithmetic series formula. This runs in O(n log n) time with O(1) extra space.
Is Append K Integers With Minimal Sum asked at Google/Amazon/Meta?
Problems involving greedy gap filling and arithmetic progression sums appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of missing-number or minimal-sum selection problems test greedy reasoning and array manipulation skills.
What data structure is used in Append K Integers With Minimal Sum?
Common implementations use arrays with sorting and simple integer pointers for the greedy approach. Another solution uses a hash set to track existing numbers and quickly test whether a candidate integer already exists.
What is the time complexity of Append K Integers With Minimal Sum?
The optimal greedy solution runs in O(n log n) time due to sorting the input array. After sorting, the algorithm scans the array once and processes missing ranges using constant-time arithmetic calculations. Space complexity is O(1) if sorting is done in place.