Difficulty: Medium
Sliding window?!?!?!!? I did this while pretending to be in an interview setting, hence the comments at the start. Lowkey the comments explain a lot of my raw thought process while I was doing the question.
The basic idea is a sliding window approach where we keep track of the count of each number in the current window. We keep moving our right pointer while the number of unique elements in the window is not equal to the number of distinct elements in the entire array.
Once the two numbers match, we can calculate how many subarrays exist (which is len(nums) - r + 1) and add this to the result - this is the number of valid subarrays that exist starting at the l index. We then move to the next l making sure to remove whatever was at the previous l when doing so.
Once we go through all possible starting indexes l, we can return the result.
class Solution(object):
def countCompleteSubarrays(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# count no. of unique get all the unique numbers
# go through the array of nums
# get count
# sliding window approach
# keep a dictionary of counts
# l and r pointers
# if the number of keys in the dictionary is the same as count, we add len(nums) - right
# shift r pointer until the count is the same
# shift l pointer until the count is invalid
# count = 3
# res = 4
# hashmap {1:1, 3:1, 2:1}
# r
# 1 3 1 2 2
# l
# 0 1 2 3 4
# len 5
unique_count = len(set(nums))
res = 0
seen = {}
r = 0
for l in range(len(nums)):
while r < len(nums) and len(seen) < unique_count:
new_node = nums[r]
seen[new_node] = seen.get(new_node, 0) + 1
r += 1
if len(seen) == unique_count:
res += len(nums) - r + 1
prev = nums[l]
seen[prev] -= 1
if seen[prev] == 0:
seen.pop(prev)
return res
Time Complexity:
O(n)Space Complexity:
O(n)Time Taken:
17m 41s