MediumNo. 2191
Sort the Jumbled Numbers — LeetCode 2191 Python Solution
- Pattern
- Sorting
- Topics
- Array, Sorting
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- 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:
Python solution
class Solution:
def sortJumbled(self, mapping: List[int], nums: List[int]) -> List[int]:
def f(x: int) -> int:
if x == 0:
return mapping[0]
y, k = 0, 1
while x:
x, v = divmod(x, 10)
v = mapping[v]
y = k * v + y
k *= 10
return y
arr = sorted((f(x), i) for i, x in enumerate(nums))
return [nums[i] for _, i in arr]Complexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 2191. Sort the Jumbled Numbers is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0056 | Merge Intervals | Medium |
| 0164 | Maximum Gap | Medium |
| 0274 | H-Index | Medium |
| 0406 | Queue Reconstruction by Height | Medium |
| 0414 | Third Maximum Number | Easy |
| 0462 | Minimum Moves to Equal Array Elements II | Medium |
Frequently asked questions
- How hard is LeetCode 2191. Sort the Jumbled Numbers?
LeetCode 2191. Sort the Jumbled Numbers is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2191. Sort the Jumbled Numbers?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 2191. Sort the Jumbled Numbers?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2191. Sort the Jumbled Numbers cover?
LeetCode 2191. Sort the Jumbled Numbers is tagged Array and Sorting on LeetCode.