O(log n) Search in a sorted python dictionary

user_7654532 0
Viewed 1201

I'm solving a programming question and stuck on the last piece of the puzzle.

This is the question: https://leetcode.com/problems/daily-temperatures/

I have a sorted (for values) dictionary and now I want to do a log(n) complexity search on the dictionary. Here's the code I have written so far.

def dailyTemperatures(self, T):
    if len(T) == 0:
        return []
    if len(T) == 1:
        return [0]
    
    R = [None] * len(T)
    
    #create map, populate map
    M = {}
    for i in range(0, len(T)):
        M[i] = T[i]
    
    #sort map by value(temps)
    MS = sorted(M.items(), key=lambda x: x[1])
    
    for i in MS:
        print(i[0], i[1])
    
    for i in range(0,len(T)):
        t = T[i]    #base value for comparison
        
        R[i] = 0
        x = 0
        
        # find smallest x for which temp T[x] > T[i]
        # Dictionary is sorted for Temps
        
        R[i] = x - i
        
    return R

The commented part in the loop is where I have trouble. I could not find an answer anywhere which would search a sorted dictionary and then filter by key.

Any tips or new suggestions to tackle this are also appreciated.

search sorting python
1 Answers

Your code could possibly be made to work, but: This algorithm is really just adding more layers of complexity on top of the naive brute force bubble sort-like algorithm, due to needing to backtrack for indexes.

Simplest modification is just to search for the minimum index > than current index. Store the position in the dict's .items() as part of the value so you can retrieve it. But, you can't binary search on index, because it is sorted by value, and index is not in order. This should give you an acceptable O(N) lookup.

You still have to search by index in the end (which has priority over temperature). Even with binary search, your attempted algorithm, ignoring the N log N complexity of pre-sorting, would at best still require O(N * log N * log N) for searching. Your current attempt would actually be O(N^2 log N), but with a third cached index table, nearest index lookup could be turned into log N.

It will be a very convoluted and inefficient algorithm, due to basically having to backtrack your search order. And it will have no advantage over a naive brute force (it's objectively worse).
Note: key point is that you need the nearest index, which is not in sorted order if you sort by value
If you still want to do it that way (I guess as a code golf challenge), you will want to add its position index in .items() of the dict to your dictionary, so when you look up your key in dict, you can find which starting position to start your search through the temperature sorted list. To get the log N, you will need to store each range of temperatures and their range of indexes. This part will probably be particularly complicated to implement. And of course you'll need to implement a binary search algorithm.

Stack algorithm:
Basic idea of below algorithm is that any lower temperatures that follow no longer matter.
eg: [...] 10 >20< 9 6 7 21. After 20; 9 6 7 (or anything <= 20) do not matter. After 9; 6 and 7 don't matter. etc.

So iterate from the end, adding numbers to the stack, popping off the stack numbers less than the current number.

Note that because the number of temperates is bound to 70 values, and numbers less than the current temperature are pruned off the stack at each iteration, both the complexity of searching for the next temperature, and the size of the stack, is bound to 70. In other words constant.
So for each item in T, you will search a maximum of 70 values in the worst case, ie: len(T) * 70. Thus the complexity of the algorithm is O(N): number of items in T.

def dailyTemperatures(T):
    res = [0]*len(T)
    stack = []
    for i, x in reversed([*enumerate(T)]):
        if len(stack) < 1:
            stack.append((i,x))
        else:
            while(len(stack)>0 and stack[-1][1]<=x):
                stack.pop()
            if len(stack)>0 and stack[-1][1]>x:
                res[i] = stack[-1][0] - i
                print(x, stack)
            stack.append((i,x))
    return res

print(dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
user_1202420
Related