Skip to content
Katabench
Try free

Degree of an Array

Medium About 20 min Free, no account needed

Find the shortest contiguous slice whose most-frequent-element count matches the whole array.

The brief

The degree of an array is the maximum number of times any single value appears in it. Given a non-empty array nums of non-negative integers, return the length of the shortest contiguous subarray that has the same degree as nums.

For [1, 2, 2, 3, 1] the degree is 2 (both 1 and 2 appear twice). The shortest slice that still reaches degree 2 is [2, 2], so the answer is 2.

The performance bar

The obvious approach inspects every possible subarray, O(n^2) or worse. The hidden test has 200,000 elements, so that approach is too slow. You will need to answer it without re-examining every slice.

Starter code

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

public class Solution
{
    // TODO: return the length of the shortest contiguous subarray whose degree equals the array's degree.
    public int ShortestSubarrayWithSameDegree(int[] nums)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Hash maps and sets
Trade memory for constant-time lookups, membership tests and frequency counts.

Related katas