Sort the Jumbled Numbers
Problem Description:
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.
Notes:
1. Elements with the same mapped values should appear in the same relative order as in the input.
2. The elements of nums should only be sorted based on their mapped values and not be replaced by them.
Examples:
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:
mapping[9] = 6, so all occurrences of the digit 9 will become 6.
mapping[1] = 9, so all occurrences of the digit 1 will become 9.
Therefore, the mapped value of 991 is 669.
338 maps to 007, or 7 after removing the leading zeros.
38 maps to 07, which is also 7 after removing leading zeros.
Since 338 and 38 share the same mapped value, they should remain in the same relative order, so 338 comes before 38.
Thus, the sorted array is [338,38,991].
Input: mapping = [0,1,2,3,4,5,6,7,8,9], nums = [789,456,123]
Output: [123,456,789]
Explanation: 789 maps to 789, 456 maps to 456, and 123 maps to 123.
Thus, the sorted array is [123,456,789].
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⁹
Brute Force Approach
Okay, so here's the thought process:
What comes to mind after reading the problem statement?
We need to change each digit of every number in nums to its matching value from the mapping array. Then, we sort the numbers based on these new values in ascending order, but we return the original numbers in this sorted order.
We first replace each digit of every number in nums with its corresponding value from the mapping array to get a new "mapped value" for each number. Using these mapped values, we sort the numbers in ascending order. If two numbers have the same mapped value, their original order in nums is preserved. Finally, instead of returning the mapped values, we return the original numbers in this sorted order. This ensures the numbers are arranged based on the new values without changing their original content.
How to do it?
To solve this problem, we start by calculating the mapped value for each number in the array nums. The mapped value is obtained by replacing every digit of the number with its corresponding value from the mapping array. Once we have these mapped values, we store them along with the original numbers as pairs (e.g., (mapped_value, original_value)). These pairs allow us to sort the numbers based on their mapped values while still keeping track of the original numbers, which need to be returned in the end.
Next, we need to sort the array of pairs based on their mapped values. To do this, we can use a simple sorting algorithm like bubble sort. In bubble sort, we repeatedly compare adjacent pairs in the array. If the mapped value of the second pair is smaller than that of the first, we swap the two pairs. This process is repeated for every pair in the array, ensuring that the largest mapped values "bubble up" to the end of the array in each pass. By the end of the sorting process, all the pairs are arranged in ascending order based on their mapped values.
Finally, once the array of pairs is sorted, we extract only the original numbers from the pairs in their new order. These original numbers are returned as the final sorted array. This way, the numbers in nums are rearranged based on their mapped values, but we return them in their original form as required.
To extract the mapped value of a number, you can use two common approaches:
- String Conversion Approach:
- Convert the number into a string.
- For every character (digit) in the string, look up the corresponding value from the mapping array.
- Replace the original character with its mapped value and reconstruct the number.
- Modulus and Division Approach:
- Take out each digit of the number by repeatedly using modulus 10 (num % 10) to get the last digit.
- Replace the last digit with its mapped value using the mapping array.
- To move to the next digit, divide the number by 10 (num /= 10), and repeat the process for all digits.
Let's understand with an example:
Input: mapping = [8,9,4,0,2,1,3,5,7,6], nums = [991, 338, 38]
Step 1: Calculate mapped values and form pairs
- 991 → Map digits: 9 → 6, 1 → 9 → Mapped value = 669 → Pair: (669, 991)
- 338 → Map digits: 3 → 0, 8 → 7 → Mapped value = 7 → Pair: (7, 338)
- 38 → Map digits: 3 → 0, 8 → 7 → Mapped value = 7 → Pair: (7, 38)
Pairs: [(669, 991), (7, 338), (7, 38)]
Step 2: Sort pairs based on mapped values
Use bubble sort:
- Compare (669, 991) and (7, 338) → Swap → [(7, 338), (669, 991), (7, 38)]
- Compare (669, 991) and (7, 38) → Swap → [(7, 338), (7, 38), (669, 991)]
- Compare (7, 338) and (7, 38) → Keep order (since their mapped values are equal, maintain relative order).
Sorted pairs: [(7, 338), (7, 38), (669, 991)]
Step 3: Extract original numbers
From the sorted pairs, extract the original numbers in order: [338, 38, 991]
Output: [338, 38, 991]
How to code it up:
Here are the concise steps to code the solution:
- Create a Data Structure to Store Pairs:
- Create a vector to store pairs of (mapped_value, original_value).
- Calculate Mapped Values:
- For each number in the input array nums, calculate its mapped value:
- Convert the number to a string to process each digit.
- Replace each digit using the mapping array.
- Convert the resulting mapped string back to an integer.
- Store the pair (mapped_value, original_value) in the vector.
- Sort the Pairs Using Bubble Sort:
- Use a nested loop to compare adjacent pairs in the vector.
- If the mapped value of a pair is greater than the next, swap them.
- Repeat the process for all pairs until the vector is sorted.
- Extract the Original Values:
- Once the vector of pairs is sorted, extract only the original_value from each pair.
- Store these values in the result array.
- Return the Result:
- Return the array of sorted original values.
Code Implementation
1. C++ Try on Compiler
class Solution {
// Helper function to compute the mapped value of a number
int getMappedValue(int num, const vector<int>& mapping) {
string numStr = to_string(num);
string mappedStr;
for (char digit : numStr) {
mappedStr += to_string(mapping[digit - '0']);
}
return stoi(mappedStr); // Convert the mapped string back to an integer
}
public:
vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
// Step 1: Create a vector of pairs to store the mapped value and the original number
vector<pair<int, int>> pairs;
// Calculate the mapped value for each number in nums
for (int num : nums) {
int mappedValue = getMappedValue(num, mapping);
pairs.push_back({mappedValue, num});
}
// Step 2: Use bubble sort to sort the pairs based on the mapped value
int n = pairs.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (pairs[j].first > pairs[j + 1].first) {
// Swap if the mapped value of the current pair is greater
swap(pairs[j], pairs[j + 1]);
}
}
}
// Step 3: Extract the original numbers from the sorted pairs
vector<int> sortedNums;
for (const auto& p : pairs) {
sortedNums.push_back(p.second);
}
return sortedNums;
}
};2. Java Try on Compiler
import java.util.*;
class Solution {
// Helper function to compute the mapped value of a number
private int getMappedValue(int num, int[] mapping) {
String numStr = Integer.toString(num);
StringBuilder mappedStr = new StringBuilder();
for (char digit : numStr.toCharArray()) {
mappedStr.append(mapping[digit - '0']);
}
return Integer.parseInt(mappedStr.toString()); // Convert the mapped string back to an integer
}
public int[] sortJumbled(int[] mapping, int[] nums) {
// Step 1: Create a list of pairs to store the mapped value and the original number
List<int[]> pairs = new ArrayList<>();
// Calculate the mapped value for each number in nums
for (int num : nums) {
int mappedValue = getMappedValue(num, mapping);
pairs.add(new int[]{mappedValue, num});
}
// Step 2: Use bubble sort to sort the pairs based on the mapped value
int n = pairs.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (pairs.get(j)[0] > pairs.get(j + 1)[0]) {
// Swap if the mapped value of the current pair is greater
Collections.swap(pairs, j, j + 1);
}
}
}
// Step 3: Extract the original numbers from the sorted pairs
int[] sortedNums = new int[nums.length];
for (int i = 0; i < pairs.size(); ++i) {
sortedNums[i] = pairs.get(i)[1];
}
return sortedNums;
}
}
3. Python Try on Compiler
class Solution:
# Helper function to compute the mapped value of a number
def getMappedValue(self, num, mapping):
numStr = str(num)
mappedStr = ""
for digit in numStr:
mappedStr += str(mapping[int(digit)])
return int(mappedStr) # Convert the mapped string back to an integer
def sortJumbled(self, mapping, nums):
# Step 1: Create a list of pairs to store the mapped value and the original number
pairs = []
# Calculate the mapped value for each number in nums
for num in nums:
mappedValue = self.getMappedValue(num, mapping)
pairs.append((mappedValue, num))
# Step 2: Use bubble sort to sort the pairs based on the mapped value
n = len(pairs)
for i in range(n - 1):
for j in range(n - i - 1):
if pairs[j][0] > pairs[j + 1][0]:
# Swap if the mapped value of the current pair is greater
pairs[j], pairs[j + 1] = pairs[j + 1], pairs[j]
# Step 3: Extract the original numbers from the sorted pairs
sortedNums = [p[1] for p in pairs]
return sortedNums
4. Javascript Try on Compiler
/**
* @param {number[]} mapping
* @param {number[]} nums
* @return {number[]}
*/
// Helper function to compute the mapped value of a number
var getMappedValue = function (num, mapping) {
let numStr = num.toString();
let mappedStr = "";
for (let digit of numStr) {
mappedStr += mapping[digit - '0'];
}
return parseInt(mappedStr); // Convert the mapped string back to an integer
}
var sortJumbled = function (mapping, nums) {
// Step 1: Create an array of pairs to store the mapped value and the original number
let pairs = [];
// Calculate the mapped value for each number in nums
for (let num of nums) {
let mappedValue = getMappedValue(num, mapping);
pairs.push([mappedValue, num]);
}
// Step 2: Use bubble sort to sort the pairs based on the mapped value
let n = pairs.length;
for (let i = 0; i < n - 1; ++i) {
for (let j = 0; j < n - i - 1; ++j) {
if (pairs[j][0] > pairs[j + 1][0]) {
// Swap if the mapped value of the current pair is greater
[pairs[j], pairs[j + 1]] = [pairs[j + 1], pairs[j]];
}
}
}
// Step 3: Extract the original numbers from the sorted pairs
let sortedNums = pairs.map(p => p[1]);
return sortedNums;
};Time Complexity: O(n²)
The time complexity of this approach can be broken down into the following steps:
- Calculating Mapped Values:
For each number in nums, we need to calculate its mapped value.The number of digits in a number can be at most O(log(num)), where num is the value of the number.
For each number in nums, we perform operations proportional to the number of digits in that number, so calculating the mapped value for all n numbers takes O(n * d) time, where d is the average number of digits in the numbers. - Bubble Sort:
Bubble sort has a time complexity of O(n²), where n is the number of elements to be sorted. In this case, we are sorting n pairs (each pair contains the mapped value and the original number). - Extracting Original Numbers:
Extracting the original numbers from the sorted pairs requires O(n) time, since we simply iterate over the sorted pairs once to collect the original numbers.
Total Time Complexity:
- Time to calculate mapped values: O(n * d)
- Time to sort pairs using bubble sort: O(n²)
- Time to extract original numbers: O(n)
Thus, the overall time complexity is dominated by the bubble sort step, resulting in: O(n² + n * d), which simplifies to O(n²) when n is large, because n² dominates over n * d.
Conclusion: The overall time complexity of this approach is O(n²), where n is the number of elements in nums.
Space Complexity: O(n)
Auxiliary Space Complexity: O(n)
Explanation: The space required for storing the pairs of (mapped_value, original_value) is O(n), where n is the number of elements in nums.
The mappedStr used in the helper function has space complexity of O(d), where d is constant (at most 10). Since d is constant, we can treat this as O(1).
Total Space Complexity: O(n)
Explanation: The input arrays mapping (fixed size of 10) and nums (size n) require O(1) and O(n) space, respectively.
Therefore, the total space used by the algorithm is O(n).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n²), which is not suitable for n ≤ 10⁴. This means that for each test case, where the size of the array is at most 10⁴, the solution might not execute within the given time limits.
Since O(n²) results in a maximum of 10⁸ operations (for n = 10⁴), the solution is not expected to work well for larger test cases. In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning that for n ≤ 10⁸, the solution with 10⁸ operations is not efficient enough.
When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10⁸ operations, especially when there are many test cases or the value of n increases.
Thus, while the solution meets the time limits for a single test case, the O(n²) time complexity poses a risk for Time Limit Exceeded (TLE) errors when handling larger input sizes or multiple test cases. This can be a challenge for competitive programming problems with larger inputs or numerous test cases
Can we optimize it?
In our previous approach, we determined the mapped values of each element in the array nums by replacing its digits according to the given mapping array. Then, we sorted these elements based on their mapped values in ascending order using bubble sort. Finally, we returned the original elements in the sorted order based on their mapped values. However, while this approach works, it is not the most efficient since bubble sort has a time complexity of O(n²).
So, how can we optimize this? The answer is simple: instead of bubble sort, we can use more efficient sorting algorithms like merge sort or heap sort, which reduce the time complexity to O(n log n). But using these algorithms might make the code lengthy and more complex to implement. Is there a more concise and efficient option?
Yes, we can use the inbuilt sort() function! This function is widely available in many programming languages and allows us to sort collections (like arrays, lists, or vectors) in ascending order by default. Furthermore, it provides the ability to define a custom comparator, which makes it versatile and perfect for our use case. The custom comparator lets us define our sorting logic, making the code both concise and efficient.
In our optimized approach, the first step is to pair each element in the nums array with its corresponding mapped value. To calculate the mapped value for a number, we replace each digit of the number with the digit specified in the given mapping array. This allows us to create a vector of pairs, where each pair contains the original number and its calculated mapped value.
Once we have this vector of pairs, we can use the inbuilt sort() function to sort the elements efficiently. The sort() function not only sorts elements in ascending order by default, but it also allows us to use a custom comparator function. This comparator will define the logic for comparing two pairs.
For two pairs:
- If their mapped values are different, the comparator will place the pair with the smaller mapped value first. This ensures that the numbers are sorted in ascending order based on their mapped values.
- If two pairs have the same mapped value, we need to preserve the order of these numbers as they appeared in the original nums array. This is achieved by comparing the original indices of the numbers—whichever number appears earlier in the input array is placed first. This aspect of the comparator ensures stability, meaning elements with the same mapped value retain their original relative order.
By using this logic, the comparator helps us handle all sorting scenarios efficiently. It ensures that the sorted order respects both the mapped values and the original order for ties, giving us a result that meets the problem’s requirements while keeping the code concise and easy to understand.
By using this approach, we achieve sorting in O(n log n) time, which is significantly faster than bubble sort’s O(n²) time complexity. Moreover, the use of the sort() function makes our code concise, readable, and easy to implement. This way, we effectively reduce the computational complexity while maintaining clarity in the logic and ensuring the stability of the sorting process.
Let's understand with an example:
Input: mapping = [8, 9, 4, 0, 2, 1, 3, 5, 7, 6], nums = [991, 338, 38]
Step 1: Calculate Mapped Values
- For 991:
- Digits are 9, 9, 1.
- Mapped values: mapping[9] = 6, mapping[9] = 6, mapping[1] = 9.
- Mapped value = 669.
- For 338:
- Digits are 3, 3, 8.
- Mapped values: mapping[3] = 0, mapping[3] = 0, mapping[8] = 7.
- Mapped value = 007 (or simply 7).
- For 38:
- Digits are 3, 8.
- Mapped values: mapping[3] = 0, mapping[8] = 7.
- Mapped value = 07 (or simply 7).
Pairs:
[(669, 991), (7, 338), (7, 38)]
Step 2: Sort Pairs by Mapped Value (Custom Comparator)
- Compare (7, 338) with (7, 38) → Both have the same mapped value. Use the original order → 338 comes before 38.
- Compare (7, 338) with (669, 991) → 7 < 669.
Sorted Pairs:
[(7, 338), (7, 38), (669, 991)]
Step 3: Extract Original Values from Sorted Pairs
[338, 38, 991]
Output: [338, 38, 991]
How to code it up?
Here are concise and generic steps to code the solution:
- Create a Helper Function for Mapped Value Conversion:
Write a function (convert) that takes a number and the mapping array as input.
Replace each digit of the number with its mapped value according to the mapping array.
Combine these mapped digits to form the mapped value. - Create a Vector of Pairs:
Iterate through the input nums array.
For each number, calculate its mapped value using the helper function.
Store the mapped value and the original index of the number as a pair in a new vector. - Sort the Vector of Pairs:
Use the sort() function with a custom comparator.
Sort pairs by their mapped value (first in the pair).
If two mapped values are the same, use the original index (second in the pair) to maintain stability. - Generate the Result:
Create a new vector for the result.
Iterate through the sorted vector of pairs and extract the original numbers from nums using the stored indices. - Return the Result Vector:
Return the sorted vector of original numbers as the final output.
Code Implementation
1. C++ Try on Compiler
class Solution {
// Helper function to convert a number to its mapped value
int convert(int num, vector<int>& map) {
// If the number is 0, return the mapped value of 0 directly
if(num == 0)
return map[0];
// Store the mapped value
int ans = 0;
for(int i = 1; num > 0; i *= 10) {
// Extract the last digit
int temp = num % 10;
// Replace the digit with its mapped value
ans += map[temp] * i;
// Remove the last digit
num /= 10;
}
// Return the final mapped value
return ans;
}
public:
vector<int> sortJumbled(vector<int>& mapping, vector<int>& nums) {
// Vector to store pairs of (mapped value, index)
vector<pair<int, int>> pi;
int n = nums.size();
// Step 1: Calculate the mapped value for each number in nums
for(int i = 0; i < n; i++) {
// Original number
int x = nums[i];
// Get the mapped value
int y = convert(x, mapping);
// Store the mapped value and original index
pi.push_back({y, i});
}
// Step 2: Sort the pairs based on mapped value
sort(pi.begin(), pi.end(), [](pair<int, int> &a, pair<int, int> &b) {
// If mapped values are equal
if(a.first == b.first)
// Sort by original index
return a.second < b.second;
// Otherwise, sort by mapped value
return a.first < b.first;
});
// Vector to store the final sorted result
vector<int> ans;
// Step 3: Extract the original numbers from the sorted pairs
for(auto &p: pi) {
// Use the stored index to get the original number
ans.push_back(nums[p.second]);
}
// Return the sorted result
return ans;
}
};
2. Java Try on Compiler
class Solution {
// Helper function to convert a number to its mapped value
private int convert(int num, int[] map) {
// If the number is 0, return the mapped value of 0 directly
if (num == 0)
return map[0];
// Store the mapped value
int ans = 0;
for (int i = 1; num > 0; i *= 10) {
// Extract the last digit
int temp = num % 10;
// Replace the digit with its mapped value
ans += map[temp] * i;
// Remove the last digit
num /= 10;
}
// Return the final mapped value
return ans;
}
public int[] sortJumbled(int[] mapping, int[] nums) {
// List to store pairs of (mapped value, index)
List<int[]> pi = new ArrayList<>();
int n = nums.length;
// Step 1: Calculate the mapped value for each number in nums
for (int i = 0; i < n; i++) {
// Original number
int x = nums[i];
// Get the mapped value
int y = convert(x, mapping);
// Store the mapped value and original index
pi.add(new int[]{y, i});
}
// Step 2: Sort the pairs based on mapped value
pi.sort((a, b) -> {
// If mapped values are equal
if (a[0] == b[0])
// Sort by original index
return Integer.compare(a[1], b[1]);
// Otherwise, sort by mapped value
return Integer.compare(a[0], b[0]);
});
// Array to store the final sorted result
int[] ans = new int[n];
// Step 3: Extract the original numbers from the sorted pairs
for (int i = 0; i < n; i++) {
// Use the stored index to get the original number
ans[i] = nums[pi.get(i)[1]];
}
// Return the sorted result
return ans;
}
}
3. Python Try on Compiler
class Solution:
# Helper function to convert a number to its mapped value
def convert(self, num, mapping):
# If the number is 0, return the mapped value of 0 directly
if num == 0:
return mapping[0]
# Store the mapped value
ans = 0
i = 1
while num > 0:
# Extract the last digit
temp = num % 10
# Replace the digit with its mapped value
ans += mapping[temp] * i
# Remove the last digit
num //= 10
i *= 10
# Return the final mapped value
return ans
def sortJumbled(self, mapping, nums):
# List to store pairs of (mapped value, index)
pi = []
n = len(nums)
# Step 1: Calculate the mapped value for each number in nums
for i in range(n):
# Original number
x = nums[i]
# Get the mapped value
y = self.convert(x, mapping)
# Store the mapped value and original index
pi.append((y, i))
# Step 2: Sort the pairs based on mapped value
pi.sort(key=lambda a: (a[0], a[1]))
# List to store the final sorted result
ans = []
# Step 3: Extract the original numbers from the sorted pairs
for _, idx in pi:
# Use the stored index to get the original number
ans.append(nums[idx])
# Return the sorted result
return ans
4. Javascript Try on Compiler
/**
* @param {number[]} mapping
* @param {number[]} nums
* @return {number[]}
*/
// Helper function to convert a number to its mapped value
var convert = function (num, map) {
// If the number is 0, return the mapped value of 0 directly
if (num === 0)
return map[0];
// Store the mapped value
let ans = 0;
let i = 1;
while (num > 0) {
// Extract the last digit
let temp = num % 10;
// Replace the digit with its mapped value
ans += map[temp] * i;
// Remove the last digit
num = Math.floor(num / 10);
i *= 10;
}
// Return the final mapped value
return ans;
}
var sortJumbled = function (mapping, nums) {
// Array to store pairs of (mapped value, index)
let pi = [];
let n = nums.length;
// Step 1: Calculate the mapped value for each number in nums
for (let i = 0; i < n; i++) {
// Original number
let x = nums[i];
// Get the mapped value
let y = convert(x, mapping);
// Store the mapped value and original index
pi.push([y, i]);
}
// Step 2: Sort the pairs based on mapped value
pi.sort((a, b) => {
// If mapped values are equal
if (a[0] === b[0])
// Sort by original index
return a[1] - b[1];
// Otherwise, sort by mapped value
return a[0] - b[0];
});
// Array to store the final sorted result
let ans = [];
// Step 3: Extract the original numbers from the sorted pairs
for (let [_, idx] of pi) {
// Use the stored index to get the original number
ans.push(nums[idx]);
}
// Return the sorted result
return ans;
};
Time Complexity: O(n log n)
- Let's break down the time complexity for each part of the code:
Mapping Conversion (convert function): In the convert function, for each number, we process its digits by repeatedly dividing the number by 10 until it becomes 0. For a number with d digits, the number of operations to extract and map each digit is proportional to d, i.e., O(d). Since d is typically on the order of log(num) where num is the value of the number being processed, this operation takes O(log(num)) time per number.
Creating the Pairs (for loop in sortJumbled function): We iterate over all the numbers in nums. For each number, we call the convert function, which takes O(log(num)) time for a number with log(num) digits. Therefore, creating the vector pi takes O(n * log(max(nums))) time, where n is the size of nums and max(nums) is the maximum number in the nums array.
Sorting the Pairs: The sorting step uses the built-in sort() function, which typically uses Timsort or Quicksort in most standard libraries. The time complexity for sorting n pairs is O(n log n). Here, each pair consists of two integers, but since we're only comparing the first element (mapped value) and occasionally the second element (index), the sorting complexity is still O(n log n).
Final Loop to Construct the Result: After sorting, we iterate over the sorted pi array to construct the final result by retrieving the numbers from the nums array based on the sorted indices. This final loop takes O(n) time.
Overall Time Complexity: The total time complexity is the sum of the following components:
- O(n * log(max(nums))) for calculating the mapped values.
- O(n log n) for sorting the pairs.
- O(n) for constructing the final result.
Thus, the overall time complexity is O(n * log(max(nums)) + n log n). Since log(max(nums)) is usually much smaller than n log n (especially for large n), we can approximate the time complexity to be O(n log n).
Space Complexity: O(n)
Auxiliary Space Complexity: O(n)
Explanation: The convert function uses O(d) space to store the intermediate results while processing the digits of a number. However, since the numbers are processed one by one and this space is reused for each number, it does not contribute additional space outside the function.
The main auxiliary space comes from storing the pairs in the vector pi:
We store a pair of (mapped value, index) for each element in the nums array. There are n elements in nums, so the space for the vector pi is O(n).
Therefore, the auxiliary space complexity is O(n) because of the space used by the vector pi and the space used during the convert function execution, which is O(d) but does not add significant extra space.
Total Space Complexity: O(n)
Explanation: The nums vector contains n elements, so it takes O(n) space.
The total space complexity is O(n).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given a string s, find the length of the longest substring without repeating characters.
2. Word Subsets
You are given two lists of words: words1 and words2.
A word from words2 is called a subset of a word in words1 if:All the letters in the word from words2 are present in the word from words1.
And each letter appears at least as many times in the word from words1 as it does in the word from words2.For example:
"wrr" is a subset of "warrior" (because "warrior" has at least 2 'r's and one 'w').
But "wrr" is not a subset of "world" (because "world" doesn’t have 2 'r's).A word from words1 is called universal if:
Every word in words2 is a subset of it.The goal is to return all the universal words from words1.