How to optimise a strictly increasing stack based list

Leo Baby Jacob 0
Viewed 54

So I am trying to solve https://leetcode.com/problems/daily-temperatures Basically given an array [30,40,50,60] we need to return the indices of the next increasing value so output would be [1,1,1,0] My algorithm is to

  1. while end !=0 read from the array
  2. if last element add 0 to output and stack
  3. Else if temperature[end] > stack top add to stack and add stack top to be the temperature difference.
  4. If temperature[end] <= stack top then we pop every element until this condition breaks and update the stack top and output.

I keep getting a time limit exceeded here, My understanding here is that the complexity is O(N). I am not sure how to optimise it further.

def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        output = []
        r = len(temperatures) - 1
        stack = []
        while r >= 0:
            if r == len(temperatures) - 1:
                stack.append(r)
                output.insert(0, 0)
            else:
                if temperatures[stack[-1]] > temperatures[r]:
                    output.insert(0, stack[-1]-r)
                    stack.append(r)
                else:
                    while stack and temperatures[stack[-1]] <= temperatures[r]:
                        stack.pop()
                    if len(stack) == 0:
                        output.insert(0, 0)
                        stack.append(r)
                    else:
                        output.insert(0, stack[-1]-r)
                        stack.append((r))

            r -= 1
        return output
stack data-structures algorithm python
3 Answers

An efficient implementation of a slow algorithm will still scale slowly. Optimizing the stack won't change the big-O. But I'll outline an idea using a different data structure for you to figure out.

In example1 of the problem you start with the array [73,74,75,71,69,72,76,73]. Let's arrange this in terms of maxes of ranges like so:

x = [
    [73,74,75,71,69,72,76,73],
    [   74,   75,   72,   76],
    [         75,         76],
    [                     76],
]

In other words x[i][j] gives the max of all elements from j * 2**i to (j+1) * 2**i - 1.

Now to find the first rise after k we go "forward and down" until we find a block with a larger (or 0 if there is none) and then "up and forward" until we find where it is. Where:

while going forward and down at (i, j): if j is even: if j not at end of x[i]: move to (i, j+1) then test else: answer is 0 else: move to (i+1, j//2 + 1) then test

while going up and forward at (i, j) with 0 < i: if answer in range for (i-1, j+j): move to (i-1, j+j) else: move to (i-1, j+j+1)

For example if k was 2 we would do this.

start at (0, 2)
go f&d to (0, 3), check if 75 < x[0][3] (ie 71), stay f&d
go f&d to (1, 2), check if 75 < x[1][2] (ie 72), stay f&d
go f&d to (1, 3), check if 75 < x[1][3] (ie 76), switch to u&f
check if 75 < x[0][6] (ie 76) go u&f to (0, 6)

And now we know that the next one is at position 6. So we get 6 - 2 == 4 there.

What is the performance? The whole data structure is O(n) to build. Each lookup is at worst O(log(n)). So doing the n checks is at worst O(n log(n)). Which should be fast enough.

btilly0

After considerable testing, your answer IS linear. (And therefore better than what I suggested before.) However in order to meet their time limit you need to microptimize everything. Meaning get rid of every unneeded if, make sure your comparisons are the fastest possible, etc.

I would definitely say that leetcode set the time limit too restrictively for the problem and language performance.

def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    if 0 == len(temperatures):
        return []
    output = [0]
    r = len(temperatures) - 1
    stack = [r]
    r -= 1
    while r >= 0:
        while len(stack) and temperatures[stack[-1]] <= temperatures[r]:
            stack.pop()
        if len(stack) == 0:
            output.append(0)
        else:
            output.append(stack[-1]-r)
        stack.append((r))
        r -= 1
    output.reverse()
    return output
btilly0

My Solution is

def dailyTemperatures(self, temperatures):
    res = []
    i = 0
    while i < len(temperatures) - 1:
        j = i + 1
        while True:
            if j >= len(temperatures):
                res.append(0)
                break
            if temperatures[j] <= temperatures[i]:
                j += 1
            else:
                res.append(j - i)
                break
        i += 1
    res.append(0)
    return res
ahtasham nazeer0
Related