Problem of The Day: TDegree of an Array

3 min read 718 words

Problem Statement

leetcode problem link

Solution [accepted]

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        freq = defaultdict(int)
        indices = defaultdict(list)
        max_freq = 0
        for i, num in enumerate(nums):
            freq[num] += 1
            if max_freq < freq[num]:
                max_freq = freq[num]
            indices[num].append(i)

        res = float('inf')
        for k, v in freq.items():
            if v == max_freq:
                length = indices[k][-1] - indices[k][0] + 1
                res = min(res, length)

        return res

// C#
using System;
using System.Collections.Generic;

public class Solution
{
    public int FindShortestSubArray(int[] nums)
    {
        // Maps: value -> count, first index, last index
        var count = new Dictionary<int, int>();
        var first = new Dictionary<int, int>();
        var last = new Dictionary<int, int>();

        int degree = 0;

        for (int i = 0; i < nums.Length; i++)
        {
            int x = nums[i];

            if (!first.ContainsKey(x))
            {
                first[x] = i;
            }
            last[x] = i;

            if (!count.ContainsKey(x))
            {
                count[x] = 0;
            }
            count[x]++;

            if (count[x] > degree)
            {
                degree = count[x];
            }
        }

        int ans = nums.Length;
        foreach (var kvp in count)
        {
            int x = kvp.Key;
            if (kvp.Value == degree)
            {
                int length = last[x] - first[x] + 1;
                if (length < ans)
                {
                    ans = length;
                }
            }
        }

        return ans;
    }
}

• time: O(n)
• space: O(n)

Editorial

Left and Right Index [Accepted]

class Solution(object):
    def findShortestSubArray(self, nums):
        left, right, count = {}, {}, {}
        for i, x in enumerate(nums):
            if x not in left:
                left[x] = i
            right[x] = i
            count[x] = count.get(x, 0) + 1

        ans = len(nums)
        degree = max(count.values())
        for x in count:
            if count[x] == degree:
                ans = min(ans, right[x] - left[x] + 1)

        return ans