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. Can the elements of the array be negative?
    • No, the problem states that the array contains non-negative integers.
  2. What is the expected range for the length of the array?
    • The problem does not specify this, but typical constraints might be up to about 10^5 elements.
  3. Can there be multiple valid subarrays with the same degree?
    • Yes, but the task is to find the length of the smallest one.

Strategy

The strategy involves several steps:

  1. Calculate the Frequency of Each Element: Create a hashmap to count the frequency of each element.
  2. Determine the Degree of the Array: This is the maximum value from the frequency hashmap.
  3. Track the First and Last Occurrence: Create two additional hashmaps to store the first and last occurrence of each element in the array.
  4. Find the Smallest Subarray: Iterate through the hashmap of frequencies and for elements that match the degree, compute the length of the subarray from the first to the last occurrence and keep track of the minimum length.

Code

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int findShortestSubArray(vector<int>& nums) {
    unordered_map<int, int> freq, first, last;
    int degree = 0, minLength = nums.size();
    
    // Calculate frequency and track first and last occurrence
    for (int i = 0; i < nums.size(); ++i) {
        int num = nums[i];
        if (first.find(num) == first.end()) {
            first[num] = i;
        }
        last[num] = i;
        freq[num]++;
        
        degree = max(degree, freq[num]);
    }
    
    // Find the smallest subarray with the same degree
    for (const auto& entry : freq) {
        if (entry.second == degree) {
            int num = entry.first;
            int length = last[num] - first[num] + 1;
            minLength = min(minLength, length);
        }
    }
    
    return minLength;
}

int main() {
    vector<int> nums = {1, 2, 2, 3, 1, 4, 2};
    cout << "The length of the smallest subarray with the same degree is " << findShortestSubArray(nums) << endl;
    return 0;
}

Time Complexity

The time complexity of the solution is O(n), where n is the length of the input array.

Thus, the approach ensures efficient processing and meets typical constraints expected in coding interviews.

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