LeetCode-Solutions/Python/smallest-stable-index-i.py at master · kamyu104/LeetCode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# Time:  O(n)
# Space: O(n)

# prefix sum
class Solution(object):
    def firstStableIndex(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        right = [float("inf")]*(len(nums)+1)
        for i in reversed(xrange(len(nums))):
            right[i] = min(right[i+1], nums[i])
        left = 0
        for i in xrange(len(nums)):
            left = max(left, nums[i])
            if left-right[i] <= k:
                return i
        return -1


# Time:  O(n)
# Space: O(n)
# prefix sum
class Solution2(object):
    def firstStableIndex(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        left = [0]*(len(nums)+1)
        for i in xrange(len(nums)):
            left[i+1] = max(left[i], nums[i])
        right = [float("inf")]*(len(nums)+1)
        for i in reversed(xrange(len(nums))):
            right[i] = min(right[i+1], nums[i])
        return next((i for i in xrange(len(nums)) if left[i+1]-right[i] <= k), -1)