Finding two non-subsequent elements in array which sum is minimal
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 elementsvar 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 listselect.onchange = function() { input.value = select.value; process();}// respond to change in input boxinput.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).
- 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.
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).