We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Complete Subarrays in an Array

Number: 2856

Difficulty: Medium

Paid? No

Companies: Amazon, TikTok

Problem Description

Given an array of positive integers, a subarray is called complete if it contains every distinct integer that appears in the entire array. The task is to count the number of complete subarrays.

Key Insights

  • First, determine the total number of distinct elements in the entire array.
  • For any starting index, we can identify the smallest ending index such that the subarray contains all distinct elements.
  • Once a subarray [i, j] is complete, every subarray [i, k] where k ≥ j is also complete.
  • Use a sliding window approach combined with a frequency counter to efficiently expand the window.
  • A two-level loop is sufficient since the array length is at most 1000.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario, where n is the number of elements in the array. Space Complexity: O(n) due to the auxiliary data structures used for counting frequencies.

Solution

We first compute the number of distinct elements in the entire array. Then, for each possible starting index, we use a sliding window to expand the subarray until it becomes complete (i.e., it contains all distinct elements). Once the minimal ending index is found for which the subarray is complete, every subarray ending from that index to the end of the array is also complete. We then add the count for that starting index. The key idea is to only compute the minimal window needed and then infer the number of valid subarrays from it.

Code Solutions

# Python solution with detailed comments

def countCompleteSubarrays(nums):
    # Determine the total distinct numbers in the array
    totalDistinct = len(set(nums))
    n = len(nums)
    result = 0

    # Iterate over each possible starting index for the subarray
    for i in range(n):
        windowFreq = {}
        distinctCount = 0
        # Expand the window from index i onward
        for j in range(i, n):
            if nums[j] in windowFreq:
                windowFreq[nums[j]] += 1
            else:
                windowFreq[nums[j]] = 1
                distinctCount += 1

            # When the current window is complete, all subarrays starting at i
            # and ending from j to the end will also be complete.
            if distinctCount == totalDistinct:
                result += (n - j)
                break  # Move to the next starting index as we only need the earliest j

    return result

# Example test cases
print(countCompleteSubarrays([1,3,1,2,2]))  # Expected output: 4
print(countCompleteSubarrays([5,5,5,5]))      # Expected output: 10
← Back to All Questions