Problem Statement

Given an array nums containing the integers, return the resultant array after sorting it in increasing order based on the frequency of the values. If two numbers have the same frequency, they should be sorted in descending numerical order.

Examples

Example 1:

• Input: nums = [4, 4, 6, 2, 2, 2]
• ExpectedOutput: [6, 4, 4, 2, 2, 2]
• Justification: Here, '6' appears once, '4' appears twice, and '2' appears three times. Thus, numbers are first sorted by frequency and then by value when frequencies tie.

Example 2:

• Input: nums = [0, -1, -1, -1, 5]
• ExpectedOutput: [5, 0, -1, -1, -1]
• Justification: '5' and '0' appears once, and '-1' appears three times. After sorting by frequency and resolving ties by sorting in descending order, the result is obtained.

Example 3:

• Input: nums = [10, 10, 10, 20, 20, 30]
• ExpectedOutput: [30, 20, 20, 10, 10, 10]
• Justification: Here, '30' has the lowest frequency, followed by '20', and '10' has the highest frequency. They are sorted accordingly.

Constraints:

• 1 <= nums.length <= 100
• -1000 <= nums[i] <= 1000

Solution

To solve this problem, we use a combination of sorting and hashmap data structures. A hashmap is utilized to count the frequency of each element in the array. The key of this approach lies in sorting the array not by the numerical values directly but by the frequency of these values as stored in the hashmap. For values with identical frequencies, a secondary sort criterion is used where numbers are sorted in descending order. This method ensures that we can efficiently sort the array according to the specified rules and handle ties in frequency properly.

Step-by-step Algorithm

1. Count Frequencies:

   • Create a HashMap (freqMap) to store each number's frequency from the array.
   • Iterate through the array, incrementing the count for each number in the freqMap.

2. Merge Sort Algorithm:

   • Base Case: If the current segment (subarray) of the array has only one element or is empty, return immediately as a single element or an empty segment is inherently sorted.
   • Recursive Sort:
     • Divide the array into two halves.
     • Recursively apply merge sort to the left half.
     • Recursively apply merge sort to the right half.
   • Merge Step:
     • Combine the two sorted halves into a single sorted segment using the merge function, which sorts by frequency and value as described.

3. Merge Function:

   • Initialize Pointers: Start with two pointers, one for each half, and a temporary array to build the merged list.
   • Comparison and Merging:
     • Compare elements from the two halves.
       • By Frequency: Place the element with the lower frequency in the temporary array first.
       • By Value on Tie: If frequencies are the same, place the element with the higher numerical value first.
     • Move the pointer forward in the half from which the element was taken.
   • Append Remaining Elements: Once one half is exhausted, append all remaining elements from the other half.
   • Copy to Original: Copy the elements from the temporary array back to the original array segment.

4. Final Assembly:

   • After the top-level merge is completed, the array is fully sorted as per the given criteria.

Algorithm Walkthrough

Let's consider the Input: nums = [4, 4, 6, 2, 2, 2]

Initial Setup:

• Array: [4, 4, 6, 2, 2, 2]
• freqMap shows frequencies:
  • 4 -> 2
  • 6 -> 1
  • 2 -> 3

Divide and Conquer with Merge Sort:

Step 1: Splitting the Array

• Split the array into two halves: [4, 4, 6] and [2, 2, 2]

Step 2: Further Split Left Half [4, 4, 6]

• Split [4, 4, 6] into [4, 4] and [6].

Merge Sort on [4, 4]

• Since all elements are the same and it’s already sorted by our criteria, this part needs no further action.

Merge Sort on [6]

• A single-element array is inherently sorted.

Step 3: Merging [4, 4] and [6]

• Compare:
  • 4 (freq = 2) and 6 (freq = 1).
• Since 6 has a lower frequency, it comes first.
• Resulting merged array: [6, 4, 4]

Step 4: Right Half [2, 2, 2]

• All elements are the same and thus, no sorting needed.

Final Step: Merging [6, 4, 4] and [2, 2, 2]

• Compare:
  • 6 (freq = 1) from the left with 2 (freq = 3) from the right.
• 6 comes first because of the lower frequency.
• 4 also has a lower frequency than 2 and they follow 6.
• Resulting final sorted array after merging: [6, 4, 4, 2, 2, 2]

Complexity Analysis

Time Complexity

1. Frequency Counting: The frequency of each element is counted using a loop that iterates through each element of the array, which takes O(n) time where (n) is the number of elements in the array.

2. Merge Sort:

   • Divide Step: The array is recursively divided into two halves until each subarray contains a single element. This division takes place logarithmically relative to the length of the array, resulting in O(\log n) divisions.
   • Conquer Step: Each merge operation for two halves takes O(n) time, as each element is considered once for merging. Since merge sort merges at each level of recursion, and each level operates over the entire array, the merge operations at each level of recursion together also take O(n) time.

Combining these two steps, the merge sort operation results in a time complexity of O(n \log n).

Therefore, the overall time complexity of the algorithm is: O(n) + O(n \log n) = O(n \log n) This is because the sorting dominates the frequency counting in terms of time complexity.

Space Complexity

1. Frequency Map: The space required for storing the frequency of each unique element is O(k), where (k) is the number of unique elements. In the worst case, where all elements are unique, this becomes O(n).

2. Merge Sort:

   • Temporary Arrays: The merge operation uses temporary arrays to hold the elements being merged. The size of these arrays collectively is equal to the size of the array being sorted, which is O(n).

3. Recursion Stack: Merge sort is a recursive algorithm. The space used by the call stack during the recursive calls depends on the depth of the recursion tree, which is O(\log n).

Combining the space required for the frequency map, the temporary arrays, and the recursion stack, the total space complexity of the algorithm is: O(n) + O(n) + O(\log n) \approx O(n) This space complexity is mainly dominated by the space needed for the frequency map and the temporary arrays used in the merge operations. The additional O(\log n) space from the recursion stack is relatively minor compared to (O(n)).