Stock

You are given an array of stock market values over different days. Return an array as a result which gives the span of the stock value for that day. A span is the number of preceding days from the current day, for which the stock market value was lower. The picture below shows the span for various days

Stock:



Input -> {7,5,4,6,9}

Output -> {-1,1,1,3,-1}

Day 1: No previous days result is -1.
Day 3: On Day 2 the value was 5. Only day 4 is considered for the span which results in 1.
Day 4: Day3 and 2 have a value lower than 6 so they are included in the span. Result -> 3
Day 5: Best stock market day. Must return -1 since there is no day before day 1.

Can this be done better than O(N2) time.

Hint -> What property of day 4 must be used so that unnecessary comparisons can be avoided ? Is it even necessary to compare day 2 and 3 ? If we can save a reference to all the days whose comparisons would yield the correct result it will help with the time constrain.

Hint -> It can be done with a stack in O(N) time.

Spoiler -> http://thinkcs.googlecode.com/svn/trunk/src/com/util/Stock.java

Test cases -> http://thinkcs.googlecode.com/svn/trunk/src/com/tests/TCStockTest.java