Sort Array by Increasing Frequency - codepath/compsci_guides GitHub Wiki

Unit 12 Session 2 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 15-20 mins
  • 🛠️ Topics: Sorting, Hash Maps, Lambda Functions

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • What happens when two values have the same frequency?

    • They are sorted in decreasing order based on their values.

  • How do we treat negative numbers?

    • Negative numbers are treated the same as positive numbers for sorting based on frequency.
HAPPY CASE
Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: Frequencies are {3: 1, 1: 2, 2: 3}. Sorted by frequency, then value.

Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: Frequencies are {1: 1, 2: 2, 3: 2}. Since 2 and 3 have the same frequency, we sort them in decreasing order.

EDGE CASE
Input: nums = []
Output: []
Explanation: An empty list returns an empty list.

Input: nums = [5]
Output: [5]
Explanation: A single element list is already sorted.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Frequency-based Sorting problems, we want to consider the following approaches:

  • Hash Map + Custom Sorting: Use a hash map to store frequencies and sort the elements based on both frequency and value.
  • Lambda Sorting: Use a custom key function to sort by frequency in increasing order and by value in decreasing order.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Use a hash map to count the frequency of each element. Then, use the built-in sort() function with a custom key to sort the array based on frequency and value.

1) Create a hash map `frequency` to store the frequency of each element in the array.
2) Iterate through the `nums` array to populate the frequency map.
3) Sort the `nums` array using a custom sorting key:
   a) Sort by frequency in increasing order.
   b) If two elements have the same frequency, sort them by value in decreasing order.
4) Return the sorted array.

⚠️ Common Mistakes

  • Forgetting to handle the case when multiple values have the same frequency.
  • Not sorting by value in decreasing order when frequencies match.

4: I-mplement

Implement the code to solve the algorithm.

def freq_sort(nums):
    # Step 1: Count frequencies
    frequency = {}
    for num in nums:
        if num in frequency:
            frequency[num] += 1
        else:
            frequency[num] = 1
    
    # Step 2: Sort by frequency first (increasing), then by value (decreasing)
    nums.sort(key=lambda x: (frequency[x], -x))
    
    return nums

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: nums = [1,1,2,2,2,3]

    • Frequencies: {1: 2, 2: 3, 3: 1}
    • Sorted Output: [3,1,1,2,2,2]
    • Output: [3,1,1,2,2,2]

  • Input: nums = [2,3,1,3,2]

    • Frequencies: {2: 2, 3: 2, 1: 1}
    • Sorted Output: [1,3,3,2,2]
    • Output: [1,3,3,2,2]

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the length of the input array.

  • Time Complexity: O(N log N) due to sorting the array.
  • Space Complexity: O(N) for storing the frequency map.