Finding two non-subsequent elements in array which sum is minimal

Question

Intro: As far as I could search, this question wasn't asked in SO yet.
This is an interview question.
I am not even specifically looking for a code solution, any algorithm/pseudocode will work.

---

The problem: Given an integer array int[] A and its size N, find 2 non-subsequent (can't be adjacent in the array) elements with minimal sum. Also the answer must not contain the first or last elements (index 0 and n-1). Also the solution should be in O(n) time and space complexity.

E.g. when A = [5, 2, 4, 6, 3, 7] the answer is 5, since 2+3=5.
When A = [1, 2, 3, 3, 2, 1] the answer is 4, since 2+2=4 and you can't choose either of the 1's since the are at the ends of the array.

---

Attempt: At first I thought that one of the numbers in the solution must be the smallest one in the array (besides the first and last), but this was refuted quickly with the counter-example
A = [4, 2, 1, 2, 4] -> 4 (2+2)

Then I thought that if I find the 2 smallest numbers (besides the first and last) in the array, the solution will be those two. This obviously quickly failed because I can't choose 2 adjacent numbers, and if I have to choose non-adjacent numbers then this is the very definition of the question :).

Finally I thought, well, I will just find the 3 smallest numbers (besides the first and last) in the array, and the solution will have to be two of those, since two of those have to not be adjacent to each other. This also failed due to A = [2, 2, 1, 2, 4, 2, 6] -> 2+1=3 , which seems to work because I will find 2, 1, 2, but assuming I am finding the 2, 1, 2 in indexes 1, 2, 3 this won't necessarily work (it would if I found specifically the 2 in index 5 but I can't guarantee that unfortunately).

---

Question: Now I'm stumped, can anyone come up with a solution/idea that works?

Stateless

Are you sure it can be solved in O(n) time? – Reducer

How about modifying the three smallest numbers approach to include the indexes as well. You would need 6 places to store - 3 indexes, 3 values. If you see a duplicate value then just update the index so that in your example upon seeing the '2' at index '5' the the 2nd index can be updated as 5 thus making elements at '2' and '5' as the solutions in the same pass. Just be sure to update index for duplicates only if the one's that are being tracked are already adjacent. – Murdock

Just to make sure I understand the question, a) The answer for A = {1,2,2,2,1} would be 4 ? b) The minimum length for the array is 5? – Murdock

A) yes. B) yes, otherwise it's not really interesting... – Stateless

You probably could use a variation of the Kadane's algorithm to solve this. – Litha

@higuaro, I think it would need a lot of variation, as that algorithm relies heavily on selected elements being adjacent, where here the requirement is opposite. – Ouse

Answer 1

Here is a live javascript implementation of an algorithm that:

• finds the 4 smallest elements (excluding first/last element from search)
• finds the pairs of these 4 elements that are not adjacent in original array
• finds from these pairs the one with the minimal sum

function findMinNonAdjacentPair(a) {
    var mins = [];
    
    // quick exits:
    if (a.length < 5) return {error: "no solution, too few elements."};
    if (a.some(isNaN)) return {error: "non-numeric values given."};
    
    // collect 4 smallest values by their indexes    
    for (var i = 1; i < a.length - 1; i++) { // O(n)
        if (mins.length < 4 || a[i] < a[mins[3]]) {
            // need to keep record of this element in sorted list of 4 elements
            for (var j = Math.min(mins.length - 1, 2); j >= 0; j--) { // O(1)
                if (a[i] >= a[mins[j]]) break;
                mins[j+1] = mins[j];
            }
            mins[j+1] = i;
        }
    }
    // mins now has the indexes to the 4 smallest values

    // Find the smallest sum
    var result = {
        sum: a[mins[mins.length-1]]*2+1 // large enough
    }
    
    for (var j = 0; j < mins.length-1; j++) { // O(1)
        for (var k = j + 1; k < mins.length; k++) {
            if (Math.abs(mins[j] - mins[k]) > 1) { // not adjacent
                if (result.sum    > a[mins[j]]+a[mins[k]]) {
                    result.sum    = a[mins[j]]+a[mins[k]];
                    result.index1 = mins[j];
                    result.index2 = mins[k];
                };
                if (k < j + 3) return result; // cannot be improved
                break; // exit inner loop: it cannot bring improvement
            }
        }
    }
    return result;
}

// Get I/O elements
var input = document.getElementById('in');
var output = document.getElementById('out');
var select = document.getElementById('pre');

function process() {
    // translate input to array of numbers
    var a = input.value.split(',').map(Number);
    // call main function and display returned value
    output.textContent = JSON.stringify(findMinNonAdjacentPair(a), null, 4);
}

// respond to selection from list
select.onchange = function() {
    input.value = select.value;
    process();
}

// respond to change in input box
input.oninput = process;

// and produce result upon load:
process();

Type comma-separated list of values (or select one):</br>
<input id="in" value="2, 2, 1, 2, 4, 2, 6"> &lt;=
<select id="pre">
    <option value="5, 2, 4, 6, 3, 7">5, 2, 4, 6, 3, 7</option>
    <option value="1, 2, 3, 3, 2, 1">1, 2, 3, 3, 2, 1</option>
    <option value="4, 2, 1, 2, 4">4, 2, 1, 2, 4</option>
    <option value="2, 2, 1, 2, 4, 2, 6" selected>2, 2, 1, 2, 4, 2, 6</option>
</select>
</br>
Output:</br>
<pre id="out"></pre>

The algorithm has a few loops with following big-O complexities:

• find 4 smallest values: O(n), as the inner loop runs at most 3 times, which is O(1)
• find the smallest sum of non-adjacent pairs has a double loop: in total the body will run at most 4 times = O(1). NB: The number of possible pairs is 6, but the execution is guaranteed to break out of the loops sooner.

So the algorithm runs in O(n).

Ouse

Answer 2

1. Find the smallest number beside the first and the last.

2. Find the second smallest that is not a neighbour of the first one and not the first or last one in the array. Then build the sum.

   • If the first element is the second or the penultimate element you already have the solution.

3. Otherwise calculate the sum of both neighbours of the first number. check if its smaller then the first sum

   • if not: take the first sum
   • otherwise take the second one

This will always work because if the first sum is not the answer that means the first number cannot be part of the solution. And that on the other hand means, the solution can just be the second sum.

Hypocycloid

This is missing a crucial element of excluding the ends from steps 2 and 3. However if you just remove both ends as step 0 (and consider all elements in step 1), then all should work OK. – Meyer

I added you suggestion to the answer – Hypocycloid

Answer 3

This problem can be solved with about 10 lines of Java code.

You can start with an obvious but inefficient (O(N^2)) solution:

public class Main {

    int solve(int[] array) {
        int answer = Integer.MAX_VALUE;
        for (int i = 3; i < array.length - 1; i++) {
            for (int j = 1; j < i - 1; j++) {
                if (array[i] + array[j] < answer) {
                    answer = array[i] + array[j];
                }
            }
        }
        return answer;
    }
}

But then you can notice that you actually do not need the internal for loop because you can just preserve the minimum and update it with every new element if necessary, which is faster than finding the minimum anew every time. Therefore the final O(N) solution looks like this:

public class Main {

    int solve(int[] array) {
        int answer = Integer.MAX_VALUE;
        int min = array[1];
        for (int i = 3; i < array.length - 1; i++) {
            min = Math.min(min, array[i - 2]);
            if (array[i] + min < answer) {
                answer = array[i] + min;
            }
        }
        return answer;
    }
}

Lindberg

The most accurate and optimal solution. – Otilia

Answer 4

Find the four smallest and consider all possibilities among those four. The smallest is nonadjacent to at least one of the second, third, or fourth smallest; the only other possibility that could be better is the second and third smallest (assuming that they are nonadjacent).

Other

I am writing some code to test this. If it is right then kudos! :) – Stateless

We would either need track the indexes to avoid another pass is it not ? – Murdock

@RavindraHV Yes, that was implicit in the asker's attempted solutions as well. – Other

If you call these numbers 1, 2, 3, 4 then the smallest sum is 1+2 if non adjacent, otherwise 1+3 if non-adjacent, otherwise 2+3 and 1+4 are both nonadjacent and the optimal result is the smaller sum. – Rowles

Answer 5

I think this does not need any deep reasoning, and can be solved in a single pass, keeping the optimal solution of the array elements processed so far:

public static int[] minimumSumOfNonAcjacentElements(int[] a) {
    // the result for the sequence a[1:i]
    int minSum = Integer.MAX_VALUE;
    int minSumElement1 = Integer.MAX_VALUE;
    int minSumElement2 = Integer.MAX_VALUE;

    // the minimum element eligible for joining with a[i], i.e. from a[1 : i-2]
    int minElement = a[1];

    int prevElement = a[2]; // a[i - 1]
    for (int i = 3; i + 1 < a.length; i++) {
        int sum = minElement + a[i];
        if (sum < minSum) {
            minSum = sum;
            minSumElement1 = minElement;
            minSumElement2 = a[i];
        }

        if (prevElement < minElement) {
            minElement = prevElement;
        }
        prevElement = a[i];
    }

    return new int[] {minSumElement1, minSumElement2};
}

Here's some test code, with the corner cases from OP's question:

private static void test(int minSumIndex1, int minSumIndex2, int... input) {
    int[] result = minimumSumOfNonAcjacentElements(input);
    if (result[0] == minSumIndex1 && result[1] == minSumIndex2) {
        // ok
    } else {
        throw new AssertionError("Expected: " + minSumIndex1 + ", " + minSumIndex2 + ". Actual=" + Arrays.toString(result));
    }
}

public static void main(String[] args) throws Exception {
    test(2, 2, 4, 2, 1, 2, 4);
    test(1, 2, 2, 2, 1, 2, 4, 2, 6);
    test(1, 2, 0, 2, 1, 2, 4, 2, 0);
    System.out.println("All tests passed.");
}

Abib

Hi can you please explain how this solution fulfills the requirements that the indexes should be not adjacent? I don't get where you keep track of this in your code.Thanks – Rocambole

Answer 6

Use dynamic programming.

1. Remove or disregard the first and last elements of your array. Since they cannot participate in the solution, they are not important. Once you've done this, you can also ignore the "must not be the first or last element" constraint since we've already accounted for it.
2. Find the solution for the first three elements of (what's left of) the array (and without considering the "no first/last element" rule). There is only one solution in this case (array[0] + array[2]), so this is a trivial step.
3. Memoize the minimal element which is not the last element (i.e. min(array[0], array[1])).
4. Find the solution for the first four elements. We don't have to redo the whole problem; instead we just have to ask whether introducing the fourth element allows us to produce a smaller solution. We can do this by adding the fourth element to the minimal element we memoized in the previous step, and comparing the sum to the solution we found in the second step.
5. Update the memoized minimal element so that it is the minimum of the first three elements.
6. Continue widening and updating in this fashion until we have considered the entire array.

The whole algorithm is O(n), since both widening and updating are constant-time operations. The algorithm can be proved correct by simple induction. O(n) is also a lower bound since we have to consider every element of the array, so this algorithm is optimal.

Dympha

The smallest array that adheres to the constraints in the OP has a length of 5. But that shouldn't affect your general approach. – Kimberelykimberlee

This puts meriton's approach into words, with some buzzwords to go. – Hypotension

Answer 7

Algorithm:

1. Find the minimum, avoiding the end indices. (1 O(n) pass)
2. Find the minimum, avoiding the end indices and the index of (1) and adjacent indices. (1 O(n) pass)
3. Find the minimum, avoiding the end indices and the index of (1) (1 O(n) pass)
4. Find the minimum, avoiding the end indices and the index of (3) and adjacent indices. (1 O(n) pass)
5. Return the minimum of the sums (1) + (2), (3) + (4), if they exist.

Passes 3 and 4 are meant to pass the case [4, 2, 1, 2, 4] = 4 by finding both 2s.

public static int minSumNonAdjNonEnd(int[] array)
{
    // 1. Find minimum
    int minIdx1 = -1;
    int minValue1 = Integer.MAX_VALUE;
    for (int i = 1; i < array.length - 1; i++)
    {
        if (array[i] < minValue1)
        {
            minIdx1 = i;
            minValue1 = array[i];
        }
    }
    // 2. Find minimum not among (1) or adjacents.
    int minIdx2 = -1;
    int minValue2 = Integer.MAX_VALUE;
    for (int i = 1; i < array.length - 1; i++)
    {
        if ((i < minIdx1 - 1 || i > minIdx1 + 1) && (array[i] < minValue2))
        {
            minIdx2 = i;
            minValue2 = array[i];
        }
    }
    boolean sum1Exists = (minIdx1 > -1 && minIdx2 > -1);
    int sum1 = minValue1 + minValue2;

    // 3. Find minimum not among (1).
    int minIdx3 = -1;
    int minValue3 = Integer.MAX_VALUE;
    for (int i = 1; i < array.length - 1; i++)
    {
        if ((i != minIdx1) && (array[i] < minValue3))
        {
            minIdx3 = i;
            minValue3 = array[i];
        }
    }

    // 4. Find minimum not among(3) or adjacents.
    int minIdx4 = -1;
    int minValue4 = Integer.MAX_VALUE;
    for (int i = 1; i < array.length - 1; i++)
    {
        if ((i < minIdx3 - 1 || i > minIdx3 + 1) && (array[i] < minValue4))
        {
            minIdx4 = i;
            minValue4 = array[i];
        }
    }
    boolean sum2Exists = (minIdx3 > -1 && minIdx4 > -1);
    int sum2 = minValue3 + minValue4;

    if (sum1Exists)
    {
        if (sum2Exists)
            return Math.min(sum1, sum2);
        else
            return sum1;
    }
    else
    {
        if (sum2Exists)
            return sum2;
        else
            throw new IllegalArgumentException("impossible");
    }
}

This performs 4 linear searches, for a complexity of O(n).

Test cases:

System.out.println(minSumNonAdjNonEnd(new int[] {5, 2, 4, 6, 3, 7}));
System.out.println(minSumNonAdjNonEnd(new int[] {1, 2, 3, 3, 2, 1}));
System.out.println(minSumNonAdjNonEnd(new int[] {4, 2, 1, 2, 4}));
System.out.println(minSumNonAdjNonEnd(new int[] {2, 2, 1, 2, 4, 2, 6}));
System.out.println(minSumNonAdjNonEnd(new int[] {2, 2, 3, 2}));

5
4
4
3
Exception in thread "main" java.lang.IllegalArgumentException: impossible

Moulder

Answer 8

edit: you're right, I completely ignored the adjacency constraint. luckily I've thought of a solution. The algorithm goes like this:

1. You run once over the array to find the smallest (O(n))
2. You run a second time to find the second smallest (O(n))
3. If second smallest is not adjacent to smallest we're done(O(1) - just an index check)
4. Otherwise run a third time to find third smallest (still O(n))
5. If not adjacent to smallest return smallest and third smallest otherwise return second and third smallest

Braise

Link-only answers are not helpful in StackOverflow - let alone that this doesn't solve my problem because of the constraints. Please re-read the question – Stateless

The OP has already tried this approach which doesn't necessarily work for the array A = [2, 2, 1, 2, 4, 2, 6]. – Alf

Answer 9

Elaborating on the above answer, you'd need a modified insertion-sort to track the smallest four values and the corresponding indexes (an array of 4 elements for each).

Once found the solution would be the first pair whose difference in indexes would be more than 1 and whose sum is the least.

The solution being one of (0,1) or (0,2) or (0,3) or (1,2) or (1,3) or (2,3) where the values indicate the indexes of the array that in turn tracks the position of the actual elements in the array.

Also you'd need to handle the special case for array-length 5 (arr\[1]+arr[3]) and an error for those arrays less than 5.

Murdock

Answer 10

I don't know if my solution is correct because I just tested it with the data in the OP, and I don't even know if this is better or worse than the other ideas but I wanted to try it.

static void printMinimalSum(int[] A) {  
    // Looking for mins so we init this with max value
    int[] mins = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE};
    // Indices, used just to print the solution
    int[] indices = new int[]{-1, -1, -1};
    // If the array has length 5 then there's only one solution with the 2nd and 4th elements
    if (A.length == 5) {
        mins[0] = A[1];
        indices[0] = 1;
        mins[1] = A[3];
        indices[1] = 3;
    } else {        
        // Loop on the array without considering the first and the last element
        for (int i = 1; i < A.length - 1; i++) {
            // We consider each element which is smaller than its neighbours
            if ((i == 1 && A[i] < A[i + 1]) // 1: first element, compare it with the second one
                    || (i == A.length - 2 && A[i] < A[i - 1]) // 2: last element, compare it with the previous one
                    || (A[i] < A[i + 1] && A[i] < A[i - 1])) { // 3: mid element, compare it with both neighbors
                // If the element is "legal" then we see if it's smaller than the 3 already saved
                if (A[i] < mins[0]) {
                    mins[0] = A[i];
                    indices[0] = i;
                } else if (A[i] < mins[1]) {
                    mins[1] = A[i];
                    indices[1] = i;
                } else if (A[i] < mins[2]) {
                    mins[2] = A[i];
                    indices[2] = i;
                }
            }
        }
    }     
    // Compute the 3 sums between those 3 elements
    int[] sums = new int[]{Math.abs(mins[0]+mins[1]), Math.abs(mins[0]+mins[2]), Math.abs(mins[1]+mins[2])};
    // Find the smaller sum and print it
    if (sums[0] < sums[1] || sums[0] < sums[2]){
        System.out.println("Sum = " + sums[0] + " (elements = {" + mins[0] + "," + mins[1] + "}, indices = {" + indices[0] + "," + indices[1] + "}");
    } else if (sums[1] < sums[0] || sums[1] < sums[2]){
        System.out.println("Sum = " + sums[1] + " (elements = {" + mins[0] + "," + mins[2] + "}, indices = {" + indices[0] + "," + indices[2] + "}");
    } else {
        System.out.println("Sum = " + sums[2] + " (elements = {" + mins[1] + "," + mins[2] + "}, indices = {" + indices[1] + "," + indices[2] + "}");
    }
}

public static void main(String[] args) {
    printMinimalSum(new int[]{5, 2, 4, 6, 3, 7});
    printMinimalSum(new int[]{1, 2, 3, 3, 2, 1});
    printMinimalSum(new int[]{4, 2, 1, 2, 4});
    printMinimalSum(new int[]{2, 2, 1, 2, 4, 2, 6});
}

Output is:

Sum = 5 (elements = {2,3}, indices = {1,4}
Sum = 4 (elements = {2,2}, indices = {1,4}
Sum = 4 (elements = {2,2}, indices = {1,3}
Sum = 3 (elements = {1,2}, indices = {2,5}

which seems fine.

Larhondalari

Answer 11

How about that: you find k smallest numbers (or more precisely their indices) (k big enough, let say 10). It is sure, that the wanted pair is between them. Now you just check the possible 50 pairs and select the best which satisfies the constraints.

You don't need 10, less would do - but more than 3 :)

Edit: finding k smallest numbers is O(n), because you just keep the best 10 for example in a heap (add new element, delete maximum O(k*logk)=O(1) operations).

Then there will be a pair which satisfy the constraints (not next to each other). It is also clear that, if you build the sum with an element not from those k, it would be bigger than the best pair chosen from those k elements.

Checking at most k*k pairs is also O(1), thus the whole running time is O(n).

Reneta

This doesn't guarantee either. – Larkin

There are no permutation involved, to find k smallest number out of n elements you need 10*n operations. And than there are only k*(k-1)/2 pairs. – Reneta

Answer 12

I think this should work:

Find the minimum 3 element and their indices. Since all of them can't be adjacent choose 2 among them.

If all of them are adjacent and the minimum number is in the middle of them, iterate through all elements, find the forth minimum element, choose minimum of min1+min4, min2+min3, whichever is smaller.

You can do this in one iteration too.

Larkin

This was literally one of my attemps... Please read the question :/ – Stateless

Answer 13

I have used dynamic programming to solve it.

Idea is to first create the array which tracks the minimum found till now as below: Input array = [1, 3, 0, 5, 6] Minimum array = [1, 1, 0, 0, 0]

Now using the minimum array and the input array we can use below:

DP[i] = min(DP[i-1], min(first_data, second_data))

where DP[i] means the minimum found till now which is sum of two previous alternate elements.

first_data = sum of current element in input array + sum of current-2 element in minimum array

second_data = sum of current-1 element in input array + sum of current-3 element in minimum array

    import random
    def get_min(numbers):
            #disregard the first and last element
            numbers = numbers[1:len(numbers)-1]
            #for remembering the past results
            DP = [0]*len(numbers)
            #for keeping track of minimum till now found
            table = [0]*len(numbers)
            high_number = 1 << 30

            min_number = numbers[0]
            table[0] = min_number
            for i in range(0, len(numbers)):
                    DP[i] = high_number
            for i in range(1, len(numbers)):
                    if numbers[i] < min_number:
                            min_number = numbers[i]
                            table[i] = numbers[i]
                    else:
                            table[i] = min_number
            for i in range(0, len(numbers)):
                    min_first, min_second = high_number, high_number
                    if i >= 2:
                            min_first = numbers[i] + table[i-2]
                    if i >= 3:
                            min_second = numbers[i-1] + table[i-3]
                    if i >= 1:
                            DP[i] = min(min(DP[i-1], min_first), min_second)
            return DP[len(numbers)-1]

    input = random.sample(range(100), 10)
    print(input)
    print(get_min(input))

Nosing

Answer 14

Here is the python implementation in O(N) time complexity

import math

def minSum(array):
    _min = array[1]
    result = math.inf

    for i in range(3, len(array) - 1):
        _min = min(_min, array[i-2])
        if (_min + array[i]) < result:
            result = _min + array[i]
    return result

Weaponless

Cf. yaskovdev's 2020 solution. Or MD Ruhul Amin's 2021/01/08 one. – Hypotension

Answer 15

As we only need to track the minimum sum of two no adjacent values, we could do it by iterating over the array excluding the first and last element and keeping the track of min values and minimum sum. current min value will the two index before current value. For example if we are checking the current index i then minValue is the minimum value from index 1 to i-2. Code:

    int minSum(int[] A){
        int minSum=Integer.MAX_VALUE;
        int min= Integer.MAX_VALUE;
        for(int i=3; i<A.length-1; i++){
            min= Math.min(A[i-2], min);
            minSum = Math.min(min+A[i], minSum);
        }
        return minSum;
    }

Otilia

Cf. yaskovdev's 2020 solution. – Hypotension