Sort the Jumbled Numbers

Medium

Asked by:

45 views

Topics:

ArraysStrings

You are given a 0-indexed integer array mapping which represents the mapping rule of a shuffled decimal system. mapping[i] = j means digit i should be mapped to digit j in this system.

The mapped value of an integer is the new integer obtained by replacing each occurrence of digit i in the integer with mapping[i] for all 0 <= i <= 9.

You are also given another integer array nums. Return the array nums sorted in non-decreasing order based on the mapped values of its elements.

Notes:

Elements with the same mapped values should appear in the same relative order as in the input.
The elements of nums should only be sorted based on their mapped values and not be replaced by them.

Example 1:

Input: mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38]
Output: [338,38,991]
Explanation: 
Map the number 991 as follows:
1. mapping[9] = 6, so all occurrences of the digit 9 will become 6.
2. mapping[1] = 9, so all occurrences of the digit 1 will become 9.
Therefore, the mapped value of 991 is 669.
338 maps to 007, or 7 after removing the leading zeros.
38 maps to 07, which is also 7 after removing leading zeros.
Since 338 and 38 share the same mapped value, they should remain in the same relative order, so 338 comes before 38.
Thus, the sorted array is [338,38,991].

Example 2:

Input: mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123]
Output: [123,456,789]
Explanation: 789 maps to 789, 456 maps to 456, and 123 maps to 123. Thus, the sorted array is [123,456,789].

Constraints:

mapping.length == 10
0 <= mapping[i] <= 9
All the values of mapping[i] are unique.
1 <= nums.length <= 3 * 10⁴
0 <= nums[i] < 10⁹

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 numbers within the `mapping` array, and what is the range of the numbers in the `nums` array?
Can the `mapping` array contain duplicate values, and if so, how should that be handled during the remapping?
Is the `nums` array guaranteed to only contain non-negative integers?
If multiple numbers have the same remapped value after applying the mapping, how should their original order in the `nums` array be preserved?
What should the return type be? Specifically, should I return a new array or sort the input array in place?

Brute Force Solution

Approach

The most straightforward way to sort jumbled numbers is to try out all the possible arrangements. We generate every possible combination, then check each one to see if it follows the rules for the jumbled numbers. Finally, we pick the arrangement that meets all the rules and is in the correct sorted order.

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

First, list every possible order the numbers could be in. Think of shuffling a deck of cards and writing down every possible shuffle.
For each of these possible orderings, check if it is 'jumbled' according to the problem rules. If a number is not mapped to the correct image, then discard this arrangement.
If an ordering follows the jumbled rules, also check if that ordering is sorted correctly from smallest to largest number.
If the ordering follows the rules and is sorted, then this is a possible solution. Save this arrangement.
After checking all possible orderings, pick any one of the arrangements that satisfy the problem's requirements. It doesn't matter which one you choose because we found a valid option.

Code Implementation

import itertools

def sort_jumbled_numbers_brute_force(number_mapping, jumbled_numbers):
    all_permutations = list(itertools.permutations(jumbled_numbers))
    valid_arrangements = []

    for permutation in all_permutations:
        is_jumbled = True

        # Ensure each number maps to the correct image
        for number in permutation:
            original_number = [key for key, value in number_mapping.items() if value == number]
            if not original_number:
                is_jumbled = False
                break

        if is_jumbled:
            is_sorted = True

            # Check if the permutation is sorted according to the original numbers
            original_numbers_permutation = []
            for number in permutation:
                original_number = [key for key, value in number_mapping.items() if value == number][0]
                original_numbers_permutation.append(original_number)

            for i in range(len(original_numbers_permutation) - 1):
                if original_numbers_permutation[i] > original_numbers_permutation[i + 1]:
                    is_sorted = False
                    break

            if is_sorted:
                valid_arrangements.append(permutation)

    if valid_arrangements:
        # Return the first valid arrangement found
        return list(valid_arrangements[0])
    else:
        return []

Big(O) Analysis

Time Complexity

O(n! * n * n) – The algorithm first generates all possible permutations of the input numbers, which takes O(n!) time, where n is the number of input numbers. For each permutation, it checks if the arrangement is 'jumbled,' which involves iterating through all n numbers and their mapped images, taking O(n) time. It also checks if the 'jumbled' arrangement is sorted, requiring another O(n) operation. Therefore, the overall time complexity is O(n! * n * n).

Space Complexity

O(N!) – The algorithm generates all possible orderings of the numbers, which are permutations. Storing all these permutations requires space proportional to the number of permutations, which is N! where N is the number of numbers to be sorted. Each permutation is stored as an auxiliary data structure, likely a list or array. The space needed to store these permutations dominates the space complexity.

Optimal Solution

Approach

We are given a list of numbers and a mapping that changes each digit to a new value. The goal is to sort the original list of numbers, but according to their *mapped* values. Essentially, we need to determine a number's mapped representation, sort according to the mapped values, and return the original numbers in that sorted order.

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

First, create a way to translate each number in the original list into its 'jumbled' or mapped version using the provided mapping.
Next, create a paired list where each element is a pair of the original number and its mapped (jumbled) representation.
Then, sort this paired list based on the mapped values, not the original numbers.
Finally, extract the original numbers from the sorted paired list. This will be the final sorted list based on the jumbled number values.

Code Implementation

def sort_jumbled_numbers(mapping, numbers):
    def map_number(number):
        number_string = str(number)
        mapped_string = "".join([str(mapping[int(digit)]) for digit in number_string])
        return int(mapped_string)

    # Create pairs of original number and its mapped value.
    paired_numbers = [(number, map_number(number)) for number in numbers]

    # Sort the paired numbers based on the mapped values.
    paired_numbers.sort(key=lambda pair: pair[1])

    # Extract the original numbers from the sorted pairs.
    sorted_numbers = [pair[0] for pair in paired_numbers]

    return sorted_numbers

def sort_the_jumbled_numbers(mapping, numbers):
    def translate_number(number):
        number_as_string = str(number)
        translated_string = "".join(str(mapping[int(digit)]) for digit in number_as_string)
        return int(translated_string)

    # Create a paired list of (original number, mapped number).
    paired_list = []
    for original_number in numbers:
        mapped_number = translate_number(original_number)
        paired_list.append((original_number, mapped_number))

    # Sort the paired list based on the mapped numbers.
    paired_list.sort(key=lambda x: x[1])

    # Extract the original numbers to form the final result.
    result = [original_number for original_number, _ in paired_list]

    return result

def sort_the_numbers(mapping, numbers):
    def get_mapped_value(number):
        number_string = str(number)
        mapped_string = "".join(str(mapping[int(digit)]) for digit in number_string)
        return int(mapped_string)

    # Pair original numbers with their mapped values.
    number_map = []
    for number in numbers:
        mapped_value = get_mapped_value(number)
        number_map.append((number, mapped_value))

    # Sort based on the mapped values.
    number_map.sort(key=lambda x: x[1])

    # Extract the sorted original numbers.
    sorted_numbers = [number for number, _ in number_map]
    return sorted_numbers

def sort_the_jumbled(mapping, numbers):
    def translate(number):
        number_string = str(number)
        translated = "".join(str(mapping[int(digit)]) for digit in number_string)
        return int(translated)

    # Pair each number with its jumbled representation
    paired = []
    for number in numbers:
        paired.append((number, translate(number)))

    # Sort by the jumbled values
    paired.sort(key=lambda x: x[1])

    # Extract the original numbers, now sorted
    result = [x[0] for x in paired]
    return result

def sort_jumbled(mapping, numbers):
    def get_jumbled_value(number):
        number_string = str(number)
        jumbled_string = "".join([str(mapping[int(digit)]) for digit in number_string])
        return int(jumbled_string)

    # Create a list of tuples (original number, jumbled number).
    jumbled_numbers = [(number, get_jumbled_value(number)) for number in numbers]

    # Sort based on the jumbled number.
    jumbled_numbers.sort(key=lambda x: x[1])

    # Extract the original numbers from the sorted list.
    sorted_numbers = [number for number, _ in jumbled_numbers]

    return sorted_numbers

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm involves mapping each of the n numbers, which takes O(n) time assuming the mapping operation for each digit is constant time. Then, the core operation is sorting the paired list of (original number, mapped number). Sorting this list of n elements using an efficient comparison-based sorting algorithm like mergesort or quicksort takes O(n log n) time. Extracting the original numbers from the sorted list is a linear O(n) operation. Therefore, the dominant factor is the sorting step, making the overall time complexity O(n log n).

Space Complexity

O(N) – The algorithm creates a paired list of size N, where N is the number of numbers in the original list, to store the original number and its mapped representation. Sorting this list in place is not guaranteed (depending on the sorting algorithm used by the language's sort function), so we assume additional space may be needed. Finally, the sorted paired list leads to an output list of size N. Therefore, the auxiliary space is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array immediately to avoid null pointer exceptions and handle the base case.
Input array with only one element	Return the original array as it is already sorted (or considered trivially sorted).
Array contains only identical values	The mapping will still function correctly, resulting in a sorted version of the identical values.
Very large array exceeding memory limits	Consider an external merge sort that sorts chunks of data and then merges the sorted chunks on disk.
Extreme boundary values (min/max integer)	Ensure the jumbling function can correctly handle integer overflow/underflow and doesn't unexpectedly change their relative ordering.
All jumbled numbers map to the same value after jumbling	The sort will produce a sorted array with respect to that identical mapped value but maintain original order.
Jumbling function produces integer overflow	Use long long or BigInteger to store jumbled numbers, ensuring we don't lose information from the calculation.
The jumbling mapping is not invertible	The numbers will be sorted based on their jumbled values and original values are ignored when sorting by the jumbled version.

Null or empty input array

How to Handle:

Return an empty array immediately to avoid null pointer exceptions and handle the base case.

Input array with only one element

How to Handle:

Return the original array as it is already sorted (or considered trivially sorted).

Array contains only identical values

How to Handle:

The mapping will still function correctly, resulting in a sorted version of the identical values.

Very large array exceeding memory limits

How to Handle:

Consider an external merge sort that sorts chunks of data and then merges the sorted chunks on disk.

Extreme boundary values (min/max integer)

How to Handle:

Ensure the jumbling function can correctly handle integer overflow/underflow and doesn't unexpectedly change their relative ordering.

All jumbled numbers map to the same value after jumbling

How to Handle:

The sort will produce a sorted array with respect to that identical mapped value but maintain original order.

Jumbling function produces integer overflow

How to Handle:

Use long long or BigInteger to store jumbled numbers, ensuring we don't lose information from the calculation.

The jumbling mapping is not invertible

How to Handle:

The numbers will be sorted based on their jumbled values and original values are ignored when sorting by the jumbled version.