algoadvance

Leetcode 697. Degree of an Array

Problem Statement

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Clarifying Questions

1. What can we assume about the input array?
   • The array nums will be non-empty and consists of non-negative integers.
2. What should be the output?
   • The length of the smallest contiguous subarray that has the same degree as the original array.
3. Are there any constraints on the size of the array?
   • No specific constraints mentioned. Typically, we can assume it to be up to (10^5) given the nature of array problems on LeetCode.

Strategy

1. Degree Calculation:
   • First, calculate the frequency of each element in the array to determine the degree of the array.
2. Track Occurrences:
   • Use a hash map to store the first and last occurrence (indices) of each element.
3. Find Minimum Length Subarray:
   • Iterate through the frequency map and determine the minimum length of the subarray for elements that have the frequency equal to the degree.

Code

import java.util.HashMap;

class Solution {
    public int findShortestSubArray(int[] nums) {
        // Maps to store the first and last positions, and the count of elements
        HashMap<Integer, Integer> left = new HashMap<>();
        HashMap<Integer, Integer> right = new HashMap<>();
        HashMap<Integer, Integer> count = new HashMap<>();
        
        int degree = 0;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (!left.containsKey(num)) {
                left.put(num, i);
            }
            right.put(num, i);
            count.put(num, count.getOrDefault(num, 0) + 1);
            degree = Math.max(degree, count.get(num));
        }
        
        int minLength = nums.length;
        for (Integer num : count.keySet()) {
            if (count.get(num) == degree) {
                minLength = Math.min(minLength, right.get(num) - left.get(num) + 1);
            }
        }
        
        return minLength;
    }
}

Time Complexity

• Time Complexity: (O(n))
  • We traverse the array three times:
    1. Once to populate the hash maps (left, right, count).
    2. Once to determine the degree.
    3. Once to find the minimum length subarray for elements with the same degree.
  • Hence, each pass over the array contributes to linear complexity.
• Space Complexity: (O(n))
  • We use three hash maps to store occurrences, positions, and counts of elements, which in the worst case will store information for all distinct elements in the array.

This approach efficiently calculates the required smallest subarray with a degree equal to that of the array with optimal time and space usage.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?