Watch 7 video solutions for Append K Integers With Minimal Sum, a medium level problem involving Array, Math, Greedy. This walkthrough by Bro Coders has 3,123 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |