Distinct Numbers in Window

Practice Link

You are given an array of N integers, A1, A2 ,..., AN and an integer B. Return the of count of distinct numbers in all windows of size B.

Formally, return an array of size N-B+1 where i'th element in this array contains number of distinct elements in sequence Ai, Ai+1 ,..., Ai+B-1.

NOTE: if B > N, return an empty array.

Brute Force - Set#

For every window starting at index i, use an inner loop to insert all B elements of the window into a hash set, then record the set's size as the distinct count. Rebuilding the set from scratch for each window is O(N×B), which degenerates to O(N²) for large windows.

vector<int> Solution::dNums(vector<int> &A, int B) {
    vector<int> result;
    if(B>A.size())
        return result;
        
    for(int i=0;i<A.size()-B+1;i++)
    {
        unordered_set<int> s;
        for(int j=0;j<B;j++)
        {
            s.insert(A[i+j]);
        }
        result.push_back(s.size());
        
    }
    return result;
    
}

Time Complexity: O(N x B) -> O(N^2) -> TLE for large N

Space Complexity: O(N)

Better Approach - Sliding Window + unordered Map#

Instead of rebuilding from scratch, slide the window by one position at a time. Use a frequency map and a running distinctCount. When the outgoing element's count drops to 1 before removal (its last occurrence leaves the window), decrement distinctCount. When the incoming element's count was 0 (first occurrence in the window), increment distinctCount. This amortizes to O(1) per slide step and O(N) overall.

vector<int> Solution::dNums(vector<int> &A, int B) {
    vector<int> result;
    if(B>A.size())
        return result;
        
    unordered_map<int,int> freq;
    int distinctCount = 0;
        
    for(int i=0;i<B;i++)
    {
        if(freq[A[i]]==0)
            distinctCount++;
        freq[A[i]]++;
    }
    result.push_back(distinctCount);
        
    for(int i=B;i<A.size();i++)
    {
        //removing outgoing freq
        if(freq[A[i-B]]==1)
            distinctCount--;
        freq[A[i-B]]--;
        
        //adding new freq
        
        if(freq[A[i]]==0)
            distinctCount++;
        freq[A[i]]++;
        result.push_back(distinctCount);
        
    }
    return result;
    
}

Time Complexity: O(N)

Space Complexity: O(N)

Other Optimization#

• If the input elements are bounded within a small range, we can replace map with fixed size array. (faster & less memory overhead).