Skip to content

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

Thinking

A complete subarray contains every distinct value of the original array. Building a set for every pair of ends is acceptable at \(n\le 1000\).

Compute the global number of distinct values \(cnt\), then for each left end grow a set rightward and count a complete subarray whenever the set size reaches \(cnt\).

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

Thinking

Solution 1 rebuilds a set from each left end. The number of distinct values is monotone in the right end: once the window is complete, every subarray that keeps this right end and a left end at most \(i\) is complete, which adds \(n-j\). Then advance the left end while updating the counts.

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        cnt = len(set(nums))
        d = Counter()
        ans, n = 0, len(nums)
        i = 0
        for j, x in enumerate(nums):
            d[x] += 1
            while len(d) == cnt:
                ans += n - j
                d[nums[i]] -= 1
                if d[nums[i]] == 0:
                    d.pop(nums[i])
                i += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int countCompleteSubarrays(int[] nums) {
        Map<Integer, Integer> d = new HashMap<>();
        for (int x : nums) {
            d.put(x, 1);
        }
        int cnt = d.size();
        int ans = 0, n = nums.length;
        d.clear();
        for (int i = 0, j = 0; j < n; ++j) {
            d.merge(nums[j], 1, Integer::sum);
            while (d.size() == cnt) {
                ans += n - j;
                if (d.merge(nums[i], -1, Integer::sum) == 0) {
                    d.remove(nums[i]);
                }
                ++i;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        unordered_map<int, int> d;
        for (int x : nums) {
            d[x] = 1;
        }
        int cnt = d.size();
        d.clear();
        int ans = 0, n = nums.size();
        for (int i = 0, j = 0; j < n; ++j) {
            d[nums[j]]++;
            while (d.size() == cnt) {
                ans += n - j;
                if (--d[nums[i]] == 0) {
                    d.erase(nums[i]);
                }
                ++i;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func countCompleteSubarrays(nums []int) (ans int) {
    d := map[int]int{}
    for _, x := range nums {
        d[x] = 1
    }
    cnt := len(d)
    i, n := 0, len(nums)
    d = map[int]int{}
    for j, x := range nums {
        d[x]++
        for len(d) == cnt {
            ans += n - j
            d[nums[i]]--
            if d[nums[i]] == 0 {
                delete(d, nums[i])
            }
            i++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function countCompleteSubarrays(nums: number[]): number {
    const d: Map<number, number> = new Map();
    for (const x of nums) {
        d.set(x, (d.get(x) ?? 0) + 1);
    }
    const cnt = d.size;
    d.clear();
    const n = nums.length;
    let ans = 0;
    let i = 0;
    for (let j = 0; j < n; ++j) {
        d.set(nums[j], (d.get(nums[j]) ?? 0) + 1);
        while (d.size === cnt) {
            ans += n - j;
            d.set(nums[i], d.get(nums[i])! - 1);
            if (d.get(nums[i]) === 0) {
                d.delete(nums[i]);
            }
            ++i;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
use std::collections::HashMap;

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

        let (mut i, mut j) = (0, 0);
        while j < n {
            *d.entry(nums[j]).or_insert(0) += 1;
            while d.len() == cnt {
                ans += (n - j) as i32;
                let e = d.get_mut(&nums[i]).unwrap();
                *e -= 1;
                if *e == 0 {
                    d.remove(&nums[i]);
                }
                i += 1;
            }
            j += 1;
        }
        ans
    }
}

Comments