LeetCode 2165 - Smallest Value of the Rearranged Number

In this problem, we are given an integer num, which may be positive, negative, or zero. Our goal is to rearrange its digits so that the resulting number is as small as possible while preserving the original sign. The important detail is that the sign cannot change.

leetcodemediummathsorting

LeetCode Problem 2165

Difficulty: 🟡 Medium
Topics: Math, Sorting

Solution

Problem Understanding

In this problem, we are given an integer num, which may be positive, negative, or zero. Our goal is to rearrange its digits so that the resulting number is as small as possible while preserving the original sign.

The important detail is that the sign cannot change. If the number is positive, the rearranged number must also remain positive. If the number is negative, the rearranged number must stay negative.

The problem also states that the resulting number cannot contain leading zeros. This means that for positive numbers, we cannot place 0 at the beginning of the rearranged number. For example, rearranging 310 into 013 is invalid because integers do not allow leading zeros in their representation.

For negative numbers, the interpretation is slightly different. Since a more negative number is numerically smaller, we actually want to maximize the absolute value. For example:

  • -7650 < -6705
  • Therefore -7650 is considered smaller

This means:

  • Positive numbers should have their digits arranged in ascending order
  • Negative numbers should have their digits arranged in descending order

The constraints are relatively small:

  • -10^15 <= num <= 10^15

A number with magnitude 10^15 has at most 16 digits including the sign, so the input size is tiny. This means sorting digits is completely feasible.

Some important edge cases include:

  • Numbers containing many zeros, such as 100200
  • Numbers that are already minimal
  • Negative numbers
  • The value 0
  • Numbers with repeated digits
  • Positive numbers where the smallest digit is 0

A naive implementation can easily fail when handling leading zeros correctly.

Approaches

Brute Force Approach

A brute force solution would generate every possible permutation of the digits, convert each permutation into a valid number, filter out arrangements with leading zeros, and then select the minimum valid value.

For example, for 310, we would generate:

  • 013
  • 031
  • 103
  • 130
  • 301
  • 310

Then we discard invalid leading-zero numbers and choose the smallest remaining value.

This approach is correct because it explicitly checks every possible arrangement. However, it is computationally impractical because the number of permutations grows factorially.

If the number has n digits, there are n! permutations. Even with only 15 digits, this becomes astronomically large.

Optimal Approach

The key observation is that we do not need to try every permutation. We only need to construct the lexicographically smallest valid arrangement.

For positive numbers:

  • Sort digits in ascending order
  • Move the first non-zero digit to the front
  • Place all zeros immediately after it
  • Append the remaining digits

This guarantees the smallest possible positive number without leading zeros.

For negative numbers:

  • Sort digits in descending order
  • Build the largest possible absolute value
  • Reapply the negative sign

This works because among negative numbers, a larger magnitude corresponds to a smaller value.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n! × n) O(n!) Generates all digit permutations
Optimal O(n log n) O(n) Uses sorting and greedy digit placement

Algorithm Walkthrough

Positive Number Case

  1. Convert the number into a list of digit characters.

This makes it easy to sort and rearrange individual digits. 2. Sort the digits in ascending order.

Smaller digits should appear earlier because we want the smallest possible value. 3. Handle leading zeros carefully.

After sorting, zeros may appear at the front. A leading zero is invalid, so we locate the first non-zero digit and move it to the beginning. 4. Keep all remaining digits in ascending order.

Once the first digit is fixed as the smallest non-zero digit, the rest should remain sorted to minimize the overall number. 5. Convert the rearranged digit list back into an integer.

Negative Number Case

  1. Remove the negative sign by taking the absolute value.
  2. Convert digits into a list.
  3. Sort digits in descending order.

For negative numbers, a larger absolute value produces a smaller final number. 4. Join the digits into a number. 5. Reapply the negative sign.

Special Case: Zero

If the input is 0, the result is simply 0.

Why it works

For positive numbers, placing the smallest non-zero digit first guarantees the smallest valid leading digit. Keeping the remaining digits in ascending order minimizes every subsequent position.

For negative numbers, maximizing the absolute value produces the numerically smallest negative number because larger magnitudes are more negative.

These greedy choices are always optimal because digit positions contribute independently according to place value.

Python Solution

class Solution:
    def smallestNumber(self, num: int) -> int:
        if num == 0:
            return 0

        # Negative number case
        if num < 0:
            digits = list(str(-num))
            digits.sort(reverse=True)

            return -int("".join(digits))

        # Positive number case
        digits = list(str(num))
        digits.sort()

        # Find first non-zero digit
        first_non_zero = 0
        while digits[first_non_zero] == '0':
            first_non_zero += 1

        # Place smallest non-zero digit first
        digits[0], digits[first_non_zero] = (
            digits[first_non_zero],
            digits[0],
        )

        return int("".join(digits))

The implementation starts by handling the simplest special case, 0.

For negative numbers, the code converts the absolute value into digits, sorts them in descending order, joins them back together, and reapplies the negative sign.

For positive numbers, the digits are sorted in ascending order. Since zeros may appear at the front, the algorithm scans for the first non-zero digit and swaps it into the leading position. This preserves the smallest possible arrangement while avoiding leading zeros.

Finally, the digits are joined and converted back into an integer.

Go Solution

package main

import (
	"sort"
	"strconv"
)

func smallestNumber(num int64) int64 {
	if num == 0 {
		return 0
	}

	// Negative number case
	if num < 0 {
		digits := []byte(strconv.FormatInt(-num, 10))

		sort.Slice(digits, func(i, j int) bool {
			return digits[i] > digits[j]
		})

		value, _ := strconv.ParseInt(string(digits), 10, 64)
		return -value
	}

	// Positive number case
	digits := []byte(strconv.FormatInt(num, 10))

	sort.Slice(digits, func(i, j int) bool {
		return digits[i] < digits[j]
	})

	// Find first non-zero digit
	firstNonZero := 0
	for digits[firstNonZero] == '0' {
		firstNonZero++
	}

	// Swap into front position
	digits[0], digits[firstNonZero] =
		digits[firstNonZero], digits[0]

	value, _ := strconv.ParseInt(string(digits), 10, 64)

	return value
}

The Go solution follows the same logic as the Python implementation.

One important difference is that Go uses []byte to manipulate characters efficiently. Sorting is implemented using sort.Slice, which allows custom comparison functions.

The final number is reconstructed using strconv.ParseInt.

Because the constraint is limited to 10^15, all results safely fit inside int64.

Worked Examples

Example 1

Input:

num = 310

Step 1: Convert to digits

Operation Result
Digits ['3', '1', '0']

Step 2: Sort ascending

Operation Result
Sorted digits ['0', '1', '3']

Step 3: Find first non-zero digit

Index Digit
0 0
1 1

First non-zero digit is at index 1.

Step 4: Swap into front

Before Swap After Swap
['0', '1', '3'] ['1', '0', '3']

Step 5: Build number

103

Output:

103

Example 2

Input:

num = -7605

Step 1: Remove sign

7605

Step 2: Convert to digits

Operation Result
Digits ['7', '6', '0', '5']

Step 3: Sort descending

Operation Result
Sorted digits ['7', '6', '5', '0']

Step 4: Build number

7650

Step 5: Reapply negative sign

-7650

Output:

-7650

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting the digits dominates the runtime
Space O(n) Stores the digit array

The number of digits is at most 16, so the algorithm is extremely efficient in practice. The sorting step dominates the runtime complexity.

Test Cases

solution = Solution()

assert solution.smallestNumber(310) == 103          # example case
assert solution.smallestNumber(-7605) == -7650     # negative example
assert solution.smallestNumber(0) == 0             # zero input
assert solution.smallestNumber(100) == 100         # leading zero handling
assert solution.smallestNumber(9070) == 7009       # multiple zeros
assert solution.smallestNumber(-1002) == -2100     # negative with zeros
assert solution.smallestNumber(12345) == 12345     # already minimal
assert solution.smallestNumber(54321) == 12345     # reverse sorted positive
assert solution.smallestNumber(-54321) == -54321   # already optimal negative
assert solution.smallestNumber(1000000) == 1000000 # many zeros
assert solution.smallestNumber(11111) == 11111     # repeated digits
assert solution.smallestNumber(-11111) == -11111   # repeated negative digits
assert solution.smallestNumber(9000000001) == 1000000009 # large zeros case
Test Why
310 Basic positive example
-7605 Basic negative example
0 Special zero case
100 Ensures no leading zeros
9070 Multiple zeros in positive number
-1002 Negative number with zeros
12345 Already minimal arrangement
54321 Requires full reordering
-54321 Negative already optimal
1000000 Many trailing zeros
11111 Repeated digits
-11111 Repeated negative digits
9000000001 Large input with many zeros

Edge Cases

Positive Numbers With Leading Zeros After Sorting

A very common bug occurs when sorting digits of a positive number containing zeros. For example, sorting 310 directly produces 013, which is invalid because integers cannot contain leading zeros.

The implementation fixes this by locating the first non-zero digit and swapping it into the front position.

Negative Numbers

Negative numbers reverse the optimization logic. For positive numbers we minimize the absolute value, but for negative numbers we maximize it.

For example:

  • -7650 < -5067

A naive solution that always sorts ascending would fail here. The implementation correctly sorts digits in descending order for negative inputs.

Input Equal to Zero

The number 0 is a special case because it has only one digit and no rearrangement is necessary.

Without explicitly handling this case, some implementations may attempt unnecessary digit processing. The solution immediately returns 0.

Numbers With Repeated Digits

Repeated digits can sometimes expose bugs in swapping logic or sorting assumptions.

For example:

11111

All permutations are identical, so the output should remain unchanged.

The implementation naturally handles this because sorting repeated digits does not alter their arrangement incorrectly.