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 <= 1015Problem 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.
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.
The C solution sorts the digits of the positive number. If leading zeros are produced, it swaps the first non-zero digit to the front.
Time Complexity: O(n log n), where n is the number of digits in num, due to sorting.
Space Complexity: O(n), used for storing the digits as characters.
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.
For negative numbers, the idea is to sort the digits in descending order, which results in a greater negative number when the original negative sign is reapplied.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(n) for storing digit characters.
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).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Sort Digits for Minimal Positive Number | Time Complexity: O(n log n), where n is the number of digits in num, due to sorting. |
| Sort Digits for Maximum Negative Number | Time Complexity: O(n log n) for sorting. |
| Counting | — |
| 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 |
2165. Smallest Value of the Rearranged Number || LeetCode 2165 || Weekly LeetCode 279 • Bro Coders • 1,288 views views
Watch 8 more video solutions →Practice Smallest Value of the Rearranged Number with our built-in code editor and test cases.
Practice on FleetCode