Python O(n) concise with explanation (two approaches)


  • 2

    Firstly, group each num and collect the index it appears into a list. The list with the longest length will be the degree of the array.

    Next loop through each of the lists, only those lists with the same length as the degree will qualify. We simply take difference between the first and last value of each qualifying lists to find the length of such a possible subarray .

    For example if we have [1, 1, 2, 2, 2, 3, 1], after grouping by value:

    [1, 1, 2, 2, 2, 3, 1] => { 1: [0, 1, 6], 2: [2, 3, 4], 3: [4] }, degree: 3

    Only have to consider values where the length == degree:

    • 1: [0, 1, 6] => subarray length: (6 - 1) + 1 = 7
    • 2: [2, 3, 4] => subarray length: (4 - 2) + 1 = 3 (Winner!)
    class Solution(object):
        def findShortestSubArray(self, nums):
            nums_map, deg, min_len = collections.defaultdict(list), 0, float('inf')
            for index, num in enumerate(nums):
                nums_map[num].append(index)
                deg = max(deg, len(nums_map[num]))
            for num, indices in nums_map.items():
                if len(indices) == deg:
                    min_len = min(min_len, indices[-1] - indices[0] + 1)
            return min_len
    

    Another solution that just requires one for loop:

    class Solution(object):
        def findShortestSubArray(self, nums):
            nums_map, deg, min_len = collections.defaultdict(list), 0, float('inf')
            for index, num in enumerate(nums):
                nums_map[num].append(index)
                if len(nums_map[num]) == deg:
                    min_len = min(min_len, nums_map[num][-1] - nums_map[num][0] + 1)
                elif len(nums_map[num]) > deg:
                    deg = len(nums_map[num])
                    min_len = nums_map[num][-1] - nums_map[num][0] + 1
            return min_len
    

    - Yangshun


Log in to reply
 

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