Find Next Biggest

1. What data structure should we use?

A naive algorithm could be to start from the $0th$ element and go down the array to find the next biggest element, and then we repeat the same procedure for the $1st$ element, $2nd$ element, and all the way till the end of the array. However, this approach will take $O(n^2)$ in an array like $[6, 5, 4, 3, 2, 1]$ since we have to propagate through the entire array each time. In order to improve our runtime from $O(n^2)$ to $O(n)$, we need to use a data structure to keep track of the elements that have not found their next biggest elements yet. This data structure should achieve two goals. First, we will keep an element in this data structure if we have not found a next biggest element for it yet. Second, we will remove the element from the data structure and update the value in the output array if we have found a next biggest element for it; we will also check if this next biggest element we just found is a next biggest element for any other elements in the data structure and update those elements accordingly if so. This way, we only need to propagate through the entire array once. What data structure could help us achieve these two goals? Also, since we could have multiple elements in this data structure, we might lose track of their relative positions. Besides the elements themselves, what other information should we also keep track of?

Part 1: Code it Up

Naive Algorithm

For the naive algorithm we start from the $0th$ element and go down the array to find the next biggest element. If we can find one, we append it to our output array; otherwise, we append $-1$ to our output array. We repeat this same procedure for the $1st$ element, $2nd$ element, and all the way till the end of the array.

Code for the above algorithm can be seen below:

def find_next_biggest_naive(num_list):
    output = []                                 
    i = 0
    #use a while loop to iterate through all elements in the input array                                       
    while (i < len(num_list)):
        #create a flag for each element indicating whether we can find a next biggest element for it                 
        if_next_biggest_exist = False
        j = i + 1 
        #use another while loop to iterate through all elements to the right of the current element                              
        while (j < len(num_list)):
            #if we find a next biggest element, update the output array and the flag
            if num_list[j] > num_list[i]:
                output.append(num_list[j])
                if_next_biggest_exist = True
                break
            j += 1
        #if the lfag is not updated, that means we have not found a next biggest element
        if not if_next_biggest_exist:
            output.append(-1)
        i += 1
    return output

Efficient Algorithm

As suggested in the hint, we will use a stack to keep track of the elements that have not found their next biggest elements yet. The stack stores pairs of index and value as they are in the input array. Every time when we process a new element in the input array, we pop one pair off the stack and compare its value with the new element. If the new element is strictly larger than the value of the pair, the corresponding entry in the output array will be replaced with the new element. We then pop another pair off the stack and compare its value with the new element and update the output array if needed. We repeat this process until there is nothing left on the stack. If the new element is not larger than the value of the pair, we put the pair back on the stack. We now add the current index and current value to the stack together as a pair. We then move on to the next element in the array. After we have propagated through the entire array this way, for every pair on the stack, we get their indices and set the corresponding entires in the output array to $-1$.

Code for the above algorithm can be seen below:

def find_next_biggest_efficient(num_list):
    #copy the input array into the output array
    output = num_list[:]
    #create a stack that keeps track of elements in the format (index, value)
    stack = [(0, num_list[0])]
    i = 1
    #use a while loop to iterate through the entire array
    while (i < len(num_list)):
        #current_val holds the value of the new element in the input array
        current_val = num_list[i]
        #use a while loop to iterate through all elements on the stack
        while stack:
            #pop the pair off top of the stack
            pair = stack.pop()
            #compare the value of the pair to the current value
            if current_val > pair[1]:
                #update the output array
                index = pair[0]
                output[index] = current_val
            else:
                #put the pair back on stack and move on to the next element in the array
                stack += [pair]
                break
        #add the current index and current value to the stack together as a pair
        stack += [(i, num_list[i])]
        i += 1
    #for elements still on the stack, update their corresponding entries in the output array to -1
    while stack:
        pair = stack.pop()
        index = pair[0]
        output[index] = -1
    return output

Part 2: Runtime Analysis

For the naive algorithm, if we are given an array whose elements are listed in decreasing order, we have to propagate through the remaining array for each element in the array. Therefore, the runtime of the naive algorithm is $O(n^2)$.

For the efficient algorithm, by implementing stack in our algorithm, we only need to go through the entire array exactly once. Therefore, the runtime of the efficient algorithm is $O(n)$.

Part 3: Answer to Follow Up Question

In order to output the distance between the current element and the next biggest element, we just need to change one line inside our efficient algorithm. Change output[index] = current_val to output[index] = i - index.