# Python solution with detailed explanation

• Degree of an Array https://leetcode.com/problems/degree-of-an-array/description/

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)
``````

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