Problem Statement in English

You’re given an array of integers nums.

You can jump from index i to index j if i < j and nums[i] < nums[j]. You can also jump from index i to index j if i > j and nums[j] > nums[i].

Retun an array answer where answer[i] is the maximum value of nums[j] such that you can jump from index i to index j.

Approach

We can either jump directly to a bigger number on the left, or we can jump to a smaller number on the right and use that as a springboard to jump to a bigger number on the left.

For this we need to maintain a list that tells us the smallest number to the right of each index. This way, if we reach a number that is smaller than the smallest number to the right, we know that we cannot jump to any smaller number on the right, and thus we need to jump directly to a bigger number on the left.

And we’re done!

Solution in Python


class Solution:
    def maxValue(self, nums):
        n = len(nums)
        if n == 0: return []
        
        suffix_min = [0] * n
        suffix_min[-1] = nums[-1]
        
        for i in reversed(range(n - 1)):
            suffix_min[i] = min(nums[i], suffix_min[i+1])
        
        ans = [0] * n

        stack = []
        current_max = 0
        
        for i in range(n):
            current_max = max(current_max, nums[i])
            stack.append(i)
            
            if i == n - 1 or current_max <= suffix_min[i + 1]:
                while stack:
                    ans[stack.pop()] = current_max
                
                if i < n - 1:
                    current_max = nums[i + 1]
                    
        return ans

Complexity

  • Time: $O(n)$
    Since we traverse the array a few times.

  • Space: $O(n)$
    Since we store the suffix minimum and the answer array.

Mistakes I Made

I had to look up the stack part - I completely overcomplicated it :(

And we are done.