EasyNo. 1636
Sort Array by Increasing Frequency — LeetCode 1636 Python Solution
- Pattern
- Sorting
- Topics
- Array, Hash Table, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.
Example
- Input
- nums = [1,1,2,2,2,3]
- Output
- [3,1,1,2,2,2]
- Explanation
- '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.
Python solution
class Solution:
def frequencySort(self, nums: List[int]) -> List[int]:
cnt = Counter(nums)
return sorted(nums, key=lambda x: (cnt[x], -x))Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1636. Sort Array by Increasing Frequency is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1630 | Arithmetic Subarrays | Medium |
| 0049 | Group Anagrams | Medium |
| 0169 | Majority Element | Easy |
| 0217 | Contains Duplicate | Easy |
| 0229 | Majority Element II | Medium |
| 0268 | Missing Number | Easy |
Frequently asked questions
- How hard is LeetCode 1636. Sort Array by Increasing Frequency?
LeetCode 1636. Sort Array by Increasing Frequency is rated Easy on LeetCode.
- What is the time complexity of LeetCode 1636. Sort Array by Increasing Frequency?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1636. Sort Array by Increasing Frequency?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1636. Sort Array by Increasing Frequency cover?
LeetCode 1636. Sort Array by Increasing Frequency is tagged Array, Hash Table and Sorting on LeetCode.