Is Sort Array by Increasing Frequency easy or hard?

Sort Array by Increasing Frequency is categorized as an Easy problem. The main idea is counting element frequencies and applying a custom sort rule. Developers familiar with hash maps and sorting can implement the solution quickly.

Sort Array by Increasing Frequency Python/Java solution

In Python, use collections.Counter to count frequencies and sort with a key like (freq[x], -x). In Java, build a HashMap for counts and sort the array with a custom comparator based on frequency and value. Both implementations run in O(n log n) time.

How to solve Sort Array by Increasing Frequency in O(n)?

Use bucket sort after computing frequencies with a hash map. Create buckets where index i contains numbers appearing exactly i times. Iterate buckets from lowest to highest frequency and append numbers in descending order of value. Each element is processed a constant number of times, giving O(n) time and O(n) space.

What is the best approach for Sort Array by Increasing Frequency?

The most practical approach uses a hash map to count frequencies and then sorts the array with a custom comparator. The comparator sorts by frequency in ascending order and by value in descending order when frequencies tie. This method runs in O(n log n) time due to sorting and uses O(n) space for the frequency map.

Is Sort Array by Increasing Frequency asked at Google/Amazon/Meta?

Frequency-based sorting problems appear in interviews at companies like Amazon and Google because they combine hash tables with custom sorting logic. The problem tests whether you can derive ordering rules from constraints and implement them efficiently.

What data structure is used in Sort Array by Increasing Frequency?

A hash table (hash map) is used to store the frequency of each number in the array. After counting, the array is sorted using a custom comparator or processed using bucket sort. Arrays and hash maps are the primary data structures involved.

What is the time complexity of Sort Array by Increasing Frequency?

The common solution using a frequency map followed by sorting runs in O(n log n) time. Counting frequencies takes O(n), and sorting the array dominates the complexity. A bucket sort variant can reduce the time complexity to O(n) by grouping numbers by frequency.

Description Hints 2 Solution Video 4:11

1636. Sort Array by Increasing Frequency

Easy80.8% acceptance10 companies

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.

Return the sorted array.

Example 1:

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.

Example 2:

Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.

Example 3:

Input: nums = [-1,1,-6,4,5,-6,1,4,1]
Output: [5,-1,4,4,-6,-6,1,1,1]

Constraints:

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

Asked at 10 companies

Adobe Agoda Zoho Bloomberg Accenture

Google Amazon Oracle Microsoft Meta

Topics

Hints open one at a time

Hint 1

Count the frequency of each value.

Hint 2

Use a custom comparator to compare values by their frequency. If two values have the same frequency, compare their values.

4:11

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution