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 <= 108Problem 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.
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.
The function first sorts the array. It then iterates through potential numbers, appending them unless they are present in the already sorted nums array. This ensures the smallest numbers are added, achieving minimal sum increment.
Time Complexity: O(n log n) due to sorting, followed by O(k + n) to traverse the array.
Space Complexity: O(1), considering the sort space is negligible.
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.
This C solution uses an array to mark existing numbers, checking present/missing status quickly as numbers are iterated from 1, ensuring efficient decision-making for minimal sum addition.
Time Complexity: O(n + k), where n is the length of nums and processing involves marking existence and iterating to find 'k'.
Space Complexity: O(MAX), due to fixed-size array employed for existence checking.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to sorting, followed by O(k + n) to traverse the array. |
| Set Based Unique Identifier Approach | Time Complexity: O(n + k), where n is the length of nums and processing involves marking existence and iterating to find 'k'. |
| Sorting + Greedy + Mathematics | — |
| 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 |
2195. Append K Integers With Minimal Sum || Leetcode Weekly Contest 283 || Leetcode 2195 • Bro Coders • 3,123 views views
Watch 6 more video solutions →Practice Append K Integers With Minimal Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor