Pattern 132 and sequential runs

Pattern 132

We are given a list of integers @list and asked to find a triad i, j, k such that $i < $j < $k, and $list[$i] < $list[$k] < $list[$j]. If none exists we are to say so, and if several exist we are to show the first one we find.

The obvious solution is to iterate over i, j and k in three nested loops, and that will find the answer. For the given examples, it will do so very quickly.

However, I created a 'hard' list comprising 1 .. 10000, 9999. The (only) 132 triad in this list is 1, 10000, 9999, and to do it the obvious way as described above takes 10s of seconds. 

Is there a better way? Given that this has been set as a challenge, the answer must be yes!

First let's note that $list[$j] has to be larger than either $list[$i] or $list[$k]. 

So if we loop $j from 1 to $last - 1, we are looking for a $list[$i] which is less than $list[$j] and occurs where $i < $j. If no such element exists we can move on to the next $j without worrying about $k.

If we do find a possible $list[$i] we then need to see if there is a $list[$k] which is also less than $list[$j] but where $k >$j. If we find one, then we have the solution.

If we still haven't found a solution, then none exists.

For my hard list, this ran in under 10 seconds.

Consecutive array slices

We are given a sorted unique integer array, @array and are asked to find all the slices of this array which comprise consecutive integers, and output the first and last element in each such slice.

Let's iterate through @array and have two persistent variables: $start, the value at the start of  a consecutive subsequence and a state boolean variable $in_slice which indicates whether we are in a consecutive subsequence or not - initialised to false.

So if $j is the index:

• if not $in_slice, see if $array[$j + 1 == $array[$j] + 1, and if so set $start = $j and set in_slice to true
• else if $in_slice, see if $array[$j] + 1 == $array[$j] + 1, and if not, record the end of a slice and set in_slice to false

This works fine, except that at the very last array element, $array[$j + 1] won't exist. Obviously we could check for this, but I avoided the issue by adding an element at the end of array equal to the supplied last one + 2, and iterating $j only up to the second last element.

This is a bit messy and I'm looking forward to someone having a more elegant solution.