Find Increasing Triplet Subsequence - Medium

Problem - Given an integer array A[1..n], find an instance of i,j,k where 0 < i < j < k <= n and A[i] < A[j] < A[k].

Let's start with the obvious solution, bruteforce every three element combination until we find a solution.

	def find_triple(arr): #O(n^3)/O(1)
	N = len(arr)
	for i in xrange(N):
	for j in xrange(i+1,N):
	for k in xrange(j+1,N):
	if arr[i] < arr[j] < arr[k]:
	return arr[i],arr[j],arr[k]
	return None

view raw gistfile1.txt hosted with ❤ by GitHub

Let's try to reduce this by searching left and right for each element, we search left for an element smaller than the current one, towards the right an element greater than the current one. When we find an element that has both such elements, we found the solution. The complexity of this solution is O(n^2).

	def find_triple(arr): #O(n^2)/O(1)
	N = len(arr)
	for i in xrange(N):
	left = None
	for j in xrange(i - 1, -1, -1):
	if arr[i] > arr[j]:
	left = j
	break
	right = None
	for j in xrange(i + 1, N):
	if arr[i] < arr[j]:
	right = j
	break
	if left and right:
	return arr[left],arr[i],arr[right]
	return None

view raw gistfile1.txt hosted with ❤ by GitHub

To reduce this even further, One can simply apply the longest increasing subsequence algorithm and break when we get an LIS of length 3. But the best algorithm that can find an LIS is O(nlogn) with O( n ) space.

An O(nlogn) algorithm seems like an overkill! Can this be done in linear time?

The Algorithm:
We iterate over the array and keep track of two things.

• The minimum value iterated over (min)
• The minimum increasing pair (a,b) where min <= a < b

When we encounter an element, say v,  that is greater than the increasing pair we return (a,b,v).

Here's my Python implementation to make my point.

	def find_triple(arr): #O(n)/O(1)
	mn = a = arr[0]
	b = None
	for v in arr[1:]:
	if mn >= v: # v is the new minimum
	mn = v
	elif b == None or b > v: # v > min but less than earlier 'b'
	a,b = mn,v
	else: # v > b > a
	return a,b,v
	return None

view raw gistfile1.txt hosted with ❤ by GitHub

Until next time, Cheers!