23.05.07 Today’s Leetcode

1964. Find the Longest Valid Obstacle Course at Each Position (hard)

TLE at 60/78

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:

        res = []
        dp = {}
        for ob in obstacles:
            temp = 0
            for key in dp.keys():
                if key <= ob:
                    temp = max(temp, dp[key])
        
            dp[ob] = temp + 1 
            res.append(dp[ob])
        
        return res

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        lis = []
        result = []
        for obstacle in obstacles:
            # print(lis)
            idx = bisect_right(lis, obstacle)
            if idx == len(lis):
                lis.append(obstacle)
            else:
                lis[idx] = obstacle
            result.append(idx + 1)
        return result