Leetcode 2191: Sort the Jumbled Numbers
You are given a mapping array where each index represents a digit, and the value at each index represents the mapped digit in a shuffled decimal system. You are also given an integer array ’nums’. Your task is to sort the array ’nums’ in non-decreasing order based on the mapped values of each element. While sorting, the original integers in ’nums’ should not be changed, only their mapped values should be considered for sorting.
Problem
Approach
Steps
Complexity
Input: The input consists of two arrays: an integer array 'mapping' and an integer array 'nums'.
Example: Input: mapping = [2,4,0,7,1,9,6,3,8,5], nums = [352,124,718]
Constraints:
• mapping.length == 10
• 0 <= mapping[i] <= 9
• All values of mapping[i] are unique.
• 1 <= nums.length <= 3 * 10^4
• 0 <= nums[i] < 10^9
Output: Return the array 'nums' sorted in non-decreasing order based on the mapped values of the elements.
Example: Output: [124,352,718]
Constraints:
• The elements in 'nums' should be sorted based on their mapped values and not be replaced by them.
Goal: The goal is to sort the numbers in 'nums' by their mapped values, where each digit of a number is replaced by the corresponding value in the 'mapping' array.
Steps:
• For each number in 'nums', generate its mapped value by replacing each digit according to the 'mapping' array.
• Store the mapped values along with the original numbers and their indices.
• Sort the numbers based on their mapped values while preserving their original relative order when mapped values are the same.
• Return the sorted array based on the original numbers.
Goal: Conditions that the solution must meet.
Steps:
• The length of the 'mapping' array is fixed to 10.
• All values in 'mapping' are unique.
• The length of 'nums' can be up to 30,000 elements.
• Each number in 'nums' is less than 10^9.
Assumptions:
• The mapping array has unique digits, meaning no digit maps to the same value.
• The numbers in 'nums' are valid integers that follow the constraints.
• Input: Input: mapping = [2,4,0,7,1,9,6,3,8,5], nums = [352,124,718]
• Explanation: For each number in 'nums', the digits are mapped according to the 'mapping' array. After mapping, we get the values 822 for 352, 214 for 124, and 278 for 718. Sorting these mapped values results in the order [214,822,278], corresponding to the original numbers [124,352,718].
• Input: Input: mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123]
• Explanation: In this case, the mapping does not change the digits because mapping[i] = i. Thus, 789 maps to 789, 456 maps to 456, and 123 maps to 123. Sorting the values results in [123, 456, 789], which is the correct output.
Approach: The approach involves generating the mapped values for each element in 'nums' by applying the 'mapping' array and then sorting the elements based on those mapped values.
Observations:
• We need to generate the mapped value for each number by replacing its digits according to the 'mapping' array.
• Sorting the elements based on their mapped values is a key aspect, while maintaining the original order when mapped values are the same.
• We can achieve this by converting each number into a string, applying the mapping to each digit, and then sorting the numbers based on the mapped results.
Steps:
• For each number in 'nums', convert it to a string and apply the mapping for each digit.
• Convert the mapped string back to an integer to get the mapped value.
• Pair the original number with its mapped value and its original index.
• Sort these pairs based on the mapped values, preserving the original relative order for elements with the same mapped value.
• Extract the sorted numbers based on the original indices and return the result.
Empty Inputs:
• There will always be at least one number in 'nums', so empty inputs are not a concern.
Large Inputs:
• Ensure the solution works for large inputs, up to 30,000 numbers in 'nums'.
Special Values:
• Consider cases where all digits in 'nums' map to the same value or where the mapping array results in no change to the numbers.
Constraints:
• Ensure that the solution meets time complexity constraints, especially for large inputs.
vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
vector<pair<int, int>> tmp;
int n = nums.size();
for(int i = 0; i < n; i++) {
int num = nums[i];
string str = to_string(num);
string formed = "";
for(int j = 0; j < str.size(); j++)
formed += to_string(mapping[str[j]- '0']);
int val = stoi(formed);
tmp.push_back({ val, i });
}
sort(tmp.begin(), tmp.end());
vector<int> ans;
for(int i = 0; i < n; i++)
ans.push_back(nums[tmp[i].second]);
return ans;
}
1 : Function Definition
vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
Defines the function 'sortJumbled' which takes a vector 'mapping' and a vector 'nums' as inputs, and returns the sorted version of 'nums' after replacing each digit with its corresponding value from 'mapping'.
2 : Variable Initialization
vector<pair<int, int>> tmp;
Initializes a vector of pairs 'tmp' to store pairs of transformed numbers and their original indices.
3 : Size Calculation
int n = nums.size();
Calculates the size of the 'nums' vector and stores it in the variable 'n'.
4 : Loop
for(int i = 0; i < n; i++) {
Starts a loop to iterate through each element of the 'nums' vector.
5 : Element Access
int num = nums[i];
Accesses the 'i'th element of the 'nums' vector and stores it in the variable 'num'.
6 : String Conversion
string str = to_string(num);
Converts the integer 'num' to a string 'str'.
7 : String Initialization
string formed = "";
Initializes an empty string 'formed' to build the transformed version of 'num'.
8 : Loop through Digits
for(int j = 0; j < str.size(); j++)
Iterates through each digit of the string 'str'.
9 : Digit Transformation
formed += to_string(mapping[str[j]- '0']);
For each digit 'str[j]', replaces it with the corresponding value from the 'mapping' vector and appends it to 'formed'.
10 : String Conversion
int val = stoi(formed);
Converts the transformed string 'formed' back to an integer and stores it in 'val'.
11 : Storing Transformed Data
tmp.push_back({ val, i });
Pushes the transformed integer 'val' and its original index 'i' as a pair into the 'tmp' vector.
12 : Sorting
sort(tmp.begin(), tmp.end());
Sorts the 'tmp' vector based on the transformed values of the numbers.
13 : Result Vector Initialization
vector<int> ans;
Initializes an empty vector 'ans' to store the final sorted numbers.
14 : Loop through Sorted Data
for(int i = 0; i < n; i++)
Iterates through the sorted 'tmp' vector to extract the numbers in their original order.
15 : Extracting Sorted Numbers
ans.push_back(nums[tmp[i].second]);
Pushes the original number from 'nums' (using the index stored in 'tmp[i].second') into the 'ans' vector.
16 : Return Statement
return ans;
Returns the sorted 'ans' vector containing the original numbers in the desired order.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is dominated by the sorting step, which is O(n log n), where n is the length of 'nums'.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage of the mapped values and the original numbers.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus