Three increasing numbers such that i
Puzzle: Given an array of integers, find three indexes i,j,k such that i<j<k and arr[i]<arr[j]<arr[k]
Solution:
As always, solving a smaller problem always sheds more light on solving the bigger problem.
If only two such variables were to be found, then its pretty simple.
Just keep track of the minimum element till now and whenever a higher element is found, print the pair.
Note that the problem is to find just any one such pair, not all the pairs.
Similarly, to find any one such triplet, we have to keep track of two minimums - arr[i] and arr[j] till arr[k] is found.
However, after two minimums have been selected and a new all-time minimum is found, how to handle that?
It is important to handle this all-time minimum because all the remaining numbers may be smaller than the current two minimums but may be larger than this all-time minimum.
For example:
This is solved by storing this new minimum as a potential start of a new series.
If another number is found which is less than the series started by current two minimums but is larger than potential minimum, then we can discard the current series in favor of current number and the previous all-time minimum.
Read full article from Three increasing numbers such that i
Puzzle: Given an array of integers, find three indexes i,j,k such that i<j<k and arr[i]<arr[j]<arr[k]
Solution:
As always, solving a smaller problem always sheds more light on solving the bigger problem.
If only two such variables were to be found, then its pretty simple.
Just keep track of the minimum element till now and whenever a higher element is found, print the pair.
Note that the problem is to find just any one such pair, not all the pairs.
Similarly, to find any one such triplet, we have to keep track of two minimums - arr[i] and arr[j] till arr[k] is found.
However, after two minimums have been selected and a new all-time minimum is found, how to handle that?
It is important to handle this all-time minimum because all the remaining numbers may be smaller than the current two minimums but may be larger than this all-time minimum.
For example:
[ 20, 30, 5, 6, 1, 7 ]
¶cursor
current-series = 20,30
new minimum = 5
This is solved by storing this new minimum as a potential start of a new series.
If another number is found which is less than the series started by current two minimums but is larger than potential minimum, then we can discard the current series in favor of current number and the previous all-time minimum.
Read full article from Three increasing numbers such that i
