Sort the Jumbled Numbers - Practice Coding Problems

Sort the Jumbled Numbers - Problem

Array Sorting Medium

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.

Note: Elements with the same mapped values should appear in the same relative order as in the input.

Input & Output

Example 1 — Basic Case

$ Input: mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991,338,38]

› Output: [338,38,991]

💡 Note: 991 maps to 669, 338 maps to 007 (which is 7), 38 maps to 07 (which is 7). Since 7 < 669, both 338 and 38 come before 991. Since 338 and 38 have the same mapped value, they maintain their original relative order.

Example 2 — Different Mapping

$ Input: mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123]

› Output: [123,456,789]

💡 Note: With identity mapping, numbers stay the same: 789→789, 456→456, 123→123. Sorted: [123,456,789].

Example 3 — All Same Mapped Value

$ Input: mapping = [1,1,1,1,1,1,1,1,1,1], nums = [12,21,3]

› Output: [12,21,3]

💡 Note: All numbers map to same digits (1): 12→11, 21→11, 3→1. Since all mapped values are different (11, 11, 1), sort by mapped values: 3 maps to 1, others to 11, so [3,12,21]. But 12 and 21 both map to 11, so original order preserved.

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⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Original array with digit mapping rule

Transform

Map each digit to create new values

Sort

Sort by mapped values, preserve original order for ties

Key Takeaway

🎯 Key Insight: Transform numbers using digit mapping, then sort by transformed values while maintaining stability for equal mapped values

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is to transform each number using the mapping array to get its "mapped value", then sort the original numbers based on these mapped values while preserving relative order for equal mapped values. The optimal approach uses a stable sort with a custom key function. Time: O(n log n + m), Space: O(m) where n is array length and m is total digits.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Manual Mapping	O(n log n + m)	O(n + m)	Map each number digit by digit, store pairs, then sort
Optimized with Stable Sort	O(n log n + m)	O(m)	Use built-in stable sort with custom key function

Brute Force with Manual Mapping — Algorithm Steps

Map each number to its transformed value
Create pairs of (original, mapped)
Sort pairs by mapped values
Extract original numbers in sorted order

Visualization

Tap to expand

Step-by-Step Walkthrough

Map Numbers

Transform each number using mapping

Create Pairs

Store (mapped_value, index, original)

Sort Pairs

Sort by mapped values

Extract Result

Get original numbers in sorted order

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int mappedVal;
    int index;
    int original;
} Pair;

int mapNumber(int num, int* mapping) {
    char numStr[20];
    sprintf(numStr, "%d", num);
    char mappedStr[100] = "";
    
    for (int i = 0; numStr[i]; i++) {
        int digit = numStr[i] - '0';
        char temp[10];
        sprintf(temp, "%d", mapping[digit]);
        strcat(mappedStr, temp);
    }
    return atoi(mappedStr);
}

int compare(const void* a, const void* b) {
    Pair* pa = (Pair*)a;
    Pair* pb = (Pair*)b;
    if (pa->mappedVal != pb->mappedVal) {
        return pa->mappedVal - pb->mappedVal;
    }
    return pa->index - pb->index;
}

int* solution(int* mapping, int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    Pair* pairs = (Pair*)malloc(numsSize * sizeof(Pair));
    
    for (int i = 0; i < numsSize; i++) {
        pairs[i].mappedVal = mapNumber(nums[i], mapping);
        pairs[i].index = i;
        pairs[i].original = nums[i];
    }
    
    qsort(pairs, numsSize, sizeof(Pair), compare);
    
    int* result = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        result[i] = pairs[i].original;
    }
    
    free(pairs);
    return result;
}

int main() {
    int mapping[10];
    int nums[1000];
    int numsSize = 0;
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse mapping array
    char* token = strtok(line + 1, ",]");
    for (int i = 0; i < 10 && token; i++) {
        mapping[i] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Parse nums array
    fgets(line, sizeof(line), stdin);
    token = strtok(line + 1, ",]");
    while (token) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(mapping, nums, numsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m)

n log n for sorting, m for total digits in all numbers

⚡ Linearithmic

Space Complexity

O(n + m)

n pairs stored, m space for mapped value strings

⚡ Linearithmic Space

15.2K Views

Medium Frequency

~15 min Avg. Time

423 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Manual Mapping — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler