[Programming Problem] Boundary of Binary Tree

No Comments

Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes. (The values of the nodes may still be duplicates.)

Left boundary is defined as the path from root to the left-most node. Right boundary is defined as the path from root to the right-most node. If the root doesn’t have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees.

The left-most node is defined as a leaf node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node.

The right-most node is also defined by the same way with left and right exchanged.

Example 1

Input:
  1
   \
    2
   / \
  3   4
 
Ouput:
[1, 3, 4, 2]
 
Explanation:
The root doesn't have left subtree, so the root itself is left boundary.
The leaves are node 3 and 4.
The right boundary are node 1,2,4. Note the anti-clockwise direction means you should output reversed right boundary.
So order them in anti-clockwise without duplicates and we have [1,3,4,2].

Example 2

Input:
    ____1_____
   /          \
  2            3
 / \          / 
4   5        6   
   / \      / \
  7   8    9  10  
 
Ouput:
[1,2,4,7,8,9,10,6,3]
 
Explanation:
The left boundary are node 1,2,4. (4 is the left-most node according to definition)
The leaves are node 4,7,8,9,10.
The right boundary are node 1,3,6,10. (10 is the right-most node).
So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,6,3].

[Problem Link]

The solution to this problem can be constructed using 3 sets:-

  • Left boundary
  • Leaf Nodes (left to right)
  • Right boundary

Generating these sets is straightforward but we need to be mindful of double counting nodes.

  • Left boundary and right boundary will contain root so best to separate that out.
  • Left boundary’s leftmost node will also be a leaf node (same for right boundary’s rightmost node). Again, best to remove these from those sets.

Our solution will be concatenation of

  • Root Node
  • Left Boundary Nodes (without the last leaf node)
  • Leaf nodes (from left to right)
  • In reverse, Right Boundary Nodes (without the last leaf node)
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
 
// get all leaf nodes (left to right)
var preOrder = function(root, level, leafs) {
    if (!root) return;
    if (!root.left && !root.right && level !== 0) leafs.push(root.val);    
    preOrder(root.left, level+1, leafs);
    preOrder(root.right, level+1, leafs);
}
 
var boundaryOfBinaryTree = function(root) {
 
    if (!root) return [];
 
    // get all left boundary nodes
    let leftList = [];
    let curr = root.left;
    while (curr) {
        leftList.push(curr.val);
        if (curr.left) curr = curr.left;
        else curr = curr.right;
    }
    // without the leftmost leaf (because that will already be part of the leaf's list)
    leftList.pop();
 
    // get all right boundary nodes
    let rightList = [];
    curr = root.right;
    while (curr) {
        rightList.push(curr.val);
        if (curr.right) curr = curr.right;
        else curr = curr.left;
    }
    // without the rightmost leaf (because that will already be part of the leaf's list)
    rightList.pop();
 
    // get all leaf nodes
    let leafList = [];
    preOrder(root, 0, leafList);
 
    // Solution is:
    // Root All_Left_Nodes All_Leaf_Nodes Reverse(All_Right_Nodes)
    // Remember to remove last leaf node from All_Left_Nodes and All_Right_Nodes otherwise you will double count!
 
    return ([root.val]).
            concat(leftList).
            concat(leafList).
            concat(rightList.reverse());
};

[Programming Problem] Deepest Leaves Sum

No Comments

Given a binary tree, return the sum of values of its deepest leaves.

Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

[Problem Link]

Algorithm

  • Traverse through the tree using a level variable (which tells you which level you’re at).
  • When you reach a leaf, maintain a key map of level->sum.
  • In the end, pick the highest key from the map and output the value (as result).

Also TIL, that Property order is predictable in JavaScript objects since ES2015. Quoting from this article “All properties that are integer indices appear first in the overall object property order and are sorted numerically.”. This means we don’t need to sort the leaf map (by key) before returning the result.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
 
var calcLeafMap = function(root, level, leafMap) {
    if (!root) return;
    if (!root.left && !root.right) {
        if (!leafMap[level]) leafMap[level] = 0;
        leafMap[level] += root.val;
    }    
    calcLeafMap(root.left, level+1, leafMap);
    calcLeafMap(root.right, level+1, leafMap);
};
 
var deepestLeavesSum = function(root) {
    let leafMap = {};
    calcLeafMap(root, 0, leafMap);
    let sortedLevels = Object.keys(leafMap);
    return leafMap[sortedLevels[sortedLevels.length-1]];
};

[Programming Problem] Minimum Remove to Make Valid Parentheses

No Comments

Given a string s of ‘(‘ , ‘)’ and lowercase English characters.

Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Example 1:
Input: s = “lee(t(c)o)de)”
Output: “lee(t(c)o)de”
Explanation: “lee(t(co)de)” , “lee(t(c)ode)” would also be accepted.

Example 2:
Input: s = “a)b(c)d”
Output: “ab(c)d”

Example 3:
Input: s = “))((”
Output: “”
Explanation: An empty string is also valid.

Example 4:
Input: s = “(a(b(c)d)”
Output: “a(b(c)d)”

[Problem Link]

Initial thought was do a BFS search where each outgoing node is the string without a bracket. At any level if we find a solution, we stop there (for e.g. in below example we would stop at Level 1 itself since we find “ab(c)d”).

                         "a)b(c)d"
 
        "ab(c)d" ✔️      "a)bc)d"      "a)b(cd"
 
  "abc)d"   "ab(cd"        ...           ...

However, above solution will time out.

Instead we use the stack data structure to determine the brackets that cause invalidity of parentheses. These are simply the brackets remaining in the stack (at the end of validity test). With the bracket, we also store the index of the bracket (in the string) which makes it quicker to delete characters from those positions and rebuild valid string.

/**
 * @param {string} s
 * @return {string}
 */
 
// Node representing bracket and its index (in the string)
var Node = function(c, idx) {
    this.c = c;
    this.idx = idx;
}
 
var minRemoveToMakeValid = function(s) {
    let sChars = Array.from(s);
 
    // Use a stack to determine which brackets are causing 'invalidity'
    // We use Node data strcuture so that we know its index's (which makes it easy to remove)
    let stk = [];
    for ( let i = 0 ; i < sChars.length ; i++ ) {
        let curr = new Node(sChars[i], i);
        if ( curr.c === '(' || (curr.c === ')' && stk.length === 0) ) {
            stk.push(curr);
        } else if ( curr.c === ')' ) {
            let prev = stk.pop();
            if ( prev.c === ')' ) {
                stk.push(prev);
                stk.push(curr);
            }
        }
    }
 
    // index'es which we need to remove
    let toDelete = stk.map(function(n) {
        return n.idx;
    });
 
    // build new string!
    let newS = '';
    for ( let i = 0 ; i < sChars.length ; i++ ) {
        if (toDelete.includes(i)) continue;
        newS += sChars[i];
    }
 
    return newS;
};

Insert Delete GetRandom O(1) – Duplicates allowed

No Comments

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.

remove(val): Removes an item val from the collection if present.

getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();
 
// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);
 
// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);
 
// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);
 
// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();
 
// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);
 
// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

[Problem Link]

The idea here is to use a HashMap and Array. As we insert val’s, we have a mapping of val’s and nodes (containing value and index). We also insert the node into an array. At any point of time if we need a random value, we simply generate a random number (between 1 to length of array) and return the value from the array (in O(1) time).

How do we remove an element in O(1) time? First we use the map, to find the node where this element is stored. We then swap that with the last element and finally remove the last element. This works because when we look for a random number, we don’t care about order of elements in the array.

This wont work if you don’t store index’es in Nodes.

Let’s look at an example for remove. Below is the status of the HashMap and array at some point of the program. Note that, #xxx is the reference to the Node object (where we store index and value).

1 -> [#abc  #def  #ghi]
2 -> [#jkl  #mno]
3 -> [#pqr]
 
[#abc  #def  #mno  #ghi  #jkl  #pqr]
 
#abc = { idx: 0, val: 1 }
#def = { idx: 1, val: 1 }
#mno = { idx: 2, val: 2 }
#ghi = { idx: 3, val: 1 }
#jkl = { idx: 4, val: 2 }
#pqr = { idx: 5, val: 3 }
 
After remove(2)
 
1 -> [#abc  #def  #ghi]
2 -> [#jkl]
3 -> [#pqr]
 
[#abc  #def  #pqr  #ghi  #jkl]
 
#abc = { idx: 0, val: 1 }
#def = { idx: 1, val: 1 }
#mno = { idx: 2, val: 2 } (DELETED)
#ghi = { idx: 3, val: 1 }
#jkl = { idx: 4, val: 2 }
#pqr = { idx: 2, val: 3 } (UPDATED INDEX AND POSITION IN ARRAY)

Here is what we need todo to remove(2)

  1. Using the HashMap find positions where ‘2’ is stored. We could pick any position to remove it from (we pick #mno pointing to { idx: 2, val: 2 }).
  2. We then pop the last element (i.e. #pqr pointing to { idx: 5, val: 3 })
  3. We need to replace the reference in the array from #mno to #pqr.
    this.arr[removeNode.idx] = lastNode;
  4. Note, at this point #pqr index is still 5, we simply update that to the correct index
    lastNode.idx = removeNode.idx;
/**
 * Initialize your data structure here.
 */
var RandomizedCollection = function() {
    this.arr = [];
    this.map = {};
    this.Node = function(val, idx) {
        this.val = val;
        this.idx = idx;
    }
};
 
/**
 * Inserts a value to the collection. Returns true if the collection did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.insert = function(val) {
    if (!this.map[val]) this.map[val] = [];
    let newNode = new this.Node(val, this.arr.length);
    this.arr.push(newNode);
    this.map[val].push(newNode);
    //console.log('insert', val, this.arr);
    return this.map[val].length === 1;
};
 
/**
 * Removes a value from the collection. Returns true if the collection contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.remove = function(val) {
    if (!this.map[val] || this.map[val].length === 0) return false;
    let removeNode = this.map[val].pop();
    let lastNode = this.arr.pop();
    if ( removeNode.idx !== lastNode.idx ) {
        lastNode.idx = removeNode.idx;
        this.arr[removeNode.idx] = lastNode;
    }
    //console.log('remove', val, this.map);
    //console.log(this.arr)
    return true;
};
 
/**
 * Get a random element from the collection.
 * @return {number}
 */
RandomizedCollection.prototype.getRandom = function() {
    if (this.arr.length < 1) return;
    let randomIdx = Math.floor(Math.random() * this.arr.length);
    //console.log('random', randomIdx, this.arr, this.arr.length)
    return this.arr[randomIdx].val;
};
 
/** 
 * Your RandomizedCollection object will be instantiated and called as such:
 * var obj = new RandomizedCollection()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

[Programming Problem] Closest Binary Search Tree Value I and II

No Comments

Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286

    4
   / \
  2   5
 / \
1   3

Output: 4

[Problem Link]

Since this is a BST, if the current node is larger than target, we look in the left subtree, else in the right subtree. In the end we simply return the value we get back from our recursion or the current node value depending on whichever one is closer to target. Remember to account for null values when we encounter a leaf node.

Time complexity is O(lgN)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @return {number}
 */
var closestValue = function(root, target) {
    if (!root) return null;
 
    let minNext;
    if (root.val > target) minNext = closestValue(root.left, target);
    else minNext = closestValue(root.right, target); 
 
    let minCurrDist = Math.abs(root.val-target);
    let minNextDist = minNext !== null ? Math.abs(minNext-target) : Number.MAX_VALUE;
 
    return minNextDist < minCurrDist ? minNext: root.val;
};

Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

Given target value is a floating point.
You may assume k is always valid, that is: k ≤ total nodes.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Example:

Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

[Problem Link]

Traverse the full tree and keep storing closest distances (to target) in a priority queue. In the end, pop k number of elements from the queue and return the result. Note, the priority queue will be ordered based on distance (and not on the node values).

Time complexity will be O(NLgN), insert N items into a heap.
If we decide to keep the heap size k, it goes to O(NLgK).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
class Node implements Comparable<Node> {
    int val;
    double dist;
    public Node(int val, double dist) {
        this.val = val;
        this.dist = dist;
    }
    public int compareTo(Node o) {
        return this.dist < o.dist ? -1 : 1;
    }
}
 
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        PriorityQueue<Node> q = new PriorityQueue<Node>();
        traverseBST(root, target, q);
        List<Integer> ret = new ArrayList<Integer>();
        for ( int i = 0 ; i < k ; i++ ) {
            ret.add(q.poll().val);
        }
        return ret;
    }
 
    public void traverseBST(TreeNode root, double target, PriorityQueue<Node> q) {
        if ( root == null )
            return;
        q.offer(new Node(root.val, Math.abs(root.val - target)));        
        traverseBST(root.left, target, q);
        traverseBST(root.right, target, q);        
    }
}

Another approach would be to traverse (inOrder) through the tree to build a sorted array (i.e. O(n)). Then we use two pointers to get the subarray which has numbers closest to k (i.e. another O(n) time complexity).

Total time complexity for this is: O(n)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} target
 * @param {number} k
 * @return {number[]}
 */
 
function inOrder(root, arr) {
    if (!root) return;
 
    inOrder(root.left, arr);
    arr.push(root.val);
    inOrder(root.right, arr);
}
 
var closestKValues = function(root, target, k) {
    let ret = [];
    inOrder(root, ret);
    let i = 0;
    let j = ret.length - 1;
    while ((j-i+1) != k) {
        let iDist = Math.abs(ret[i] - target);
        let jDist = Math.abs(ret[j] - target);
        if ( iDist < jDist ) j--
        else i++
    }    
    let finalRet = [];
    for ( let start = i ; start <= j ; start++ ) finalRet.push(ret[start]);
    return finalRet;
};

[Programming Problem] Daily Temperatures

No Comments

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

[Problem Link]

If you find a decreasing sequence keep moving forward until you find the number that breaks the sequence. Once you find that, move backward to find temperatures lower than that one. We could use a stack for this.

  1. Keep adding temperatures to a stack.
  2. If current temperature is less than or equal to the last element, add this temperature to the stack.
  3. If you find the current temperature is more than the last element on the stack you’ve found the next highest temperature for it (and possibly some temperatures before that). Keep doing this while the topmost element on the stack is less than the current temperature.

Basically when you find a decreasing sequence, just keep adding it to the stack. When that sequence breaks (meaning you find an element higher than the previous one), keep pop-ing elements from the stack to find temperatures that are lesser than the current temperature. We store indexes (and not actual temperatures) on the stack, so that we can calculate the days elapsed as we go.

Time and space complexity for this would be O(N)

/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function(T) {
    if ( T.length === 0 ) return [];
    let ret = [];
    let arr = [ 0 ];
    T.forEach(function(curr, i) {
        if ( i === 0 ) return;
        while ( arr.length > 0 && T[arr[arr.length-1]] < curr ) {
            let lastElement = arr.pop();
            ret[lastElement] = i - lastElement;
        }
        arr.push(i);
    });
    if ( arr.length > 0 ) {
        arr.forEach(function(curr) {
            ret[curr] = 0;
        });
    }
    return ret;
};

[Programming Problem] Restore IP Addresses

No Comments

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:
 
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

Problem Link

This was an interesting problem. We divide the string into fragments (starting with 4) and return strings at each recursion.

Gotcha 1: for some reason i thought for the final fragment (e.g ‘123’) would return ([‘1’, ‘2’, ‘3’]). if we’re at the last fragment we simply return the string (if its valid).

Gotcha 2: an ip fragment cannot be more than 255 (and it cannot be more than 3 numbers, but if we check if fragment is less than 255, the max char check takes care of itself)

Gotcha 3: Just ‘0’ as a fragment is valid but ‘0xx’ (e.g. ’01’, ‘001’, ‘010’ etc) are not. We need to check for that.

Gotcha 4: an empty ” fragment is invalid! Make sure we check for that and return an empty array.

/**
 * @param {string} s
 * @return {string[]}
 */
 
function isValid(s) {
  if (s.length === 0) return false;
  if (s.length > 1 && s[0] === '0') return false;
  if (s > 255) return false;
  return true;
}
 
function breakString(s, parts) {
  if (parts === 1 && !isValid(s)) return [];
  else if (parts === 1) return [s];
 
  let ret = [];
 
  //break into 3 pieces
  for (let i = 1 ; i <= 3 ; i++ ) {
    let part1 = s.slice(0, i);
    let part2 = s.slice(i);
    if (!isValid(part1)) continue;
    let tmp = breakString(part2, parts-1);
    if (tmp.length === 0 ) continue;
    tmp = tmp.map((str) => part1 + "." + str);
    ret = ret.concat(tmp);      
  }
 
  return ret;
 
}
 
var restoreIpAddresses = function(s) {
    return breakString(s, 4);
};

Time complexity?
https://cs.stackexchange.com/questions/121293/time-complexity-for-the-restore-ip-addresses-problem

[Programming Problem] N-ary Tree Level Order Traversal

No Comments

Given an n-ary tree, return the level order traversal of its nodes’ values.

[Problem Link]

Pretty straightforward BFS traversal logic. Here are some small gotcha’s:

  • Add condition for empty/undefined input.
  • When you return the list of lists, the expectation is to return just values and not the Node object. Notice the last line (ret.map(..)) is doing just that.
/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */
/**
 * @param {Node} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if ( !root || root.length === 0) return [];
    let ret = [[root]];
    let currLevel = 0;
    while (true) {
        let nextLevel = [];
        ret[currLevel].forEach((item) => item.children.forEach((child) => nextLevel.push(child))); 
        if ( nextLevel.length === 0 ) break;
        ret.push(nextLevel);
        currLevel++;
    }    
    return ret.map((arr) => arr.map((item) => item.val))
};

Simplify Path

No Comments

[Problem Link]

  • Tokenize the string with ‘/’ as a delimiter.
  • Create a graph where nodes have pointers to parent nodes.
  • Keep moving up(& down) the graph depending on the directory.
  • If you see a directory, create (or move) to the node (depending on if it exists or not)!
  • Make sure you don’t move above the root node because “Going one level up from the root directory is a no-op”.
  • When you’re done, traverse up to the root node (while creating the path).
  • If the path is empty, return “/”
/**
 * @param {string} path
 * @return {string}
 */
 
function node(val, parent) {
  this.val = val;
  this.parent = parent;
  this.children = [];
 
  this.findChild = function(val) {
    var result = this.children.filter((child) => child.val === val);
    return result && result.length === 1 && result[0];
  }
}
 
var simplifyPath = function(path) {
  var root = new node('', null);
  path.split("/").forEach((dir) => {
    if ( dir ) {
      if ( dir === '..' ) {
        if (root.parent) {
          root = root.parent;
        }
      } else if ( dir !== '.' ) {
        var child = root.findChild(dir);
        if (!child) {
          child = new node('/' + dir, root);
          root.children.push(child);
        }
        root = child;
      }
    }
  })
 
  var ret = '';
  var curr = root;
  while (curr) {
    ret = curr.val + ret;
    curr = curr.parent;
  }
 
  return ret ? ret : '/';
};

Integer to English Words

No Comments

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 – 1.

[Problem Link]

  1. Create a list of numbers for which you have to know the text. For example, there is no way you could come up with text for 1-9, 10-20, 30, 40… without knowing them!
  2. Create a subroutine that solves this problem for 3 digit numbers (up-to 999). If you find the number in the above map return string, else build it. For eg. 123
    1            2 0          3
    - - -      | - - -      | - - -
    ^ Hundred    ^ Twenty     ^ There
  3. Use the above routine to convert digits in batches of 3. Depending on the batch, add Thousand, Million and/or Billion to the converted batch of 3 digits. E.g. to convert 2,190,876,001
    0 0 2          1 9 0        8 7 6         0 0 1
    - - -        | - - -      | - - -       | - - -
    ^ Billion    ^ Million    ^ Thousand

Gotcha’s

  • If num is 0 output “Zero”. This is the only case you will use zero.
  • If any of the 3 digits in the batches are 0, output nothing! E.g. 1000123, make sure you don’t output an extra Thousand anywhere, meaning something like “One Million Thousand One Hundred Twenty Three”.
class Solution {
 
    Map<Integer, String> num2wordsMap = new HashMap<Integer, String>() {{
        put(1, "One");
        put(2, "Two");
        put(3, "Three");
        put(4, "Four");
        put(5, "Five");
        put(6, "Six");
        put(7, "Seven");
        put(8, "Eight");
        put(9, "Nine");
        put(10, "Ten");
        put(11, "Eleven");
        put(12, "Twelve");
        put(13, "Thirteen");
        put(14, "Fourteen");
        put(15, "Fifteen");
        put(16, "Sixteen");
        put(17, "Seventeen");
        put(18, "Eighteen");
        put(19, "Nineteen");
        put(20, "Twenty");
        put(30, "Thirty");
        put(40, "Forty");
        put(50, "Fifty");
        put(60, "Sixty");
        put(70, "Seventy");
        put(80, "Eighty");
        put(90, "Ninety");
        put(100, "One Hundred");
        put(200, "Two Hundred");
        put(300, "Three Hundred");
        put(400, "Four Hundred");
        put(500, "Five Hundred");
        put(600, "Six Hundred");
        put(700, "Seven Hundred");
        put(800, "Eight Hundred");
        put(900, "Nine Hundred");
    }};
 
    public String numberToWords(int num) {
        if (num == 0)
            return "Zero";
 
        String ret = "";
        int index = 0;
        while ( num > 0 ) {
            int lastThree = 0;
            lastThree += (num % 10);
            num /= 10;
            lastThree += ((num % 10)*10);
            num /= 10;
            lastThree += ((num % 10)*100);
            num /= 10;
 
            if (lastThree==0) {
                index++;
                continue;
            }
 
            String threeDigitRet = threeDigitNumberToWords(lastThree);
            if ( index == 0 ) {
                ret = threeDigitRet;
            } else if ( index == 1 ) {
                ret = threeDigitRet + " Thousand " + ret;
            } else if ( index == 2 ) {
                ret = threeDigitRet + " Million " + ret;
            } else if ( index == 3 ) {
                ret = threeDigitRet + " Billion " + ret;
            }
 
            index++;
        }
        return ret.trim();
    }
 
    /**
    * convert 3 numbers to text
    */
    public String threeDigitNumberToWords(int num) {
        int units = num % 10;
        int tens = (num/10) % 10;
        int hundreds = (num/100) % 10;
        int tensNum = tens*10 + units;
 
        String ret = "";
        if (!numberToWordsMap(num).equals("")) {
            ret += numberToWordsMap(num);
        } else {
            ret += hundreds != 0 ? numberToWordsMap(hundreds) + " Hundred " : "";
            if (!numberToWordsMap(tensNum).equals("")) {
                ret += numberToWordsMap(tensNum);
            } else {
                ret += (tens != 0 ? numberToWordsMap(tens*10) + " " : "");
                ret += numberToWordsMap(units);
            }
        }
 
        return ret;
    }
 
    public String numberToWordsMap(int n) {
        return num2wordsMap.getOrDefault(n, "");
    }
}

Older Entries