LC-2420 Medium LeetCode

2420. Find All Good Indices

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 40% Topics: Array, Dynamic Programming, Prefix Sum

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

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

Solution from kamyu104/LeetCode-Solutions · MIT