EasyNo. 2465
Number of Distinct Averages — LeetCode 2465 Python Solution
- Pattern
- Two Pointers
- Topics
- Array, Hash Table, Two Pointers, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a 0-indexed integer array nums of even length. As long as nums is not empty, you must repetitively: Find the minimum number in nums and remove it.
Example
- Input
- nums = [4,1,4,0,3,5]
- Output
- 2
- Explanation
- 1. Remove 0 and 5, and the average is (0 + 5) / 2 = 2.5. Now, nums = [4,1,4,3].
Python solution
class Solution:
def distinctAverages(self, nums: List[int]) -> int:
nums.sort()
return len(set(nums[i] + nums[-i - 1] for i in range(len(nums) >> 1)))Complexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Two Pointers
Use the order already in the input to discard half the search space at every step. LeetCode 2465. Number of Distinct Averages is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.
The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0349 | Intersection of Two Arrays | Easy |
| 0350 | Intersection of Two Arrays II | Easy |
| 0522 | Longest Uncommon Subsequence II | Medium |
| 0532 | K-diff Pairs in an Array | Medium |
| 0923 | 3Sum With Multiplicity | Medium |
| 1048 | Longest String Chain | Medium |
Frequently asked questions
- How hard is LeetCode 2465. Number of Distinct Averages?
LeetCode 2465. Number of Distinct Averages is rated Easy on LeetCode.
- What is the time complexity of LeetCode 2465. Number of Distinct Averages?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 2465. Number of Distinct Averages?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2465. Number of Distinct Averages cover?
LeetCode 2465. Number of Distinct Averages is tagged Array, Hash Table, Two Pointers and Sorting on LeetCode.