Simple Python Solution


  • 0
    L

    1- First loop is to get the max degree of array while we keep track of min index and max index for the number.
    2- In second step, we consider numbers that have maximum degree and find the number with minimum interval.

    class Solution(object):
        def findShortestSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            #if len(nums)==1: return 1
            cd = {}
            degree = 0
            for i in range(0, len(nums)):
                if nums[i] not in cd:
                    cd[nums[i]] = [1, [i,-1]] # [count, [start_index, end_index]]
                else:
                    val = cd[nums[i]]
                    val[0]+=1
                    val[1][1]=i
                    cd[nums[i]]=val
                    degree = max(degree, val[0])
            min_int = sys.maxint
            for k,v in cd.iteritems():
                if v[0]==degree and v[1][1]!=-1: # second check for nums where no duplicate. nums=[1,2]
                    min_int= min(min_int, v[1][1]-v[1][0]+1)
            if min_int!=sys.maxint:
                return min_int
            else:
                return 1
    

Log in to reply
 

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