Scale Engineer

Count Complete Subarrays in an Array

Med
#2506Time: O(N^3), where N is the length of the array. The two outer loops iterate through all O(N^2) subarrays. For each subarray of length L, we iterate through it to count distinct elements, which takes O(L) time. In the worst case, L is O(N), leading to an overall complexity of O(N^3).Space: O(N), where N is the length of the array. In the worst case, a subarray can contain N distinct elements, requiring a `HashSet` of size N. The set for the total distinct count also takes up to O(N) space.
Patterns
Sliding Window
Data structures
ArrayHash Table

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to generate every possible subarray and, for each one, check if it is 'complete'. A subarray is complete if its number of distinct elements equals the number of distinct elements in the entire original array.

Algorithm

    1. Create a HashSet from the entire nums array to find the total number of distinct elements, k.
    1. Initialize a counter count to 0.
    1. Use a nested loop with index i from 0 to n-1 to mark the start of a subarray.
    1. Use another nested loop with index j from i to n-1 to mark the end of a subarray.
    1. For each subarray nums[i...j], create a temporary HashSet.
    1. Iterate from i to j and add elements of the subarray to the temporary set.
    1. If the size of the temporary set equals k, increment count.
    1. After all loops complete, return count.

Walkthrough

First, we need to determine the target number of distinct elements. We can do this by iterating through the entire nums array once and storing the elements in a HashSet. The size of this set is our target count, let's call it k.

Then, we use two nested loops to define the start (i) and end (j) indices of all possible subarrays. For each subarray nums[i...j], we use a third loop to iterate through its elements, count the number of distinct elements using another temporary HashSet, and check if this count equals k. If it does, we increment our result counter.

import java.util.HashSet;import java.util.Set; class Solution {    public int countCompleteSubarrays(int[] nums) {        Set<Integer> totalDistinctSet = new HashSet<>();        for (int num : nums) {            totalDistinctSet.add(num);        }        int k = totalDistinctSet.size();        int n = nums.length;        int count = 0;         for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                // Subarray is nums[i...j]                Set<Integer> subArrayDistinctSet = new HashSet<>();                for (int l = i; l <= j; l++) {                    subArrayDistinctSet.add(nums[l]);                }                if (subArrayDistinctSet.size() == k) {                    count++;                }            }        }        return count;    }}

Complexity

Time

O(N^3), where N is the length of the array. The two outer loops iterate through all O(N^2) subarrays. For each subarray of length L, we iterate through it to count distinct elements, which takes O(L) time. In the worst case, L is O(N), leading to an overall complexity of O(N^3).

Space

O(N), where N is the length of the array. In the worst case, a subarray can contain N distinct elements, requiring a `HashSet` of size N. The set for the total distinct count also takes up to O(N) space.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Highly inefficient due to the triple nested loop.

  • Will likely result in a 'Time Limit Exceeded' error for larger inputs.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem