Jobs

Interviews

Discussions

Sort Array by Increasing Frequency

#27 Most AskedEasy

Sort Array by Increasing Frequency #27 Most Asked

Easy

SAP

2 views

Topics:

Arrays

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

Try coding it in LeetCode

Sort Array by Increasing Frequency

#27 Most AskedEasy

Sort Array by Increasing Frequency #27 Most Asked

Easy

SAP

2 views

Topics:

Arrays

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the input array? Can I expect negative numbers, zeros, or a mix?
If multiple numbers have the same frequency, how should I order them in the output?
What should I return if the input array is null or empty?
Are there any constraints on the size of the input array? I want to be mindful of potential memory limitations.
Is the input array guaranteed to contain only integers, or could it contain other data types like floats or strings?

Brute Force Solution

Approach

The brute force method for sorting by increasing frequency means we try out all possible arrangements of the items. We'll check each arrangement to see if it follows the 'increasing frequency' rule. If it does, we keep it; otherwise, we discard it and try a different arrangement until we find a valid solution.

Here's how the algorithm would work step-by-step:

First, consider every possible order you could put the items in.
For each possible order, count how many times each different item appears in that order.
Then, check if the items are sorted by how often they appear, from least frequent to most frequent.
If the items are sorted by increasing frequency, that's a valid solution. If not, it's not a valid solution.
If you find multiple valid solutions, you can select one arbitrarily or apply additional rules to pick the 'best' one (like keeping the original order for items with the same frequency).

Code Implementation

import itertools

def sort_by_increasing_frequency_brute_force(items):
    all_permutations = list(itertools.permutations(items))

    valid_solutions = []
    for permutation in all_permutations:
        item_counts = {}
        for item in permutation:
            item_counts[item] = item_counts.get(item, 0) + 1

        is_sorted_by_frequency = True
        frequency = -1
        # Check increasing frequency for validity
        for item in permutation:

            current_frequency = item_counts[item]

            if current_frequency < frequency:
                is_sorted_by_frequency = False
                break

            frequency = current_frequency

        # Store valid permutation
        if is_sorted_by_frequency:

            valid_solutions.append(list(permutation))

    if valid_solutions:
        return valid_solutions[0]
    else:
        return []

Big(O) Analysis

Time Complexity

O(n! * n) – The brute force method involves generating all possible permutations of the input array of size n. There are n! (n factorial) possible permutations. For each permutation, we need to count the frequency of each element, which takes O(n) time. After calculating the frequencies, we must verify if the permutation is sorted by increasing frequency. This frequency check also takes O(n) time. Thus, the overall time complexity is dominated by generating all permutations and checking each permutation's frequencies, resulting in O(n! * n) time complexity, even when combining the frequency counting and sorting into one O(n) pass.

Space Complexity

O(N) – The brute force approach considers all possible arrangements of the input array of size N. Generating all permutations of an array of size N requires storing N elements in each arrangement. Furthermore, for each permutation, we count the frequency of each element, which could involve a hash map or an array of size up to N. Therefore, the auxiliary space used is proportional to the size of the input array, resulting in O(N) space complexity.

Optimal Solution

Approach

The trick to efficiently sorting the array is to count how often each number appears, then use that count to rearrange the numbers. We will sort the numbers based on their frequencies, placing the least frequent numbers first.

Here's how the algorithm would work step-by-step:

First, count how many times each unique number shows up in the array.
Next, sort the unique numbers based on their counts. Numbers that appear less often should come earlier in the sorted list.
If multiple numbers have the same count, sort them in descending order based on their original values. This puts larger numbers ahead of smaller numbers with the same frequency.
Finally, build a new array by repeating each number according to its frequency, following the order determined in the previous step. This will give the sorted array.

Code Implementation

def sort_by_frequency(numbers):
    frequency_map = {}
    for number in numbers:
        frequency_map[number] = frequency_map.get(number, 0) + 1

    # Sort by frequency, then descending value
    sorted_numbers = sorted(numbers, key=lambda number: (frequency_map[number], -number))

    # Build the result array based on the sorted frequencies
    result = []
    number_counts = {}
    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    # Ensure correct ordering by frequencies
    unique_numbers = []
    for number in numbers:
        if number not in unique_numbers:
            unique_numbers.append(number)

    unique_numbers = sorted(unique_numbers, key=lambda number: (frequency_map[number], -number))

    # Construct the sorted array
    for number in unique_numbers:
        result.extend([number] * frequency_map[number])

    return result

def sort_array_by_increasing_frequency(numbers):
    # Count the frequency of each number.
    number_frequencies = {}
    for number in numbers:
        number_frequencies[number] = number_frequencies.get(number, 0) + 1

    # Sort based on frequency then value.
    # Important for stability with same frequencies.
    sorted_numbers = sorted(numbers, key=lambda number: (number_frequencies[number], -number))
    
    # Create a map to efficiently count processed elements.
    seen_numbers = {}
    # Sort unique elements based on frequencies and values.
    unique_numbers = []
    for number in sorted_numbers:
        if number not in seen_numbers:
            unique_numbers.append(number)
            seen_numbers[number] = True

    # Construct sorted array.
    result_array = []
    for number in unique_numbers:
        # Use Extend to duplicate numbers the number of times they appear.
        result_array.extend([number] * number_frequencies[number])

    return result_array

Big(O) Analysis

Time Complexity

O(n log n) – Counting the frequency of each number takes O(n) time using a hash map. Sorting the unique numbers based on frequency can be done in O(k log k) time where k is the number of unique elements (k <= n). Building the final sorted array by repeating each number according to its frequency takes O(n) time. Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n) since k <= n.

Space Complexity

O(N) – The algorithm uses a hash map to count the frequency of each number in the input array. In the worst-case scenario, where all numbers in the input array are unique, the hash map will store N key-value pairs, where N is the size of the input array. Additionally, a sorted list of unique numbers is created, which in the worst case will also be of size N. Therefore, the auxiliary space used is proportional to N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list or throw an IllegalArgumentException, depending on the desired behavior.
Array with one element	Return the array itself as it's already sorted.
Array with all identical elements	The frequency count will be equal for all elements, resulting in either the original order or any other valid permutation that preserves the original order.
Array with maximum possible size allowed by memory constraints	Ensure the frequency counting data structure (e.g., HashMap) has sufficient capacity to handle the number of unique elements efficiently to avoid performance degradation.
Array containing negative numbers	The solution should correctly count frequencies and sort based on frequency, regardless of whether numbers are negative or positive.
Array with extreme boundary values (e.g., Integer.MAX_VALUE, Integer.MIN_VALUE)	Ensure the frequency count doesn't lead to integer overflow or other data type limitations during count increment or comparison.
Array with very large range of numbers, but relatively small number of unique elements	The frequency counting and sorting algorithm should perform efficiently based on the number of unique elements, not the range of values.
Multiple elements with the same frequency	Sort the elements with same frequency in decreasing order of their numerical value to achieve desired behavior.

Null or empty input array

How to Handle:

Return an empty list or throw an IllegalArgumentException, depending on the desired behavior.

Array with one element

How to Handle:

Return the array itself as it's already sorted.

Array with all identical elements

How to Handle:

The frequency count will be equal for all elements, resulting in either the original order or any other valid permutation that preserves the original order.

Array with maximum possible size allowed by memory constraints

How to Handle:

Ensure the frequency counting data structure (e.g., HashMap) has sufficient capacity to handle the number of unique elements efficiently to avoid performance degradation.

Array containing negative numbers

How to Handle:

The solution should correctly count frequencies and sort based on frequency, regardless of whether numbers are negative or positive.

Array with extreme boundary values (e.g., Integer.MAX_VALUE, Integer.MIN_VALUE)

How to Handle:

Ensure the frequency count doesn't lead to integer overflow or other data type limitations during count increment or comparison.

Array with very large range of numbers, but relatively small number of unique elements

How to Handle:

The frequency counting and sorting algorithm should perform efficiently based on the number of unique elements, not the range of values.

Multiple elements with the same frequency

How to Handle:

Sort the elements with same frequency in decreasing order of their numerical value to achieve desired behavior.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values within the input array? Can I expect negative numbers, zeros, or a mix?
If multiple numbers have the same frequency, how should I order them in the output?
What should I return if the input array is null or empty?
Are there any constraints on the size of the input array? I want to be mindful of potential memory limitations.
Is the input array guaranteed to contain only integers, or could it contain other data types like floats or strings?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider every possible order you could put the items in.
For each possible order, count how many times each different item appears in that order.
Then, check if the items are sorted by how often they appear, from least frequent to most frequent.
If the items are sorted by increasing frequency, that's a valid solution. If not, it's not a valid solution.
If you find multiple valid solutions, you can select one arbitrarily or apply additional rules to pick the 'best' one (like keeping the original order for items with the same frequency).

Code Implementation

import itertools

def sort_by_increasing_frequency_brute_force(items):
    all_permutations = list(itertools.permutations(items))

    valid_solutions = []
    for permutation in all_permutations:
        item_counts = {}
        for item in permutation:
            item_counts[item] = item_counts.get(item, 0) + 1

        is_sorted_by_frequency = True
        frequency = -1
        # Check increasing frequency for validity
        for item in permutation:

            current_frequency = item_counts[item]

            if current_frequency < frequency:
                is_sorted_by_frequency = False
                break

            frequency = current_frequency

        # Store valid permutation
        if is_sorted_by_frequency:

            valid_solutions.append(list(permutation))

    if valid_solutions:
        return valid_solutions[0]
    else:
        return []

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each unique number shows up in the array.
Next, sort the unique numbers based on their counts. Numbers that appear less often should come earlier in the sorted list.
If multiple numbers have the same count, sort them in descending order based on their original values. This puts larger numbers ahead of smaller numbers with the same frequency.
Finally, build a new array by repeating each number according to its frequency, following the order determined in the previous step. This will give the sorted array.

Code Implementation

def sort_by_frequency(numbers):
    frequency_map = {}
    for number in numbers:
        frequency_map[number] = frequency_map.get(number, 0) + 1

    # Sort by frequency, then descending value
    sorted_numbers = sorted(numbers, key=lambda number: (frequency_map[number], -number))

    # Build the result array based on the sorted frequencies
    result = []
    number_counts = {}
    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    # Ensure correct ordering by frequencies
    unique_numbers = []
    for number in numbers:
        if number not in unique_numbers:
            unique_numbers.append(number)

    unique_numbers = sorted(unique_numbers, key=lambda number: (frequency_map[number], -number))

    # Construct the sorted array
    for number in unique_numbers:
        result.extend([number] * frequency_map[number])

    return result

def sort_array_by_increasing_frequency(numbers):
    # Count the frequency of each number.
    number_frequencies = {}
    for number in numbers:
        number_frequencies[number] = number_frequencies.get(number, 0) + 1

    # Sort based on frequency then value.
    # Important for stability with same frequencies.
    sorted_numbers = sorted(numbers, key=lambda number: (number_frequencies[number], -number))
    
    # Create a map to efficiently count processed elements.
    seen_numbers = {}
    # Sort unique elements based on frequencies and values.
    unique_numbers = []
    for number in sorted_numbers:
        if number not in seen_numbers:
            unique_numbers.append(number)
            seen_numbers[number] = True

    # Construct sorted array.
    result_array = []
    for number in unique_numbers:
        # Use Extend to duplicate numbers the number of times they appear.
        result_array.extend([number] * number_frequencies[number])

    return result_array

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list or throw an IllegalArgumentException, depending on the desired behavior.
Array with one element	Return the array itself as it's already sorted.
Array with all identical elements	The frequency count will be equal for all elements, resulting in either the original order or any other valid permutation that preserves the original order.
Array with maximum possible size allowed by memory constraints	Ensure the frequency counting data structure (e.g., HashMap) has sufficient capacity to handle the number of unique elements efficiently to avoid performance degradation.
Array containing negative numbers	The solution should correctly count frequencies and sort based on frequency, regardless of whether numbers are negative or positive.
Array with extreme boundary values (e.g., Integer.MAX_VALUE, Integer.MIN_VALUE)	Ensure the frequency count doesn't lead to integer overflow or other data type limitations during count increment or comparison.
Array with very large range of numbers, but relatively small number of unique elements	The frequency counting and sorting algorithm should perform efficiently based on the number of unique elements, not the range of values.
Multiple elements with the same frequency	Sort the elements with same frequency in decreasing order of their numerical value to achieve desired behavior.

Null or empty input array

How to Handle:

Return an empty list or throw an IllegalArgumentException, depending on the desired behavior.

Array with one element

How to Handle:

Return the array itself as it's already sorted.

Array with all identical elements

How to Handle:

The frequency count will be equal for all elements, resulting in either the original order or any other valid permutation that preserves the original order.

Array with maximum possible size allowed by memory constraints

How to Handle:

Ensure the frequency counting data structure (e.g., HashMap) has sufficient capacity to handle the number of unique elements efficiently to avoid performance degradation.

Array containing negative numbers

How to Handle:

The solution should correctly count frequencies and sort based on frequency, regardless of whether numbers are negative or positive.

Array with extreme boundary values (e.g., Integer.MAX_VALUE, Integer.MIN_VALUE)

How to Handle:

Ensure the frequency count doesn't lead to integer overflow or other data type limitations during count increment or comparison.

Array with very large range of numbers, but relatively small number of unique elements

How to Handle:

The frequency counting and sorting algorithm should perform efficiently based on the number of unique elements, not the range of values.

Multiple elements with the same frequency

How to Handle:

Sort the elements with same frequency in decreasing order of their numerical value to achieve desired behavior.

0/41 SAP questions completed

0/41 completed