You are given an array nums consisting of positive integers.
We call a subarray of an array complete if the following condition is satisfied:
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 <= 10001 <= nums[i] <= 2000This approach uses a sliding window technique in combination with a HashMap (or dictionary) to keep track of the distinct elements within the window.
The solution uses a sliding window technique to efficiently count complete subarrays. It maintains a dictionary to hold the frequency of each element in the current window and counts the complete subarrays dynamically by shrinking the window from the left when a complete subarray is found.
Java
C++
C
C#
JavaScript
Time Complexity: O(n), where n is the length of the array, because we are processing each element at most twice.
Space Complexity: O(d), where d is the number of distinct elements, needed for the HashMap to store frequencies.
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,273 views views
Watch 9 more video solutions →Practice Count Complete Subarrays in an Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor