We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sort the Jumbled Numbers

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each digit in the numbers from nums can be transformed based on the mapping array.
  • The transformation needs to be applied to each number, and the resulting mapped values are used for sorting.
  • The sorted output must maintain the relative order of elements with the same mapped value.
  • We need to handle leading zeros in the mapped values carefully.

Space and Time Complexity

Time Complexity: O(n * m), where n is the number of elements in nums and m is the maximum number of digits in the largest number (up to 9). Space Complexity: O(n), for storing the mapped values and the sorted output.

Solution

To solve the problem, we will:

  1. Create a function to compute the mapped value of each number in nums.
  2. Use the mapping array to replace each digit in the number according to the mapping rules.
  3. Sort the nums array based on the computed mapped values while maintaining the original order for elements with the same mapped value.
  4. Return the sorted array.

We will use a list to hold the original numbers along with their mapped values for sorting.

Code Solutions

def sortJumbled(mapping, nums):
    def map_value(num):
        # Convert the number to its mapped value
        return int(''.join(str(mapping[int(digit)]) for digit in str(num)))

    # Create a list of tuples containing the original number and its mapped value
    mapped_nums = [(num, map_value(num)) for num in nums]
    
    # Sort based on mapped values while maintaining original order for ties
    mapped_nums.sort(key=lambda x: x[1])
    
    # Return the sorted original numbers
    return [num for num, _ in mapped_nums]

# Example usage
mapping = [8, 9, 4, 0, 2, 1, 3, 5, 7, 6]
nums = [991, 338, 38]
print(sortJumbled(mapping, nums))  # Output: [338, 38, 991]
← Back to All Questions