Question

I NEED AN NLOGN OR LINEAR SOLUTION TO THIS PROBLEM!

I NEED A FASTER SOLUTION THAN THE ONE GIVEN BELOW!! The solution below runs in quadratic time, I need one faster than this.

I REPEAT I NEED A FASTER SOLUTION!! THE SOLUTION GIVEN BELOW IS TOO SLOW!

Slow Solution:

def predictAnswer(stockData, queries):
    stockData = [0] + stockData
    length = len(stockData)
    ans = []
    for q in queries:
        l = q-1
        r = q+1
        flag = True
        while l > 0 or r < length:
            if l > 0 and stockData[l] < stockData[q]:
                ans.append(l)
                flag = False
                break
            if r < length and stockData[r] < stockData[q]:
                ans.append(r)
                flag = False
                break
            l -= 1
            r += 1
        if flag:
            ans.append(-1)
    return ans

Question:

The function predictAnswer should be made based on the following.

In the prediction game, the first player gives the second player some stock market data for some consecutive days. The data contains a company's stock price on each day. The rules for the game are:

1. Player 1 will tell player 2 a day number
2. Player 2 has to find the nearest day on which stock price is smaller than the given day
3. If there are two results, then player 2 finds the day number which is smaller
4. If no such day exits, then the answer is -1.

Example 1;

stockData size n =10;

stockData = [5,6,8,4,9,10,8,3,6,4]

queries = [6,5,4]

Result is [5,4,8]

On day 6, the stock price is 10. Both 9 and 8 are lower prices one day away. Choose 9 (day 5) because it is before day 6. On day 5, the stock price is 9. 4 is the closest lower price on day 4. On day 4, the stock price is 4. The only lower price is on day 8. The return array is [5,4,8]

Example - 2

stockData size n = 10

stockData = [5,6,8,4,9,10,8,3,6,4]

queries = [3,1,8]

Result is [2,4,-1]

If the day number is 3.both days 2 and 4 are smaller.choose the earlier day,day 2.

If the day number is 1,day 4 is the closet day with a smaller price.

If the day number is 8,there is no day where the price is less than 3.

The return array is [2,4,-1]

/*

     * Complete the 'predictAnswer' function below.

     *

     * The function is expected to return an INTEGER_ARRAY.

     * The function accepts following parameters:

     *  1. INTEGER_ARRAY stockData

     *  2. INTEGER_ARRAY queries

     */

def predictAnswer(stockData, queries):

Answer 1

We maintain two stacks, one for left side and the other for right side to calculate the answer.

Algorithm: 
Start from the first stock and do this for all the stocks
a) If stack is empty or stockData[i] is higher than the stockPrice at top of stack, then push ‘i’ to stack.
b) If this stockPrice is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater.

Runtime complexity:

Space complexity:

import sys

def predictAnswer(stockData, queries):
    n = len(stockData)
    left = [0] * n
    right = [0] * n

    # Implementing stack using list
    stack = list()

    # Processing minimum stack for left side
    for i, stock in enumerate(stockData):
        while len(stack) != 0 and stock <= stockData[stack[-1]]:
            stack.pop()
        if len(stack) == 0:
            left[i] = -2
        else:
            left[i] = stack[-1]
        stack.append(i)

    # Re initializing stack
    stack = list()

    # Processing minimum stack from right side
    for i, stock in reversed(list(enumerate(stockData))):
        while len(stack) != 0 and stock <= stockData[stack[-1]]:
            stack.pop()
        if len(stack) == 0:
            right[i] = -2
        else:
            right[i] = stack[-1]
        stack.append(i)

    ans = [0] * len(queries)

    for i, query in enumerate(queries):
        ans[i] = -1
        diff = sys.maxsize
        if left[query - 1] != -2:
            ans[i] = left[query - 1] + 1
            diff = query - 1 - left[query - 1]
        if right[query-1] != -2 and diff > right[query - 1] - query + 1:
            ans[i] = right[query - 1] + 1
    return ans


# Driver code
if __name__ == "__main__":
    # stockData = [5, 6, 8, 4, 9, 10, 8, 3, 6, 4]
    # queries = [6, 5, 4]
    # stockData = [5, 6, 8, 4, 9, 10, 8, 3, 6, 4]
    # queries = [3, 1, 8]
    # stockData = [2, 4, 5, 1]
    # queries = [3]
    stockData = [1, 6, 5, 1]
    queries = [3]
    print(predictAnswer(stockData, queries))