Length of Last Word

Length of Last WordMar 27 '12

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, 
Given s = "Hello World",
return 5.

Valid Palindrome

Valid PalindromeJan 13

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Remove Duplicates from Sorted Array

Remove Duplicates from Sorted ArrayFeb 16 '12

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Swap Nodes in Pairs

Swap Nodes in PairsFeb 15 '12

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Balanced Binary Tree

Balanced Binary TreeOct 9 '12

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of everynode never differ by more than 1.

Two Sum

Two SumMar 14 '11

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Remove Element

Remove ElementFeb 16 '12

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Jump Game

Jump GameMar 25 '12

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Remove Nth Node From End of List

Remove Nth Node From End of ListJan 28 '12

Given a linked list, remove the n^th node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

Valid Parentheses

Valid ParenthesesJan 30 '12

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search TreeOct 2 '12

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Path Sum II

Path Sum IIOct 14 '12

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Binary Tree Inorder Traversal

Binary Tree Inorder TraversalAug 27 '12

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {     
        vector<int> inOrderVector;
        stack<TreeNode*> inOrderStack;
        TreeNode *runner=root;
        
        if (!root)
            return inOrderVector;  
        while (!inOrderStack.empty() || runner) {
            if (runner) {
                inOrderStack.push(runner);
                runner=runner->left;
            }
            else {
                runner=inOrderStack.top();
                inOrderStack.pop();
                inOrderVector.push_back(runner->val);
                runner=runner->right;
            }
        }  
        return inOrderVector;
    }
};

Path Sum

Path SumOct 14 '12

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1 

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22. 

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    bool hasPathSumInt(TreeNode *root, int sum, int currSum) {    
        if (!root)
            return false;    
        if (!root->left && !root->right)
            return currSum + root->val== sum;
        return hasPathSumInt(root->left, sum,  root->val + currSum) ||
               hasPathSumInt(root->right, sum, root->val + currSum);
    }
public:
    bool hasPathSum(TreeNode *root, int sum) {
        return hasPathSumInt(root, sum, 0);
    }
};

Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node IIOct 28 '12

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

/**
 * Definition for binary tree
 * struct TreeLinkNode {
 *     int val;
 *     TreeLinkNode *left;
 *     TreeLinkNode *right;
 *     TreeLinkNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {  
        if(!root)
            return;

        queue<TreeLinkNode *> levelQ;
        int queueCount=1, levelCount=0;
        TreeLinkNode *prev=NULL;
        
        levelQ.push(root);
        while (!levelQ.empty())
        {
            while(queueCount)
            {
                TreeLinkNode *temp = levelQ.front();
                levelQ.pop();
                queueCount--;
                if (prev)
                    prev->next = temp;
                prev = temp;
                if (temp->left) {
                    levelQ.push(temp->left);
                    levelCount++;
                }
                if (temp->right) {
                    levelQ.push(temp->right);
                    levelCount++;
                }
            }
            queueCount = levelCount++;
            prev = NULL;
            levelCount=0;
        }
    }
};

Populating Next Right Pointers in Each Node

Populating Next Right Pointers in Each NodeOct 28 '12

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set toNULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

» Solve this problem

/**
 * Definition for binary tree
 * struct TreeLinkNode {
 *     int val;
 *     TreeLinkNode *left;
 *     TreeLinkNode *right;
 *     TreeLinkNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) { 
        if (!root)
            return;    
        if (root->left)
            root->left->next = root->right;
        if (root->right && root->next)
            root->right->next = root->next->left;
        if (root->left)
            connect(root->left);
        if (root->right)
            connect(root->right);
    }
};

Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked ListOct 14 '12

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    void flattenInt(TreeNode *root)
    {       
        if (root->left) {
            flattenInt(root->left); 
        
            TreeNode *temp=root->right;
            TreeNode *trav=root->left;

            /* Attach the right child of this node to
             * the rightmost node of the left child 
             */
            while (trav->right)
                trav = trav->right;        

            root->right=root->left;
            trav->right=temp;
            root->left=NULL;
        }  
        if (root->right)
            flattenInt(root->right);
    }
public:
    void flatten(TreeNode *root) {
        if (!root)
            return;
        if (!root->left && !root->right)
            return;
        flattenInt(root);
        
    }
};

/* Alternative Solution */

class Solution {
    void flattenInt(TreeNode *root, TreeNode **tail) {
        if (root) {
            TreeNode *right = root->right;
            TreeNode *left  = root->left;
            if (*tail) {
                (*tail)->right = root;
                (*tail)->left  = nullptr;
            }
            *tail = root;
            flattenInt(left, tail);
            flattenInt(right, tail);
        }
    }
public:
    void flatten(TreeNode *root) {
        TreeNode *tail=nullptr;
        flattenInt(root, &tail);
    }
};

Sum Root to Leaf Numbers

Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    void sumNumbersInt(TreeNode *root, string path, int &pathSum)
    {
        if (!root)
            return;      
        if (!root->left && !root->right)
        {
           path+=to_string(root->val);
           pathSum+=atoi(path.c_str());
        }
        string currentPath = path + to_string(root->val);
        sumNumbersInt(root->left, currentPath, pathSum);
        sumNumbersInt(root->right, currentPath, pathSum);
    }
public:
    int sumNumbers(TreeNode *root) 
    {
        int pathSum=0;
        string path;
        if (!root)
            return 0;
        if (!root->left && !root->right)
            return root->val;
        sumNumbersInt(root, path, pathSum);
        return pathSum;
    }
};

Reverse Between m and n

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:

Symmetric Tree

Symmetric TreeSep 24 '12

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

Level Order Traversal

Binary Tree Level Order TraversalSep 29 '12

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Recursive Version

Minimum Depth of a Binary Tree

Minimum Depth of Binary TreeOct 10 '12

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Maximum Depth of a Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Same Trees

Same TreeSep 3 '12

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value

Validate BST

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.