Convert a non-negative integer num to its English words representation.
Example 1:
Input: num = 123 Output: "One Hundred Twenty Three"
Example 2:
Input: num = 12345 Output: "Twelve Thousand Three Hundred Forty Five"
Example 3:
Input: num = 1234567 Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
Constraints:
0 <= num <= 231 - 1Problem Overview: Convert a non‑negative integer into its English words representation. For example, 12345 becomes "Twelve Thousand Three Hundred Forty Five". The main challenge is handling number groupings (thousands, millions, billions) while correctly formatting hundreds, tens, and units.
Approach 1: Recursive Approach with Segmentation (O(log n) time, O(log n) space)
This approach breaks the number into major segments: billions, millions, thousands, and the remaining hundreds. A recursive helper converts numbers smaller than 1000 into words by processing hundreds, tens, and units. Each recursive call reduces the number by a factor of 1000, so the depth remains small. The key idea is mapping numbers 1-19 and multiples of ten while recursively composing phrases like "Million" or "Thousand". This pattern fits naturally with recursion because each chunk is processed independently.
Approach 2: Iterative Approach with Stack (O(log n) time, O(log n) space)
The number is repeatedly divided into three-digit chunks while pushing segments onto a stack. Each chunk is converted to words and combined with its scale label (Thousand, Million, etc.). Using a stack ensures segments appear in the correct order when building the final sentence. This method avoids recursion while still following the same chunking logic. It works well when implementing the solution in languages where explicit stack handling is clearer than recursive calls.
Approach 3: Recursive Chunking Approach (O(log n) time, O(log n) space)
This variation treats the number as repeated chunks of size 1000. The algorithm recursively processes num // 1000 first, then converts the remaining num % 1000. The resulting phrase appends the corresponding scale word based on the recursion depth. Compared with segmentation by fixed ranges, this version uses cleaner recursive composition and reduces conditional branches. It relies heavily on lookup arrays and string composition, combining ideas from string manipulation and math decomposition.
Approach 4: Iterative Approach with Number Mapping (O(log n) time, O(1) space)
This method iterates through predefined magnitude values such as 1_000_000_000, 1_000_000, and 1_000. For each magnitude, divide the number to determine how many units exist, convert that portion to words, then append the corresponding scale label. A helper function converts numbers below 1000 using arrays for units and tens. Because the number of magnitudes is fixed, the extra memory usage stays constant while the algorithm runs in logarithmic time relative to the number of digits.
Recommended for interviews: The recursive segmentation approach is usually expected. It clearly shows how you decompose the number into thousands-based chunks and reuse a helper for numbers under 1000. Interviewers look for clean mapping tables and correct handling of edge cases like 0, teens, and trailing spaces. Implementing the iterative magnitude version is also acceptable, but recursion demonstrates stronger problem decomposition skills.
This approach utilizes recursion to convert the integer into segments of hundreds, thousands, millions, and billions, and then converts each of these segments into words using a predefined dictionary. This method divides and conquers the problem by handling one segment at a time.
This Python solution decomposes the number recursively into segments of 1000 using integer division and modulus operations. The function helper converts numbers below 1000 to words. The main function iterates over increasing powers of thousand, converts each segment, and concatenates them with appropriate thousand scales.
Time Complexity: O(1), since the number of segments is constant. Space Complexity: O(1), due to constant space usage for building the output string.
An iterative approach using a stack can sequentially build the English words representation by handling one segment of the number at a time. This non-recursive method is useful in avoiding too deep recursion especially with large numbers.
This JavaScript solution uses iteration and a helper function to convert each segment of the number into English words. Similar to the recursive solution, it iteratively processes segments in the order of ones, thousands, millions, and so on. This approach uses string concatenation and avoids recursion depth issues.
Time Complexity: O(1), as the number of operations is fixed for a constant set of segments. Space Complexity: O(1), using constant space for string manipulation.
This approach breaks down the number into smaller chunks of thousands and recursively converts each chunk into words. By handling different magnitudes separately, such as thousands, millions, etc., the problem becomes more manageable.
This solution uses recursion to handle chunks of up to three digits: ones, tens, and hundreds, separately. It utilizes lists to map integer values to their corresponding English word equivalents for numbers up to nineteen, tens, and big chunks (thousands, millions, billions). When a chunk is processed, it concatenates the word value, and processes recursively for larger chunks.
Time Complexity: O(log(num)) - Because the number is processed in chunks of thousands.
Space Complexity: O(log(num)) - Due to the recursion stack when handling each chunk.
This approach uses an iterative method to convert the integer into words by dividing the number into parts less than 1000 and mapping each part to its English equivalent. The algorithm keeps updating the resultant string by concatenating appropriate word segments.
The solution involves converting each part of the number separated by thousands into words iteratively. It uses arrays to map numbers to words, efficiently processing up to two-digit numbers, and recursively handling hundreds, enhancing both clarity and performance.
Time Complexity: O(log(num)) - Efficient handling by breaking number into segments.
Space Complexity: O(1) - Iterative approach minimizes auxiliary space usage.
| Approach | Complexity |
|---|---|
| Recursive Approach with Segmentation | Time Complexity: O(1), since the number of segments is constant. Space Complexity: O(1), due to constant space usage for building the output string. |
| Iterative Approach with Stack | Time Complexity: O(1), as the number of operations is fixed for a constant set of segments. Space Complexity: O(1), using constant space for string manipulation. |
| Recursive Chunking Approach | Time Complexity: O(log(num)) - Because the number is processed in chunks of thousands. |
| Iterative Approach with Number Mapping | Time Complexity: O(log(num)) - Efficient handling by breaking number into segments. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Approach with Segmentation | O(log n) | O(log n) | Clean recursive design; common interview solution |
| Iterative Approach with Stack | O(log n) | O(log n) | When avoiding recursion or building output in reverse order |
| Recursive Chunking Approach | O(log n) | O(log n) | Simpler recursive structure using repeated 1000‑based chunks |
| Iterative Approach with Number Mapping | O(log n) | O(1) | Efficient iterative implementation with fixed magnitude checks |
Integer to English Words - Leetcode 273 - Python • NeetCodeIO • 19,279 views views
Watch 9 more video solutions →Practice Integer to English Words with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor