Finding two non-subsequent elements in array which sum is minimal
- Find the smallest number beside the first and the last.
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.
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.
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"> <=
<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).