find minimum sum of non-neighbouring K entries inside an array

Question

Given an integer array A of size N, find minimum sum of K non-neighboring entries (entries cant be adjacent to one another, for example, if K was 2, you cant add A[2], A[3] and call it minimum sum, even if it was, because those are adjacent/neighboring to one another), example:

A[] = {355, 46, 203, 140, 28}, k = 2, result would be 74 (46 + 28)

A[] = {9, 4, 0, 9, 14, 7, 1}, k = 3, result would be 10 (9 + 0 + 1)

The problem is somewhat similar to House Robber on leetcode, except instead of finding maximum sum of non-adjacent entries, we are tasked to find the minimum sum and with constraint K entries.

From my prespective, this is clearly a dynamic programming problem, so i tried to break down the problem recursively and implemented something like this:

#include <vector>
#include <iostream>
using namespace std;
int minimal_k(vector<int>& nums, int i, int k)
{
    if (i == 0) return nums[0];
    if (i < 0 || !k) return 0;
    return min(minimal_k(nums, i - 2, k - 1) + nums[i], minimal_k(nums, i - 1, k));
}
int main()
{
    // example above
    vector<int> nums{9, 4, 0, 9, 14, 7, 1};
    cout << minimal_k(nums, nums.size() - 1, 3);
    // output is 4, wrong answer
}

This was my attempt at the solution, I have played around a lot with this but no luck, so what would be a solution to this problem?

Answer 1

This is 2D Dynamic Programming problem and in my opinion it's more similar to those 'best time to buy / sell stocks' problems instead of house robber which is 1D.

The reason why it needs to be 2D is there are two variables to track:

• The idx of the item from array A
• The remaining value of k

Recursion stops at 2 conditions:

1. Remaining value of k becomes 0 in which case we find a candidate value
2. The idx reaches end of array A while k > 0 in which case we don't find a candidate value

If a particular value at idx is selected, the recursion will look idx + 2 for the next number.

The top-down solution in C++ is already provided by the other answer. Here's Python implementation. Note that in case of a candidate value is not found, I use None but if the problem allows (e.g. no negative numbers in A), we can also use negative numbers.

def min_non_adjacent_sum_top_down(nums: typing.List[int], k: int) -> int:
    cache = {}

    def dfs(idx, remain_k):
        if (idx, remain_k) in cache:  # already cached
            return cache[(idx, remain_k)]
        if remain_k == 0:  # We found the candidate value
            return 0
        if idx > len(nums) - 1:  # iterated all numbers while remain_k > 0 - not a candidate value
            return None

        include_idx = dfs(idx + 2, remain_k - 1)  # include nums[idx]
        if include_idx is not None:
            include_idx += nums[idx]  # We have a candidate solution which includes nums[idx]
        exclude_idx = dfs(idx + 1, remain_k)  # exlcude nums[idx]

        if include_idx is None and exclude_idx is None:
            res = None
        elif include_idx is None and exclude_idx is not None:
            res = exclude_idx
        elif include_idx is not None and exclude_idx is None:
            res = include_idx
        else:
            res = min(include_idx, exclude_idx)
        cache[(idx, remain_k)] = res
        return res

    return dfs(0, k)

We can also implement this with bottom up approach using a 2D list where the number of rows is k and number of columns is the length of A. So each row i, column j represents the sum for i-th step out of k for choosing j-th number in A. The logic for updating the table is as follows:

1. For row i = 0, its column is just the value of A since it's possible to choose any number from A as the first number out of k
2. For next row i = 0, row[j] will pick up the minimum from non-adjacent previous_row[0] ... previous_row[j - 2] and add the result to A[j]

Once the table is constructed, we can just iterate the last column to get the minimum.

Again my bottom-up solution is based on Python but it should be straightforward to change it to C++:

def min_non_adjacent_sum_bottom_up(nums: typing.List[int], k: int) -> int:
    dp = [[None] * len(nums) for _ in range(k)]
    for i in range(k):
        for j in range(len(nums)):
            if i == 0:
                dp[i][j] = nums[j]  # first number from k can be any numbers from nums
            else:
                min_prev = None
                for k in range(0, j - 1):  # if nums[j] is selected, then its previous k will have to be before nums[j - 1] to be non-adjancent
                    if dp[i - 1][k] is None:
                        continue
                    if min_prev is None:
                        min_prev = dp[i - 1][k]
                    min_prev = min(dp[i - 1][k], min_prev)
                dp[i][j] = (min_prev + nums[j]) if min_prev is not None else None

    res = None
    for j in range(len(nums)):  # iterate the last column to get the answer
        if dp[-1][j] is None:
            continue
        if res is None:
            res = dp[-1][j]
        res = min(dp[-1][j], res)
    return res

To run:

for min_non_adjacent_sum in (min_non_adjacent_sum_top_down, min_non_adjacent_sum_bottom_up):
    print(
        min_non_adjacent_sum([355, 46, 203, 140, 28], 2),
        min_non_adjacent_sum([9, 4, 0, 9, 14, 7, 1], 3),
    )

Answer 2

It is core sorting related problem. To find sum of minimum k non adjacent elements requires minimum value elements to bring next to each other by sorting. Let's see this sorting approach,

Given input array = [9, 4, 0, 9, 14, 7, 1] and k = 3
Create another array which contains elements of input array with indexes as showed below,
[9, 0], [4, 1], [0, 2], [9, 3], [14, 4], [7, 5], [1, 6]
then sort this array.

Motive behind this element and index array is, after sorting information of index of each element will not be lost.
One more array is required to keep record of used indexes, so initial view of information after sorting is as showed below,

Element and Index array
..............................
| 0 | 1 | 4 | 7 | 9 | 9 | 14 |
..............................
  2   6   1   5   3   0   4    <-- Index   

Used index record array
..............................
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
..............................
  0   1   2   3   4   5   6    <-- Index 

In used index record array 0 (false) means element at this index is not included yet in minimum sum.
Front element of sorted array is minimum value element and we include it for minimum sum and update used index record array to indicate that this element is used, as showed below,
font element is 0 at index 2 and due to this set 1(true) at index 2 of used index record array showed below,

min sum = 0

Used index record array
..............................
| 0 | 0 | 1 | 0 | 0 | 0 | 0 |
..............................
  0   1   2   3   4   5   6   

iterate to next element in sorted array and as you can see above it is 1 and have index 6. To include 1 in minimum sum we have to find, is left or right adjacent element of 1 already used or not, so 1 has index 6 and it is last element in input array it means we only have to check if value of index 5 is already used or not, and this can be done by looking at used index record array, and as showed above usedIndexRerocd[5] = 0 so 1 can be considered for minimum sum. After using 1, state updated to following,

min sum = 0 + 1

Used index record array
..............................
| 0 | 0 | 1 | 0 | 0 | 0 | 1 |
..............................
  0   1   2   3   4   5   6   

than iterate to next element which is 4 at index 1 but this can not be considered because element at index 0 is already used, same happen with elements 7, 9 because these are at index 5, 3 respectively and adjacent to used elements.
Finally iterating to 9 at index = 0 and by looking at used index record array usedIndexRecordArray[1] = 0 and that's why 9 can be included in minimum sum and final state reached to following,

min sum = 0 + 1 + 9

Used index record array
..............................
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
..............................
  0   1   2   3   4   5   6   

Finally minimum sum = 10,

One of the Worst case scenario when input array is already sorted then at least 2*k - 1 elements have to be iterated to find minimum sum of non adjacent k elements as showed below
input array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and k = 4
then following highlighted elements shall be considered for minimum sum,
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Note: You have to include all input validation, like one of the validation is, if you want to find minimum sum of k non adjacent elements then input should have at least 2*k - 1 elements. I am not including these validations because i am aware of all input constraints of problem.

#include <iostream>

#include <vector>
#include <algorithm>

using std::cout;

long minSumOfNonAdjacentKEntries(std::size_t k, const std::vector<int>& arr){

    if(arr.size() < 2){
        return 0;
    }

    std::vector<std::pair<int, std::size_t>> numIndexArr;
    numIndexArr.reserve(arr.size());

    for(std::size_t i = 0, arrSize = arr.size(); i < arrSize; ++i){

        numIndexArr.emplace_back(arr[i], i);
    }

    std::sort(numIndexArr.begin(), numIndexArr.end(), [](const std::pair<int, std::size_t>& a,
              const std::pair<int, std::size_t>& b){return a.first < b.first;});

    long minSum = numIndexArr.front().first;

    std::size_t elementCount = 1;
    std::size_t lastIndex = arr.size() - 1;

    std::vector<bool> usedIndexRecord(arr.size(), false);

    usedIndexRecord[numIndexArr.front().second] = true;

    for(std::vector<std::pair<int, std::size_t>>::const_iterator it = numIndexArr.cbegin() + 1,
        endIt = numIndexArr.cend(); elementCount < k && endIt != it; ++it){

        bool leftAdjacentElementUsed = (0 == it->second) ? false : usedIndexRecord[it->second - 1];
        bool rightAdjacentElementUsed = (lastIndex == it->second) ? false : usedIndexRecord[it->second + 1];

        if(!leftAdjacentElementUsed && !rightAdjacentElementUsed){

            minSum += it->first;

            ++elementCount;
            usedIndexRecord[it->second] = true;
        }
    }

    return minSum;
}

int main(){

    cout<< "k = 2, [355, 46, 203, 140, 28], min sum = "<< minSumOfNonAdjacentKEntries(2, {355, 46, 203, 140, 28})
        << '\n';

    cout<< "k = 3, [9, 4, 0, 9, 14, 7, 1], min sum = "<< minSumOfNonAdjacentKEntries(3, {9, 4, 0, 9, 14, 7, 1})
        << '\n';
}

Output:

k = 2, [355, 46, 203, 140, 28], min sum = 74
k = 3, [9, 4, 0, 9, 14, 7, 1], min sum = 10

Answer 3

This line:

if (i < 0 || !k) return 0;

If k is 0, you should probably return return 0. But if i < 0 or if the effective length of the array is less than k, you probably need to return a VERY LARGE value such that the summed result goes higher than any valid solution.

In my solution, I have the recursion return INT_MAX as a long long when recursing into an invalid subset or when k exceeds the remaining length.

And as with any of these dynamic programming and recursion problems, a cache of results so that you don't repeat the same recursive search will help out a bunch. This will speed things up by several orders of magnitude for very large input sets.

Here's my solution.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

// the "cache" is a map from offset to another map
// that tracks k to a final result.
typedef unordered_map<size_t, unordered_map<size_t, long long>> CACHE_MAP;

bool get_cache_result(const CACHE_MAP& cache, size_t offset, size_t k, long long& result);
void insert_into_cache(CACHE_MAP& cache, size_t offset, size_t k, long long result);


long long minimal_k_impl(const vector<int>& nums, size_t offset, size_t k, CACHE_MAP& cache)
{
    long long result = INT_MAX;
    size_t len = nums.size();

    if (k == 0)
    {
        return 0;
    }

    if (offset >= len)
    {
        return INT_MAX; // exceeded array boundary, return INT_MAX
    }

    size_t effective_length = len - offset;

    // If we have more k than remaining elements, return INT_MAX to indicate
    // that this recursion is invalid
    // you might be able to reduce to checking (effective_length/2+1 < k)
    if ( (effective_length < k)  ||  ((effective_length == k) && (k != 1)) )
    {
        return INT_MAX;
    }

    if (get_cache_result(cache, offset, k, result))
    {
        return result;
    }

    long long sum1 = nums[offset] + minimal_k_impl(nums, offset + 2, k - 1, cache);
    long long sum2 = minimal_k_impl(nums, offset + 1, k, cache);
    result = std::min(sum1, sum2);

    insert_into_cache(cache, offset, k, result);

    return result;
}

long long minimal_k(const vector<int>& nums, size_t k)
{
    CACHE_MAP cache;
    return minimal_k_impl(nums, 0, k, cache);
}


bool get_cache_result(const CACHE_MAP& cache, size_t offset, size_t k, long long& result)
{
    // effectively this code does this:
    // result = cache[offset][k]

    bool ret = false;
    auto itor1 = cache.find(offset);
    if (itor1 != cache.end())
    {
        auto& inner_map = itor1->second;
        auto itor2 = inner_map.find(k);
        if (itor2 != inner_map.end())
        {
            ret = true;
            result = itor2->second;
        }
    }
    return ret;
}

void insert_into_cache(CACHE_MAP& cache, size_t offset, size_t k, long long result)
{
    cache[offset][k] = result;
}


int main()
{
    vector<int> nums1{ 355, 46, 203, 140, 28 };
    vector<int> nums2{ 9, 4, 0, 9, 14, 7, 1 };
    vector<int> nums3{8,6,7,5,3,0,9,5,5,5,1,2,9,-10};

    long long result = minimal_k(nums1,  2);
    std::cout << result << std::endl;

    result = minimal_k(nums2, 3);
    std::cout << result << std::endl;

    result = minimal_k(nums3, 3);
    std::cout << result << std::endl;


    return 0;
}