DSCPPAS265 - Editorial

editorial
,
1

Problem Statement:

You are given a list of integers. The task is to sort the list based on the frequency of each integer in ascending order. If two integers have the same frequency, the integer with the smaller value should come first.

Approach:

To solve this problem, we need to accomplish two main tasks:

  1. Count the frequency of each integer in the list.
  2. Sort the integers based on their frequency in ascending order. If two integers have the same frequency, the one with the smaller value should appear first.

Here’s a step-by-step explanation of the approach:

Step 1: Counting the Frequencies

  • We initialize an array count where count[i] stores the frequency of integer i.
  • We iterate over the input list and increment the count of each integer in the count array.

Step 2: Creating a List of Pairs

  • After counting the frequencies, we create a list of pairs where each pair consists of an integer and its corresponding frequency.
  • For example, if the frequency of integer 3 is 2, we create a pair (3, 2).

Step 3: Sorting the List of Pairs

  • We then sort this list of pairs based on two criteria:
    1. Primary Criterion: Sort by frequency in ascending order.
    2. Secondary Criterion: If two integers have the same frequency, sort by the integer’s value in ascending order.

Step 4: Generating the Sorted List

  • Finally, we construct the sorted list by appending each integer in the order determined by the sorted list of pairs.

Example:

Let’s consider an example where the input list is:

[4, 5, 6, 5, 4, 3]

  • The frequency count will be:

    • 4 occurs 2 times.
    • 5 occurs 2 times.
    • 6 occurs 1 time.
    • 3 occurs 1 time.

  • The list of pairs based on frequency would be:

    [(6, 1), (3, 1), (4, 2), (5, 2)]

  • After sorting based on frequency and value, the list becomes:

    [(3, 1), (6, 1), (4, 2), (5, 2)]

  • The final sorted output list would be:

    [3, 6, 4, 4, 5, 5]

Time Complexity:

The time complexity is O(n + k log k) where n is the number of elements and k is the number of unique elements in the list.

Space Complexity:

The space complexity is O(k) for storing the frequency list, where k is the number of unique elements.