Abstract / Summary

Rearrange digits so all even digits come before odd digits to form the largest possible number.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 66% (100k+ submissions).

Typical patterns to solve this problem:

• Heap (Priority Queue)
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution.largestInteger method receives a non-negative integer, rearranges its digits while preserving the original parity (even-ness or odd-ness) of each position, and returns the maximum possible integer that respects this constraint. The algorithm works by separating even and odd digits, sorting each group, and then rebuilding the number by selecting the largest remaining digit of the required parity for each original position.

Key Steps

Convert the number to a string

The integer is first transformed into its decimal string representation so that each digit can be processed individually.

s = str(num)

Determine the parity of each digit

A list called parity is built where each element is 0 for an even digit and 1 for an odd digit. The bitwise & 1 operation extracts the least-significant bit of the integer value of each character.

parity = [int(c) & 1 for c in s]

Collect digits by parity

A dictionary digits maps parity values to lists that will hold the corresponding characters. The loop iterates over the indices of the string, appending each character to the list that matches its parity.

digits = {0: [], 1: []}
for i in range(len(s)):
    digits[parity[i]].append(s[i])

Sort each parity list

Both the even-digit list and the odd-digit list are sorted in ascending order. Sorting once per parity group allows the algorithm to later retrieve the largest available digit of the required parity by popping from the end of the list.

digits[0].sort()
digits[1].sort()

Reconstruct the result

An empty string result is prepared. The algorithm walks through the original parity sequence; for each parity value it removes the last element from the corresponding sorted list (the largest remaining digit of that parity) and appends it to result. Because the lists are sorted ascending, pop() retrieves the greatest digit efficiently.

result = ""
for p in parity:
    result += digits[p].pop()

Convert back to integer

Finally, the assembled string is converted back to an integer, which automatically discards any leading zeros that may have been introduced during the rearrangement.

return int(result)

Edge Cases Handled

When the input consists of a single digit, the parity list contains one element, the corresponding digit list holds that single character, and the reconstruction loop simply returns the original digit.

If all digits share the same parity (all even or all odd), one of the parity lists remains empty. The algorithm never attempts to pop from an empty list because the reconstruction loop only accesses the list matching the current parity, which is guaranteed to contain the needed digit.

The case where the number is zero (num = 0) is also covered. The string "0" yields a parity list [0], the even-digit list becomes ['0'], and the final conversion returns 0.

Leading zeros that could appear after sorting (for example, when the smallest even digit is 0) are removed automatically by the final int() conversion, ensuring the returned value has no spurious leading zeros.

Performance Optimizations

The algorithm minimizes the number of expensive operations. By sorting each parity group only once, it avoids repeated ordering work during reconstruction. The use of pop() on the end of a Python list is an O(1) operation, providing fast retrieval of the next largest digit.

Storing parity as a separate list allows the reconstruction loop to run in a single pass without recomputing digit properties. The comment in the code notes that reversing the sorted lists would be more intuitive, but keeping them in ascending order and popping from the end yields better runtime performance due to the constant-time nature of list.pop() at the tail.

Overall, the method processes the input in linear time relative to the number of digits, with the dominant cost being the two sorts, each operating on at most half of the total digits. The design choices keep auxiliary memory usage proportional to the number of digits, and the in-place list operations avoid unnecessary copying.

Imagine you have a big bucket full of number blocks, some are even numbers and some are odd numbers. The computer separates all the even numbers into one pile and all the odd numbers into another pile. Then, it sorts each pile so the biggest numbers are on top.

Now, the computer looks at the original sequence of those numbers to see if it should pull from the even pile or the odd pile. It walks through that original order one by one. If it sees that a spot was held by an even number, it grabs the biggest one currently sitting in the even pile. If it sees that a spot was held by an odd number, it grabs the biggest one from the odd pile. By putting these biggest pieces back into the same spots where the originals used to be, a new, much larger number is created.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java		Python				TS
	WalkCCC	C++	Java		Python
	leetcode.ca	C++	Java		Python			Go	TS
	Progiez	C++	Java		Python
github	black-shadows	C++
	charles-wangkai		Java
	fartem			Ruby
	fsq	C++
	JoshCrozier					JS
	lkwq007				Python
	suxrobGM						C#
	varunu28		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality