Append K Integers With Minimal Sum

MEDIUM

Description

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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁸

Approaches

Checkout 3 different approaches to solve Append K Integers With Minimal Sum. Click on different approaches to view the approach and algorithm in detail.

Brute-force Simulation with a Set

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 HashSet and populate it with all the numbers from the input array nums. This allows for average O(1) time complexity for checking if a number exists.
Initialize a long variable sum to 0 to store the sum of the appended integers, and an integer count to 0.
Initialize a long variable currentNum to 1. This will be the candidate integer to append.
Start a loop that continues as long as count < k.
Inside the loop, check if currentNum is present in the HashSet.
If currentNum is not in the set, it's a valid number to append. Add currentNum to sum and increment count.
Increment currentNum in every iteration to check the next positive integer.
Once the loop finishes (i.e., count reaches k), return the total sum.

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 Analysis

Time Complexity: 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 Complexity: O(n), where n is the number of elements in `nums`. This space is used to store the `HashSet`.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Highly inefficient for large values of k, as the main loop's iterations depend on k.

Code Solutions

Checking out 3 solutions in different languages for Append K Integers With Minimal Sum. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Append K Integers With Minimal Sum

Algorithms:

Sorting

Patterns:

MathGreedy

Data Structures:

Array