Python solution with detailed explanation

  • 1

    Degree of an Array

    Two Pointer Solution

    • First compute the degree of the array.
    • Then use start and end as two pointers. Initialize start as 0 and extend end till we get a solution. Then reduce start to optimize the solution.
    • O(N) time and O(N) space.
    from collections import Counter, defaultdict
    class Solution:
        def findShortestSubArray(self, nums):
            :type nums: List[int]
            :rtype: int
            if nums == []:
                return 0
            degree = max(Counter(nums).values())
            so_far = defaultdict(int)
            min_size = len(nums)
            start, end = 0, len(nums)-1
            for end, num in enumerate(nums):
                so_far[num] += 1
                while start <= end and so_far[num] == degree:
                    min_size = min(min_size, end-start+1)
                    so_far[nums[start]] -= 1
                    start += 1
            return min_size

    Store start and end indices to optimize range

    • In the first pass, preprocess the input so that we have the frequency of each number, start index and end index. In addition, we can also compute the degree.
    • In the second pass, scan the table again, and minimize the range.
    • O(N) time and space.
    class Solution:
        def findShortestSubArray(self, nums):
            :type nums: List[int]
            :rtype: int
            table, degree, min_range = {}, 0, len(nums)
            for idx, num in enumerate(nums):
                v = table.setdefault(num, [0, None, None])
                v[0] += 1
                if v[1] is None: v[1]= idx
                v[2] = idx
                degree = max(degree, v[0])
            return min(v[2]-v[1]+1 for k,v in table.items() if v[0]==degree)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.