Watch 9 video solutions for Smallest Value of the Rearranged Number, a medium level problem involving Math, Sorting. This walkthrough by Bro Coders has 1,288 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |