Skip to main content
Talentd

Smallest Value of the Rearranged Number - Solution & Explanation

MediumMathSorting15 min readAsked at: Microsoft, Cognizant
Practice this problem

Problem Statement

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) for sorting.
Space Complexity: O(n) for storing digit characters.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sort Digits for Minimal Positive Number

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.

Sort Digits for Maximum Negative Number

Time Complexity: O(n log n) for sorting.
Space Complexity: O(n) for storing digit characters.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort Digits for Minimal Positive NumberO(d log d)O(d)When the number is positive and you must avoid leading zeros while minimizing value
Sort Digits for Maximum Negative NumberO(d log d)O(d)When the number is negative and the goal is maximizing magnitude to produce the smallest numeric value

Video Solution

2165. Smallest Value of the Rearranged Number || LeetCode 2165 || Weekly LeetCode 279 • Bro Coders • 1,306 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Smallest Value of the Rearranged Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Largest Number