Palindrome Number

Problem:
Determine whether an integer is a palindrome. Do this without extra space.

Solution:
First, compare the first and last digit. If they are not the same, it must not be a palindrome. If they are the same, chop off one digit from both ends and continue until you have no digits left, which you conclude that it must be a palindrome.

Now, getting and chopping the last digit is easy. However, getting and chopping the first digit in a generic way requires some thought.

bool isPalindrome(int x) {
    if (x < 0) return false;
    int div = 1;
    while (x / div >= 10) {
        div *= 10;
    }
    while (x != 0) {
        int l = x / div;
        int r = x % 10;
        if (l != r) return false;
        x = (x % div) / 10;
        div /= 100;
    }
    return true;
}

Complexity:

time - O(1)
space - O(1)

Links and credits:
http://discuss.leetcode.com/questions/181/palindrome-number

Regular Expression Matching

Problem:
Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:

 bool isMatch(const char *s, const char *p)
Some examples:

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Solution:

1. If the next character of p is NOT '*', then it must match the current character of s. Continue pattern matching with the next character of both s and p.
2. If the next character of p is '*', then we do a brute force exhaustive matching of 0, 1, or more repeats of current character of p... Until we could not match any more characters.

bool isMatch(const char *s, const char *p) {
    assert(s && p);
    if (*p == '\0') return *s == '\0';

    // next char is not '*': must match current character
    if (*(p+1) != '*') {
        assert(*p != '*');
        return ((*p == *s) || (*p == '.' && *s != '\0')) && isMatch(s+1, p+1);
    }
    // next char is '*'
    while ((*p == *s) || (*p == '.' && *s != '\0')) {
        if (isMatch(s, p+2)) return true;
        s++;
    }
    return isMatch(s, p+2);
}

Complexity:

time - O(2^n)
space - O(n)

Links and credits:
http://discuss.leetcode.com/questions/175/regular-expression-matching

Optimal solution (that grep, awk, and other tools use):
http://swtch.com/~rsc/regexp/regexp1.html

Binary Tree Zigzag Level Order Traversal

Problem:
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

Solution:
This problem can be solved easily using two stacks (one called currentLevel and the other one called nextLevel). You would also need a variable to keep track of the current level's order (whether it is left->right or right->left).

You pop from stack currentLevel and print the node's value. Whenever the current level's order is from left->right, you push the node's left child, then its right child to stack nextLevel. Remember a Stack is a Last In First OUT (LIFO) structure, so the next time when nodes are popped off nextLevel, it will be in the reverse order.

On the other hand, when the current level's order is from right->left, you would push the node's right child first, then its left child. Finally, don't forget to swap those two stacks at the end of each level (ie, when currentLevel is empty).

void printLevelOrderZigZag(BinaryTree *root) {
    stack<BinaryTree*> currentLevel, nextLevel;
    bool leftToRight = true;
    currentLevel.push(root);
    while (!currentLevel.empty()) {
        BinaryTree *currNode = currentLevel.top();
        currentLevel.pop();
        if (currNode) {
            cout << currNode->data << " ";
            if (leftToRight) {
                nextLevel.push(currNode->left);
                nextLevel.push(currNode->right);
            } else {
                nextLevel.push(currNode->right);
                nextLevel.push(currNode->left);
            }
        }
        if (currentLevel.empty()) {
            cout << endl;
            leftToRight = !leftToRight;
            swap(currentLevel, nextLevel);
        }
    }
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://discuss.leetcode.com/questions/52/binary-tree-zigzag-level-order-traversal

Print Left View of a Binary Tree

Problem:
Given a Binary Tree, print left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from left side. Left view of following tree is 12, 10, 25.

          12
       /     \
     10       30
            /    \
          25      40

Solution:
The left view contains all nodes that are first nodes in their levels. A simple solution is to do level order traversal and print the first node in every level.

The problem can also be solved using simple recursive traversal. We can keep track of level of a node by passing a parameter to all recursive calls. The idea is to keep track of maximum level also. Whenever we see a node whose level is more than maximum level so far, we print the node because this is the first node in its level (Note that we traverse the left subtree before right subtree).

Note: the same procedure can be used to get the "right view" of a tree if we first traverse the right sub-tree in the recursive algorithm.

// Recursive function to print left view of a binary tree.
void leftViewUtil(struct node *root, int level, int *max_level)
{
    // Base Case
    if (root==NULL)  return;
 
    // If this is the first node of its level
    if (*max_level < level)
    {
        printf("%d\t", root->data);
        *max_level = level;
    }
 
    // Recur for left and right subtrees
    leftViewUtil(root->left, level+1, max_level);
    leftViewUtil(root->right, level+1, max_level);
}
 
// A wrapper over leftViewUtil()
void leftView(struct node *root)
{
    int max_level = 0;
    leftViewUtil(root, 1, &max_level);
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.geeksforgeeks.org/print-left-view-binary-tree/

Print Postorder traversal from given Inorder and Preorder traversals

Problem:
Given Inorder and Preorder traversals of a binary tree, print Postorder traversal.

Example:

Input:
Inorder traversal in[] = {4, 2, 5, 1, 3, 6}
Preorder traversal pre[] = {1, 2, 4, 5, 3, 6}

Output:
Postorder traversal is {4, 5, 2, 6, 3, 1}

Trversals in the above example represents following tree

         1
      /     \   
     2       3
   /   \      \
  4     5      6

Solution:
A naive method is to first construct the tree, then use simple recursive method to print postorder traversal of the constructed tree. We can print postorder traversal without constructing the tree.

1. The pre[0] is the root of the tree --> 1
2. The in[] represents the tree as:
   
   { { left-sub-tree } ;  root ;   { right-sub-tree } }
   
   So the index of the root at in[] is the length of the left sub-tree --> 3
3. The (in[].length - rootIndex - 1) is the length of the right sub-tree --> 2
4. The pre[] represents the tree as:
   
   { root ;   { left-sub-tree } ;  { right-sub-tree } }
   
   Since we know the lengths of the sub-trees from steps #2 and #3, we can proceed recursively as follows:
   
   leftIn[] = in[ 0 .. (rootIndex-1) ] = { 4, 2, 5 }
   leftPre[] = pre[ 1 .. (rootIndex-2) ] = { 2, 4, 5 }
   
   rightIn[] = in[ (rootIndex+1) .. (length-1) ] = { 3, 6 }
   rightPre[] = pre[ (rootIndex+1) .. (length-1) ] = { 3, 6 }
   
   Recursion ends when the lengths of the in[] and pre[] become equal to 1.

int search(int arr[], int x, int n)
{
    for (int i = 0; i < n; i++)
      if (arr[i] == x)
         return i;
    return -1;
}
 
// Prints postorder traversal from given inorder and preorder traversals
void printPostOrder(int in[], int pre[], int n)
{
   // The first element in pre[] is always root, search it
   // in in[] to find left and right subtrees
   int root = search(in, pre[0], n);
 
   // If left subtree is not empty, print left subtree
   if (root != 0)
      printPostOrder(in, pre+1, root);
 
   // If right subtree is not empty, print right subtree
   if (root != n-1)
      printPostOrder(in+root+1, pre+root+1, n-root-1);
 
   // Print root
   cout << pre[0] << " ";
}

Complexity:

time - O(n^2)
space - O(n)

Links and credits:
http://www.geeksforgeeks.org/print-postorder-from-given-inorder-and-preorder-traversals/