Count Complete Subarrays in an Array

Another classic two-pointers / sliding-window question.

First, you have to iterate through the array nums to find the number of unique values, unique_count, present.

Simply iterate the r index of the sliding window until there areunique_count numbers present, keeping track of the number of occurences of a number in the sliding window using the hash-map mp. When iterating through the array nums, we can simply increment mp[nums[r]] and check if this is the first instance of the number inside the sliding window.

Then, if there are unique_count unique numbers present, we can add nums.size() - r + 1 to the count of subarrays with the maximum number of unique numbers present. Finally, before we increment our l index, we decrement mp[nums[l]] and then decrement our count of unique numbers present in the sliding window if that was the last occurence, before repeating this all over again until either the r index exceeds the length of the array or the number of unique numbers is smaller than unique_count.

code

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        int mp[2001] = {0};
        int unique_count = 0;
        for (int num : nums) {
            if (mp[num] == 0) {
                ++unique_count;
                ++mp[num];
            }
        }
        memset(mp, 0, sizeof(mp));
        int l = 0, r = 0, counter = 0, ans = 0;
        for (;r < nums.size() || counter == unique_count;) {
            for (; r < nums.size() && counter < unique_count; ++r) {
                if (mp[nums[r]] == 0) {
                    ++counter;
                }
                ++mp[nums[r]];
            }
            if (counter == unique_count) {
                ans += nums.size()-r+1;
            }
            --mp[nums[l]];
            if (mp[nums[l]] == 0) {
                --counter;
            }
            ++l;
        }
        return ans;
    }
};

complexity

• Time: O(n), where n denotes the size of the array nums
• Space: O(n)

learnings

• you can use memset(unique_count, 0, sizeof(unique_count)) to reset the values inside of an automatically-allocated array quickly
  • you can also use memset(unique_count, 0, sizeof(N*unique_count)) to reset the values inside of a heap-allocated array quickly

time taken

• i forgot to press the timer, but believe me it took less than 5 minutes...