Number Of Distinct Averages - Leetcode Solution

Problem Statement:

Given an integer array nums, return the number of distinct averages of subarrays of nums with length at least 2.

Example 1:

Input: nums = [3,1,2,3] Output: 2 Explanation: The distinct averages are (3+1)/2=2 and (1+2+3)/3=2.

Example 2:

Input: nums = [0,4,3,3,4] Output: 3 Explanation: The distinct averages are (4+3)/2=3, (3+3)/2=3, and (4+3+3+4)/4=3.

Solution:

Approach:

• We can iterate the array to get all possible subarrays with length at least 2.
• We calculate the average of each subarray and store it in a set to keep track of unique averages.
• Finally, we return the size of the set as the number of distinct averages.

Code:

class Solution:
    def numOfSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        avg_set = set()
        for i in range(n):
            sum = 0
            for j in range(i, n):
                sum += nums[j]
                if j-i >= 1:
                    avg = sum / (j-i+1)
                    avg_set.add(avg)
        return len(avg_set)

Time Complexity:

The two nested loops result in O(n^2) time complexity. For each subarray, we calculate its average, which requires O(1) time. Adding an item to the set also takes O(1) time. Thus, the overall time complexity of the solution is O(n^2).

Space Complexity:

The set used to store distinct averages can have a maximum size of O(n^2), which is the number of possible subarrays. Therefore, the space complexity of the solution is also O(n^2).

1