Leetcode – Sort Array by Increasing Frequency Solution

Spread the love

The “Sort Array by Increasing Frequency” problem on Leetcode provides an excellent opportunity to explore array manipulation and sorting algorithms in depth. It poses a dual challenge: first, you need to sort the elements based on their frequency, and second, for elements with the same frequency, you need to sort them based on their value. This multi-level sorting requirement makes the problem a rich ground for exploration and discussion.

In this detailed article, we will dissect the problem, delve into different approaches to solve it, discuss their time and space complexities, and implement the solutions in Python.

Problem Description

The problem statement is as follows:

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

frequencySort([1,1,2,2,2,3])  # Output: [3,1,1,2,2,2]

Approach 1: Count and Custom Sort

Algorithm

  1. Count the frequency of each number in the array using a dictionary.
  2. Use Python’s built-in sorted function with a custom key function that takes into account both frequency and value.

Python Code

from typing import List
from collections import Counter

def frequencySort(nums: List[int]) -> List[int]:
    freq_map = Counter(nums)
    
    return sorted(nums, key=lambda x: (freq_map[x], -x))

Time Complexity

The time complexity is O(n log⁡ n), where n is the length of the input list. This is primarily because of the sorting operation.

Space Complexity

The space complexity is O(n) for storing the frequency map.

Approach 2: Bucket Sort

Algorithm

  1. Count the frequency of each number and store it in a dictionary.
  2. Create buckets based on frequencies and place numbers in their corresponding buckets.
  3. Sort each bucket individually, then concatenate them.

Python Code

from typing import List
from collections import Counter

def frequencySort(nums: List[int]) -> List[int]:
    freq_map = Counter(nums)
    max_freq = max(freq_map.values())
    
    buckets = [[] for _ in range(max_freq + 1)]
    
    for num, freq in freq_map.items():
        buckets[freq].append(num)
    
    for bucket in buckets:
        bucket.sort(reverse=True)
        
    sorted_nums = []
    for i, bucket in enumerate(buckets):
        for num in bucket:
            sorted_nums.extend([num] * i)
    
    return sorted_nums

Time Complexity

The time complexity is O(n+k log⁡ k), where n is the number of elements in the list and k is the number of unique elements. This is because we need to sort each bucket.

Space Complexity

The space complexity is O(n) for storing the frequency map and buckets.

Conclusion

The “Sort Array by Increasing Frequency” problem serves as an excellent platform to deepen our understanding of sorting algorithms and array manipulation. While the custom sort approach is simple and leverages Python’s powerful built-ins, the bucket sort approach provides an alternative that might be more efficient when the number of unique elements is small.

Leave a Reply