Is there an efficient way to find a subsequence of length 3 where the first is the lowest, the second the largest and the last inside that range?

Question

For instance, given the list [5, 9, 1, 2, 7, 8], the algorithm should find subsequences such as [5, 9, 7] or [5, 9, 8].

I need the algorithm to be efficient. One approach could involve tracking the maximum and minimum values while iterating through the list. Whenever a number falls between the current maximum and minimum, it's a potential candidate. However, this approach may fail in certain scenarios like this:

Consider the list [5, 8, 10, 2, 4]. The algorithm might suggest [2, 10, 4] as a solution, but it violates the restriction that the lowest value must precede the highest.

Do you know of a solution that works? Thank you.

Answer 1

You could use this approach:

• Maintain a stack of "segments", where each segment is a low-high pair that was encountered in that order (first low, then high) and could be a candidate for the first two values of the solution. This stack starts empty.
• Iterate the input values:
  • Keep track of the least value encountered so far
  • If the current value is not that running minimum, then:
    • as long as the current value is greater than the high-value of the segment at the top of the stack, pop and discard that segment, since that means we have completely encompassed that segment with a new segment.
    • If the current value sits inside the segment at the top of the stack, we have a solution.
    • Otherwise, we have formed a new segment that is disjoint from any stacked segment, and has boundaries that are less than the other segments.

Implementation in runnable JavaScript snippet:

function getTriplet(arr) {
    const n = arr.length;
    let segments = []; // pairs of non-overlapping (low, high) in descending order
    let min = Infinity; // running minimum
    for (const value of arr) {
        if (value < min) {
            min = value; // update minimum encountered so far
        } else if (value > min) {
            // Maybe we make previous segment(s) obsolete
            while (segments.length && value >= segments.at(-1)[1]) {
                segments.pop();  // Discard segment, as new one contains it
            }
            if (segments.length && value > segments.at(-1)[0]) { // Bingo
                return [segments.at(-1)[0], segments.at(-1)[1], value];
            }
            segments.push([min, value]); // Add disjoint, lesser segment
        }
    }
}

// Test case 1:
const arr = [5, 9, 1, 2, 7, 8];
console.log(getTriplet(arr)); // 5 9 8
// Test case 2:
const arr2 = [5, 8, 10, 2, 4];
console.log(getTriplet(arr2)); // undefined: no solution
// Test case 3:
const arr3 = [7, 5, 8, 6, 10];
console.log(getTriplet(arr3)); // 5 8 6
// Test case 4:
const arr4 = [6, 8, 7, 9, 10, 11];
console.log(getTriplet(arr4)); // 6 8 7
// Test case 5:
const arr5 = [8, 10, 5, 7, 2, 4, 10, 11];
console.log(getTriplet(arr5)); // undefined

As a value can only be pushed once on the stack and popped once from it, this algorithm has a O() complexity.

Answer 2

Here is a O(n²) solution in Ruby that can be read as pseudo-code. If there are three ordered values from the array that have the specified properties the indices of one such triple is returned; else nil is returned.

def find_a_peak(arr)
  min_i = 0 # meaning of this variable is explained below
  
  (1..arr.size-2).each do |j| # (1..arr.size-2) denotes a range of indices 

    # min_i equals the index of the smallest value the precedes the 
    # element at index j after the following update is performed
    min_i = j-1 if arr[j-1] < arr[min_i]

    # attempt to find and return an index k > j such that arr[k] falls between
    # arr[min_i] and arr[j]. nil is returned if no element has that property
    k = (j+1..arr.size-1).find { |k| arr[k] > arr[min_i] && arr[k] < arr[j] }

    # We are finished if k is not nil
    return [min_i,j,k] unless k.nil?

    # k = nil. Repeat the loop if j < arr.size - 2; else exit the loop
  end
  
  # return nil, signifying no three elements have the desired property
  nil

end

---

Here are a few test cases.

        arr                   indices     values
__________________________________________________

[3, 2, 1, 3, 4, 6, 2, 7]     [2, 3, 6]   [1, 3, 2]
[1, 2, 3, 4, 5, 6, 7]         nil
[5, 9, 1, 2, 7, 8]           [0, 1, 4]   [5, 9, 7]
[5, 8, 10, 2, 4]              nil
[7, 5, 8, 6, 10]             [1, 2, 3]   [5, 8, 6]
[6, 8, 7, 9, 10, 11]         [0, 1, 2]   [6, 8, 7]
[8, 10, 5, 7, 2, 4, 10, 11]    nil

Here is an example of using Ruby to obtained the values from the indices:

arr = [3, 2, 1, 3, 4, 6, 2, 7]
idx = [2, 3, 6]
arr.values_at(*idx)
  #=> [1, 3, 2]