Integer to English Words - Video Solutions

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.