Search code examples
javaarraysalgorithmtime-complexityminimum

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

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?

Solution

  • 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).