Skip to content

2191. Sort the Jumbled Numbers 👍

Approach 1: Sort

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
    vector<int> ans;
    vector<tuple<int, int, int>> A;  // (mapped, index, num)

    for (int i = 0; i < nums.size(); ++i)
      A.emplace_back(getMapped(nums[i], mapping), i, nums[i]);

    ranges::sort(A);

    for (const auto& [_, i, num] : A)
      ans.push_back(num);

    return ans;
  }

 private:
  int getMapped(int num, const vector<int>& mapping) {
    string mapped;
    for (const char c : to_string(num))
      mapped += to_string(mapping[c - '0']);
    return stoi(mapped);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int[] sortJumbled(int[] mapping, int[] nums) {
    int[] ans = new int[nums.length];
    List<int[]> A = new ArrayList<>(); // (mapped, index, num)

    for (int i = 0; i < nums.length; ++i)
      A.add(new int[] {getMapped(nums[i], mapping), i, nums[i]});

    Collections.sort(
        A, (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
    return A.stream().mapToInt(a -> a[2]).toArray();
  }

  private int getMapped(int num, int[] mapping) {
    StringBuilder sb = new StringBuilder();
    for (final char c : String.valueOf(num).toCharArray())
      sb.append(mapping[c - '0']);
    return Integer.parseInt(sb.toString());
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def sortJumbled(self, mapping: list[int], nums: list[int]) -> list[int]:
    def getMapped(num: int) -> int:
      mapped = []
      for c in str(num):
        mapped.append(str(mapping[int(c)]))
      return int(''.join(mapped))
    A = [(getMapped(num), i, num) for i, num in enumerate(nums)]
    return [num for _, i, num in sorted(A)]

Approach 2: Ordered Map

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
    vector<int> ans;
    map<int, vector<int>> mappedToOriginalNums;

    for (const int num : nums)
      mappedToOriginalNums[getMapped(num, mapping)].push_back(num);

    for (const auto& [_, originalNums] : mappedToOriginalNums)
      ans.insert(ans.end(), originalNums.begin(), originalNums.end());

    return ans;
  }

 private:
  int getMapped(int num, const vector<int>& mapping) {
    string mapped;
    for (const char c : to_string(num))
      mapped += to_string(mapping[c - '0']);
    return stoi(mapped);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int[] sortJumbled(int[] mapping, int[] nums) {
    List<Integer> ans = new ArrayList<>();
    TreeMap<Integer, List<Integer>> mappedToOriginalNums = new TreeMap<>();

    for (final int num : nums) {
      final int mapped = getMapped(num, mapping);
      mappedToOriginalNums.putIfAbsent(mapped, new ArrayList<>());
      mappedToOriginalNums.get(mapped).add(num);
    }

    for (List<Integer> originalNums : mappedToOriginalNums.values())
      ans.addAll(originalNums);

    return ans.stream().mapToInt(Integer::intValue).toArray();
  }

  private int getMapped(int num, int[] mapping) {
    StringBuilder sb = new StringBuilder();
    for (final char c : String.valueOf(num).toCharArray())
      sb.append(mapping[c - '0']);
    return Integer.parseInt(sb.toString());
  }
}