Thomas Ngo

Software Engineer

2 minute read

Problem Statement

2191

Intuition

When tackling this problem, I noticed that the key challenge is transforming each number in the list according to a given mapping and then sorting the transformed numbers. The transformed number is derived by replacing each digit of the original number with its corresponding value in the provided mapping. After transformation, sorting these transformed numbers and retrieving the original numbers in the sorted order completes the task.

Approach

  1. Mapping Transformation: For each number in the list, transform it into a new number based on the provided digit mapping.
  2. Use a Dictionary: Utilize a dictionary to store the original numbers grouped by their transformed values.
  3. Sorting: Sort the keys of the dictionary, which represent the transformed values.
  4. Reconstruct the Result: Iterate through the sorted keys and extend the result list with the original numbers in the order of their transformed values.

Complexity

  • Time complexity: (O(n \log n))
    • This is primarily due to the sorting step. The transformation of each number is linear, and sorting the transformed values will take (O(n \log n)) where (n) is the number of elements in the list.
  • Space complexity: (O(n))
    • We are using a dictionary to store the transformed values and the original numbers, which in the worst case requires space proportional to the number of elements in the list.

Code

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        mapped_values = defaultdict(list)
        for num in nums:
            if num == 0:
                mapped_values[mapping[num]].append(num)
                continue
            curr = 0
            n = 0
            x = num
            while num > 0:
                digit = num % 10
                num //= 10
                curr = curr + mapping[digit] * (10 ** n)
                n += 1
            mapped_values[curr].append(x)

        keys = sorted(mapped_values.keys())
        res = []
        for k in keys:
            res.extend(mapped_values[k])
        return res

Editorial

Approach 1: Conversion using strings and Sorting

class Solution:
    def sortJumbled(self, mapping, nums):
        store_pairs = []

        for i in range(len(nums)):
            # Convert current value to string
            number = str(nums[i])
            formed = ""
            for j in range(len(number)):
                formed = formed + str(mapping[int(number[j])])
            # Store the mapped value.
            mapped_value = int(formed)
            # Push a pair consisting of mapped value and original value's index.
            store_pairs.append((mapped_value, i))

        # Sort the array in non-decreasing order by the first value (default).
        store_pairs.sort()
        answer = []
        for pair in store_pairs:
            answer.append(nums[pair[1]])
        return answer

Approach 2: Conversion without using strings and Sorting

class Solution:
    def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
        store_pairs = []

        for i in range(len(nums)):
            mapped_value = 0
            temp = nums[i]

            # Start making changes from the units place.
            place = 1
            # If the value initially is 0, return mapping[0] and index.
            if temp == 0:
                store_pairs.append((mapping[0], i))
                continue
            # Repeat the process for units, tenths, hundredths.. places.
            while temp != 0:
                mapped_value = place * mapping[temp % 10] + mapped_value
                place *= 10
                temp //= 10
            store_pairs.append((mapped_value, i))

        # Sort the array in non-decreasing order by the first value (default).
        store_pairs.sort()
        answer = [nums[pair[1]] for pair in store_pairs]

        return answer

You may also enjoy