Integer to English Words - Solution & Explanation
Problem Statement
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 - 1
Approach Overview
Problem Overview: Convert a non‑negative integer into its English words representation. For example, 123 becomes "One Hundred Twenty Three". The challenge is handling number groupings such as thousands, millions, and billions while formatting words correctly.
Approach 1: Recursive Approach with Segmentation (O(log n) time, O(log n) space)
Break the number into segments: billions, millions, thousands, and the remaining hundreds. For each segment, recursively convert values below 1000 using mappings for numbers under 20 and multiples of ten. Each recursive call handles a smaller portion of the number and appends the corresponding scale word like Thousand or Million. This works well because English number naming naturally follows a recursive hierarchy. Space complexity is O(log n) due to recursion depth.
Approach 2: Iterative Approach with Stack (O(log n) time, O(log n) space)
Instead of recursion, push number chunks (groups of three digits) onto a stack while repeatedly dividing the number by 1000. Process each chunk by converting values under 1000 using predefined word maps, then append the correct scale word when popping from the stack. The stack ensures the highest magnitude segments appear first in the final string. This approach avoids recursion while preserving the natural ordering of billions → millions → thousands → hundreds.
Approach 3: Recursive Chunking Approach (O(log n) time, O(log n) space)
Process the number by recursively reducing it with thresholds such as 1,000,000,000, 1,000,000, and 1,000. Each recursion splits the number into num / scale and num % scale. Convert the left portion first, append the scale word, then recursively process the remainder. Because each recursion removes the highest magnitude chunk, the call depth stays small (bounded by the number of digit groups). This approach is concise and closely mirrors how humans read numbers.
Approach 4: Iterative Approach with Number Mapping (O(log n) time, O(1) space)
Use arrays that map integers to their word equivalents (0–19, tens, and scale names). Iteratively extract three-digit chunks using num % 1000, convert them with helper logic, and prepend the corresponding scale word. Because the number of scales is fixed (billion, million, thousand), auxiliary memory stays constant aside from the output string. This approach is often preferred in languages like Java due to its predictable control flow and minimal recursion.
Recommended for interviews: The recursive segmentation approach is usually the clearest to explain. It directly reflects the structure of English number naming and keeps the implementation compact. Interviewers typically expect a clean mapping strategy for numbers under 20 and tens, combined with recursive handling of thousands and above. Practicing problems involving recursion, string manipulation, and math decomposition helps build the intuition needed for this pattern.
Approach 1: Recursive Approach with Segmentation
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.
Code
Python
Complexity
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.
Approach 2: Iterative Approach with Stack
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.
Code
JavaScript
Complexity
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.
Approach 3: Recursive Chunking Approach
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.
Code
Python
Complexity
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.
Approach 4: Iterative Approach with Number Mapping
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.
Code
Java
Complexity
Time Complexity: O(log(num)) - Efficient handling by breaking number into segments.
Space Complexity: O(1) - Iterative approach minimizes auxiliary space usage.
Approach 5: Default Approach
Code
Python
Java
C++
Go
TypeScript
JavaScript
C#
Complexity Comparison
| 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. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Approach with Segmentation | O(log n) | O(log n) | Clean and intuitive solution that mirrors the hierarchical structure of English numbers |
| Iterative Approach with Stack | O(log n) | O(log n) | Useful when avoiding recursion or when processing chunks in reverse order |
| Recursive Chunking Approach | O(log n) | O(log n) | Concise recursive design that repeatedly splits the number by scale thresholds |
| Iterative Approach with Number Mapping | O(log n) | O(1) | Best when implementing in strongly typed languages with simple loops and fixed mappings |
Video Solution
Integer to English Words - Leetcode 273 - Python • NeetCodeIO • 25,981 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Integer to English Words easy or hard?
Integer to English Words Python/Java solution
How to solve Integer to English Words in O(log n)?
What is the best approach for Integer to English Words?
Is Integer to English Words asked at Google/Amazon/Meta?
What data structure is used in Integer to English Words?
What is the time complexity of Integer to English Words?
Ready to solve this problem?
Practice Integer to English Words with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor