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?

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

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.