2799. Count Complete Subarrays in an Array

Description

You are given an array nums consisting of positive integers.

We call a subarray of an array complete if the following condition is satisfied:

The number of distinct elements in the subarray is equal to the number of distinct elements in the whole array.

Return the number of complete subarrays.

A subarray is a contiguous non-empty part of an array.

Example 1:

Input: nums = [1,3,1,2,2]
Output: 4
Explanation: The complete subarrays are the following: [1,3,1,2], [1,3,1,2,2], [3,1,2] and [3,1,2,2].

Example 2:

Input: nums = [5,5,5,5]
Output: 10
Explanation: The array consists only of the integer 5, so any subarray is complete. The number of subarrays that we can choose is 10.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 2000

Solutions

Solution 1: Hash Table + Enumeration

First, we use a hash table to count the number of distinct elements in the array, denoted as \(cnt\).

Next, we enumerate the left endpoint index \(i\) of the subarray and maintain a set \(s\) to store the elements in the subarray. Each time we move the right endpoint index \(j\) to the right, we add \(nums[j]\) to the set \(s\) and check whether the size of the set \(s\) equals \(cnt\). If it equals \(cnt\), it means the current subarray is a complete subarray, and we increment the answer by \(1\).

After the enumeration ends, we return the answer.

Time complexity: \(O(n^2)\), Space complexity: \(O(n)\), where \(n\) is the length of the array.

Python3JavaC++GoTypeScriptRust

class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        cnt = len(set(nums))
        ans, n = 0, len(nums)
        for i in range(n):
            s = set()
            for x in nums[i:]:
                s.add(x)
                if len(s) == cnt:
                    ans += 1
        return ans

class Solution {
    public int countCompleteSubarrays(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int x : nums) {
            s.add(x);
        }
        int cnt = s.size();
        int ans = 0, n = nums.length;
        for (int i = 0; i < n; ++i) {
            s.clear();
            for (int j = i; j < n; ++j) {
                s.add(nums[j]);
                if (s.size() == cnt) {
                    ++ans;
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int cnt = s.size();
        int ans = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            s.clear();
            for (int j = i; j < n; ++j) {
                s.insert(nums[j]);
                if (s.size() == cnt) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

func countCompleteSubarrays(nums []int) (ans int) {
    s := map[int]bool{}
    for _, x := range nums {
        s[x] = true
    }
    cnt := len(s)
    for i := range nums {
        s = map[int]bool{}
        for _, x := range nums[i:] {
            s[x] = true
            if len(s) == cnt {
                ans++
            }
        }
    }
    return
}

function countCompleteSubarrays(nums: number[]): number {
    const s: Set<number> = new Set(nums);
    const cnt = s.size;
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        s.clear();
        for (let j = i; j < n; ++j) {
            s.add(nums[j]);
            if (s.size === cnt) {
                ++ans;
            }
        }
    }
    return ans;
}

use std::collections::HashSet;

impl Solution {
    pub fn count_complete_subarrays(nums: Vec<i32>) -> i32 {
        let mut s = HashSet::new();
        for &x in &nums {
            s.insert(x);
        }
        let cnt = s.len();
        let n = nums.len();
        let mut ans = 0;

        for i in 0..n {
            s.clear();
            for j in i..n {
                s.insert(nums[j]);
                if s.len() == cnt {
                    ans += 1;
                }
            }
        }

        ans
    }
}

Solution 2: Hash Table + Two Pointers

Similar to Solution 1, we can use a hash table to count the number of distinct elements in the array, denoted as \(cnt\).

Next, we use two pointers to maintain a sliding window, where the right endpoint index is \(j\) and the left endpoint index is \(i\).

Each time we fix the left endpoint index \(i\), we move the right endpoint index \(j\) to the right. When the number of distinct elements in the sliding window equals \(cnt\), it means that all subarrays from the left endpoint index \(i\) to the right endpoint index \(j\) and beyond are complete subarrays. We then increment the answer by \(n - j\), where \(n\) is the length of the array. Afterward, we move the left endpoint index \(i\) one step to the right and repeat the process.

Time complexity: \(O(n)\), Space complexity: \(O(n)\), where \(n\) is the length of the array.