Smallest Value of the Rearranged Number solution and explanation
8 more videos on this problem
2165. Smallest Value of the Rearranged Number || LeetCode 2165 || Weekly LeetCode 279Bro Coders · 7:38 · 1K views
Smallest Value of the Rearranged Number| Leetcode 2165 | Contest 279 | Arrays Sorting Easy Peasy 🔥🔥Coding Decoded · 6:01 · 1K views
LeetCode 2165. Smallest Value of the Rearranged Number | PythonLea's coding · 3:00 · 448 views
2165. Smallest Value of the Rearranged Number (Leetcode Medium)Programming Live with Larry · 6:42 · 385 views
Leetcode 2165 - Smallest Value of Rearranged NumberSameeksha Bhatia · 10:00 · 239 views
2165. Smallest Value of the Rearranged Number Leetcode Weekly contest Medium Problem (Explained)Rajat's corner ; Microsoft | IITG · 11:27 · 57 views
2165. Smallest Value of the Rearranged Number | বাংলা সমাধানOne-Problem-A-Day · 11:43 · 27 views
【Leetcode III 31/100】2165. Smallest Value of the Rearranged Number (~Medium)思臉AI · 2:00 · 7 views
LeetCode 2165: Smallest Value of the Rearranged NumberAlitaCode · 26:54 · 4 views
The problem
You are given an integer num. Rearrange the digits of num such that its value is minimized and it does not contain any leading zeros.
Return the rearranged number with minimal value.
Note that the sign of the number does not change after rearranging the digits.
Example 1:
Input: num = 310 Output: 103 Explanation: The possible arrangements for the digits of 310 are 013, 031, 103, 130, 301, 310. The arrangement with the smallest value that does not contain any leading zeros is 103.
Example 2:
Input: num = -7605 Output: -7650 Explanation: Some possible arrangements for the digits of -7605 are -7650, -6705, -5076, -0567. The arrangement with the smallest value that does not contain any leading zeros is -7650.
Constraints:
-1015 <= num <= 1015
Approach overview
Problem Overview: You receive an integer num and must rearrange its digits to produce the smallest possible numeric value. Leading zeros are not allowed, and negative numbers must remain negative. The trick is handling positive and negative numbers differently while keeping the digit rearrangement valid.
Approach 1: Sort Digits for Minimal Positive Number (O(d log d) time, O(d) space)
For positive numbers, the smallest value comes from arranging digits in ascending order. A direct sort works, but leading zeros would produce invalid numbers like 00123. After sorting, move the first non-zero digit to the front, then place all zeros immediately after it, followed by the remaining digits. Implementation steps: convert the number to a digit array, sort it, scan for the first non-zero digit, swap it to index 0, and rebuild the integer. Sorting dominates the cost, giving O(d log d) time where d is the number of digits, and O(d) space for the digit list.
This approach relies on basic sorting mechanics and simple digit manipulation. It's reliable and easy to implement across languages.
Approach 2: Sort Digits for Maximum Negative Number (O(d log d) time, O(d) space)
Negative numbers flip the goal. The smallest numeric value is the most negative one, which means maximizing the magnitude of the number before applying the negative sign. Extract the digits from the absolute value and sort them in descending order. Reconstruct the number from these digits and apply the negative sign at the end. Example: -310 becomes digits [3,1,0], sorted descending to [3,1,0], giving -310, which is smaller than alternatives like -130.
The key insight: minimizing a negative number means maximizing its absolute value. Sorting digits in reverse order achieves that directly. Like the positive case, the complexity comes from sorting, resulting in O(d log d) time and O(d) auxiliary space. The logic mainly uses integer manipulation and concepts from math and digit processing.
Recommended for interviews: Interviewers expect the digit-sorting solution. It shows you recognize how sign changes the optimization goal. Handling the leading-zero edge case for positive numbers demonstrates attention to detail, while reversing the sort for negatives shows strong problem decomposition.
Approach 1: Sort Digits for Minimal Positive Number
For a positive integer, rearrange its digits in ascending order to achieve the smallest possible number. Special handling is required to prevent leading zeros. The smallest non-zero digit should precede any zeros.
def minimize_positive_number(num):
digits = list(str(num))
digits.sort()
for i in range(len(digits)):
if digits[i] != '0':
digits[0], digits[i] = digits[i], digits[0]
break
return int(''.join(digits))
num = 310
print(minimize_positive_number(num))import java.util.Arrays;
public class Main {
public static long minimizePositiveNumber(long num) {
char[] digits = Long.toString(num).toCharArray();
Arrays.sort(digits);
for (int i = 0; i < digits.length; i++) {
if (digits[i] != '0') {
char temp = digits[0];
digits[0] = digits[i];
digits[i] = temp;
break;
}
}
return Long.parseLong(new String(digits));
}
public static void main(String[] args) {
long num = 310;
System.out.println(minimizePositiveNumber(num));
}
}#include <iostream>
#include <algorithm>
#include <string>
long long minimizePositiveNumber(long long num) {
std::string digits = std::to_string(num);
std::sort(digits.begin(), digits.end());
auto zero_position = digits.find_first_not_of('0');
if (zero_position != std::string::npos) {
std::swap(digits[0], digits[zero_position]);
}
return std::stoll(digits);
}
int main() {
long long num = 310;
std::cout << minimizePositiveNumber(num) << std::endl;
return 0;
}function minimizePositiveNumber(num) {
let digits = num.toString().split('').sort();
for (let i = 0; i < digits.length; i++) {
if (digits[i] !== '0') {
[digits[0], digits[i]] = [digits[i], digits[0]];
break;
}
}
return parseInt(digits.join(''), 10);
}
const num = 310;
console.log(minimizePositiveNumber(num));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void *a, const void *b) {
return (*(char *)a - *(char *)b);
}
long long minimizePositiveNumber(long long num) {
char digits[20];
sprintf(digits, "%lld", num);
qsort(digits, strlen(digits), sizeof(char), compare);
for (int i = 0; digits[i] == '0'; i++) {
if (digits[i + 1] != '0') {
char temp = digits[i];
digits[i] = digits[i + 1];
digits[i + 1] = temp;
break;
}
}
return atoll(digits);
}
int main() {
long long num = 310;
printf("%lld\n", minimizePositiveNumber(num));
return 0;
}using System;
class Program {
static long MinimizePositiveNumber(long num) {
char[] digits = num.ToString().ToCharArray();
Array.Sort(digits);
for (int i = 0; i < digits.Length; i++) {
if (digits[i] != '0') {
char temp = digits[0];
digits[0] = digits[i];
digits[i] = temp;
break;
}
}
return long.Parse(new string(digits));
}
static void Main() {
long num = 310;
Console.WriteLine(MinimizePositiveNumber(num));
}
}Python aligns with the described approach, converting the number to a sorted list of digits, and then correcting possible leading zeros.
Time Complexity: O(n log n), for sorting the digits.
Space Complexity: O(n), to store the list of digits.
Approach 2: Sort Digits for Maximum Negative Number
For a negative integer, rearrange its digits in descending order to achieve the most negative value without altering the number's sign. The negative sign influences this ordering.
def minimize_negative_number(num):
num = -num # Work with positive
digits = sorted(str(num), reverse=True)
return -int(''.join(digits))
num = -7605
print(minimize_negative_number(num))import java.util.Arrays;
import java.util.Collections;
public class Main {
public static long minimizeNegativeNumber(long num) {
num = -num; // Work with positive
String digits = Long.toString(num);
Character[] chars = new Character[digits.length()];
for (int i = 0; i < digits.length(); i++) {
chars[i] = digits.charAt(i);
}
Arrays.sort(chars, Collections.reverseOrder());
StringBuilder sortedDigits = new StringBuilder();
for (char c : chars) {
sortedDigits.append(c);
}
return -Long.parseLong(sortedDigits.toString());
}
public static void main(String[] args) {
long num = -7605;
System.out.println(minimizeNegativeNumber(num));
}
}#include <iostream>
#include <algorithm>
#include <string>
long long minimizeNegativeNumber(long long num) {
num = -num; // Handle as positive
std::string digits = std::to_string(num);
std::sort(digits.rbegin(), digits.rend());
return -std::stoll(digits);
}
int main() {
long long num = -7605;
std::cout << minimizeNegativeNumber(num) << std::endl;
return 0;
}function minimizeNegativeNumber(num) {
num = -num; // Handle absolute value
let digits = num.toString().split('').sort((a, b) => b - a);
return -parseInt(digits.join(''), 10);
}
const num = -7605;
console.log(minimizeNegativeNumber(num));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compareDesc(const void *a, const void *b) {
return (*(char *)b - *(char *)a);
}
long long minimizeNegativeNumber(long long num) {
num = -num; // Work with positive magnitude
char digits[20];
sprintf(digits, "%lld", num);
qsort(digits, strlen(digits), sizeof(char), compareDesc);
return -atoll(digits);
}
int main() {
long long num = -7605;
printf("%lld\n", minimizeNegativeNumber(num));
return 0;
}using System;
using System.Linq;
class Program {
static long MinimizeNegativeNumber(long num) {
num = -num; // Convert for sorting
char[] digits = num.ToString().ToCharArray();
Array.Sort(digits, (x, y) => y.CompareTo(x));
return -long.Parse(new string(digits));
}
static void Main() {
long num = -7605;
Console.WriteLine(MinimizeNegativeNumber(num));
}
}Python sorts digits in descending order using reverse sorting for negative numbers.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(n), as we store the digits temporarily.
Approach 3: Counting
We first use an array cnt to record the number of occurrences of each digit in num.
If num is negative, the digits should be arranged in descending order. Therefore, we traverse cnt from 9 to 0 and arrange the digits in descending order according to their occurrences.
If num is positive, we first find the first non-zero digit and place it in the first position, then arrange the remaining digits in ascending order.
The time complexity is O(log n), where n is the size of the number num. The space complexity is O(1).
function smallestNumber(num: number): number {
const neg = num < 0;
num = Math.abs(num);
const cnt = Array(10).fill(0);
while (num > 0) {
cnt[num % 10]++;
num = Math.floor(num / 10);
}
let ans = 0;
if (neg) {
for (let i = 9; i >= 0; i--) {
while (cnt[i] > 0) {
ans = ans * 10 + i;
cnt[i]--;
}
}
return -ans;
}
if (cnt[0] > 0) {
for (let i = 1; i < 10; i++) {
if (cnt[i] > 0) {
cnt[i]--;
ans = i;
break;
}
}
}
for (let i = 0; i < 10; i++) {
while (cnt[i] > 0) {
ans = ans * 10 + i;
cnt[i]--;
}
}
return ans;
}func smallestNumber(num int64) (ans int64) {
neg := num < 0
num = max(num, -num)
cnt := make([]int, 10)
for num > 0 {
cnt[num%10]++
num /= 10
}
if neg {
for i := 9; i >= 0; i-- {
for cnt[i] > 0 {
ans = ans*10 + int64(i)
cnt[i]--
}
}
return -ans
}
if cnt[0] > 0 {
for i := 1; i < 10; i++ {
if cnt[i] > 0 {
cnt[i]--
ans = int64(i)
break
}
}
}
for i := 0; i < 10; i++ {
for cnt[i] > 0 {
ans = ans*10 + int64(i)
cnt[i]--
}
}
return ans
}impl Solution {
pub fn smallest_number(num: i64) -> i64 {
let mut neg = num < 0;
let mut num = num.abs();
let mut cnt = vec![0; 10];
while num > 0 {
cnt[(num % 10) as usize] += 1;
num /= 10;
}
let mut ans = 0;
if neg {
for i in (0..10).rev() {
while cnt[i] > 0 {
ans = ans * 10 + i as i64;
cnt[i] -= 1;
}
}
return -ans;
}
if cnt[0] > 0 {
for i in 1..10 {
if cnt[i] > 0 {
cnt[i] -= 1;
ans = i as i64;
break;
}
}
}
for i in 0..10 {
while cnt[i] > 0 {
ans = ans * 10 + i as i64;
cnt[i] -= 1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sort Digits for Minimal Positive Number | Time Complexity: O(n log n), for sorting the digits. |
| Sort Digits for Maximum Negative Number | Time Complexity: O(n log n) for sorting. |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort Digits for Minimal Positive Number | O(d log d) | O(d) | When the number is positive and you must avoid leading zeros while minimizing value |
| Sort Digits for Maximum Negative Number | O(d log d) | O(d) | When the number is negative and the goal is maximizing magnitude to produce the smallest numeric value |
Frequently asked questions
Is Smallest Value of the Rearranged Number easy or hard?
LeetCode classifies this problem as Medium. The core logic is straightforward sorting, but handling negative numbers and avoiding leading zeros introduces edge cases that often trip up candidates.
Smallest Value of the Rearranged Number Python/Java solution
Python and Java implementations follow the same steps: convert the number to a string or extract digits mathematically, store digits in a list, sort them appropriately, handle leading zeros for positive numbers, and reconstruct the integer. Both languages achieve O(d log d) time complexity.
How to solve Smallest Value of the Rearranged Number in O(n)?
An O(d) solution is possible using counting sort because digits range from 0 to 9. Count the frequency of each digit, then reconstruct the number in ascending order for positive values or descending order for negative values. This removes the need for comparison-based sorting.
What is the best approach for Smallest Value of the Rearranged Number?
The standard approach sorts the digits of the number. For positive numbers, sort digits in ascending order and move the first non-zero digit to the front to avoid leading zeros. For negative numbers, sort digits in descending order and then apply the negative sign. This approach runs in O(d log d) time where d is the number of digits.
Is Smallest Value of the Rearranged Number asked at Google/Amazon/Meta?
Digit manipulation and sorting problems like this appear in interviews at companies such as Amazon, Google, and Microsoft. While the exact problem may vary, the pattern of rearranging digits to optimize numeric value is commonly tested in coding interviews.
What data structure is used in Smallest Value of the Rearranged Number?
The solution typically uses a dynamic array or list to store digits extracted from the number. A sorting algorithm is then applied to this array. Some optimized versions use a frequency array of size 10 to count digits.
What is the time complexity of Smallest Value of the Rearranged Number?
The dominant operation is sorting the digits of the number. If the number contains d digits, sorting takes O(d log d) time and rebuilding the number takes O(d). The total time complexity is O(d log d) with O(d) auxiliary space.