LeetCode - Sort Colors

Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?

Solution #1: (two-pass counting sort as the follow up says)

public class Solution {
    public void sortColors(int[] A) {
        if(A == null || A.length == 0 || A.length == 1)  return;
        
        int red = 0, white = 0, blue = 0;
        for(int i = 0; i < A.length; i++) {
            if(A[i] == 0)       red++;
            else if(A[i] == 1)  white++;
            else                blue++;
        }
        
        for(int i = 0; i < red; i++) 
            A[i] = 0;
        for(int i = red; i < red + white; i++)
            A[i] = 1;
        for(int i = red + white; i < A.length; i++)
            A[i] = 2;
    }
}

Solution #2: (one-pass solution)

public class Solution {
    public void sortColors(int[] A) {
        if(A == null || A.length == 0 || A.length == 1)  return;
        
        // one-pass solution
        int red = 0, blue = A.length - 1, tmp, i = 0;
        // stop looping when current >= blue
        while(i <= blue) {
            // if color is red, move to the front
            if(A[i] == 0) {
                // when cur > red, switch
                if(i > red) {
                    tmp = A[red];
                    A[red] = A[i];
                    A[i] = tmp;
                    red++;
                }
                // when cur <= red, no need to switch, just move both to next
                else {
                    i++;
                    red++;
                }
            }
            // if color is blue, move to the end
            else if(A[i] == 2) {
                // when cur < blue, switch
                if(i < blue) {
                    tmp = A[blue];
                    A[blue] = A[i];
                    A[i] = tmp;
                    blue--;
                }
                // when cur >= blue, end the loop
                else {
                    return;
                }
            }
            // if color is white, skip
            else {
                i++;
            }
        }
    }
}

Thanks to http://blog.unieagle.net/2012/10/23/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Asort-colors/

Leetcode - Candy

Candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

public class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        if(len == 0 || len == 1)    return len;
        
        // start with every child already has one candy
        int min = len;
        int[] candies = new int[len];
        
        // scan from head + 1 to tail, compare each child with their next neighbos's rating
        int cur = 0;
        for(int i = 1; i < len; i++) {
            if(ratings[i - 1] < ratings[i])
                cur++;
            else
                cur = 0;
            candies[i] = cur;
        }
        
        // scan from tail - 1 to head, do the same process as above loop
        cur = 0;
        for(int i = len - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1])
                cur++;
            else
                cur = 0;
            // no need to store another candies array again, just compare each node and store the max 
            // (why max: candy num of this position should match with both left and right neighbors)
            min += Math.max(candies[i], cur);
        }
        
        // add the candy num of the tail position, since the loop for add a sum didn't cover that position
        min += candies[len - 1];
        
        return min;
    }
}

Many thanks to : http://blog.csdn.net/violet_program/article/details/12233949 

Leetcode - Merge Two Sorted Lists

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null || l2 == null)    return l1 == null ? l2 : l1;
        
        // init
        ListNode head;
        if(l1.val < l2.val) {
            head = new ListNode(l1.val);
            l1 = l1.next;
        }
        else {
            head = new ListNode(l2.val);
            l2 = l2.next;
        }
        ListNode node = head;
        
        // loop
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                node.next = new ListNode(l1.val);
                node = node.next;
                l1 = l1.next;
            }
            else {
                node.next = new ListNode(l2.val);
                node = node.next;
                l2 = l2.next;
            }
        }
        
        while(l1 != null) {
            node.next = new ListNode(l1.val);
            node = node.next;
            l1 = l1.next;
        }
        
        while(l2 != null) {
            node.next = new ListNode(l2.val);
            node = node.next;
            l2 = l2.next;
        }
        
        return head;
    }
}

Leetcode - Remove Duplicates from Sorted List

Remove Duplicates from Sorted List

 

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)   return head;
        
        ListNode node = head;
        
        while(node != null) {
            ListNode tmp = node.next;
            while(tmp != null && node.val == tmp.val) {
                tmp = tmp.next;
            }
            node.next = tmp;
            node = node.next;
        }
        
        return head;
    }
}

Leetcode - Maximum Depth of Binary Tree

Wait to hear back from an onsite interview. May God Bless me!

Maximum Depth of 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.

Solution:
1. Recursive:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)    return 0;
        
        return getDepth(root, 1);
    }
    
    public int getDepth(TreeNode node, int depth) {
        int left = depth, right = depth;
        if(node.left != null) left = getDepth(node.left, depth + 1);
        if(node.right != null) right = getDepth(node.right, depth + 1);
        
        return left > right ? left : right;
    }
}

2. Non-recursive:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)    return 0;
        
        // Non-recursive, use level order triversal
        ArrayList<TreeNode> q = new ArrayList<TreeNode>();
        q.add(root);
        int depth = 0;
        
        while(!q.isEmpty()) {
            ArrayList<TreeNode> next = new ArrayList<TreeNode>();
            for(TreeNode node : q) {
                if(node.left != null)   next.add(node.left);
                if(node.right != null)  next.add(node.right);
            }
            q = new ArrayList<TreeNode>(next);
            depth++;
        }
        
        return depth;
    }
}

! ? Leetcode - Recover Binary Search Tree

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

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

OJ's Binary Tree Serialization: The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.
Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode prev;
    
    public void recoverTree(TreeNode root) {
        if(root == null)    return;
        
        ArrayList<TreeNode> wrongList = new ArrayList<TreeNode>();
        prev = null;
        inOrder(root, wrongList);
        
        int tmp = wrongList.get(0).val;
        wrongList.get(0).val = wrongList.get(wrongList.size() - 1).val;
        wrongList.get(wrongList.size() - 1).val = tmp;

    }
    
    public void inOrder(TreeNode node, ArrayList<TreeNode> wrongList) {
        if(node == null)    return;
        
        inOrder(node.left, wrongList);
        
        // if found
        if(prev != null && prev.val > node.val) {
            if(!(wrongList.contains(prev))) wrongList.add(prev);
            if(!(wrongList.contains(node))) wrongList.add(node);
        }
        prev = node;
        
        inOrder(node.right, wrongList);
    }
}

Reference:
1. http://jane4532.blogspot.com/2013/07/recover-binary-search-treeleetcode.html
2. https://gist.github.com/guolinaileen/5125340

Leetcode - Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree

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

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if(num == null || num.length == 0) return null;
        
        int start = 0, end = num.length - 1;

        TreeNode root = buildTree(num, start, end);
        
        return root;
    }
    
    public TreeNode buildTree(int[] num, int start, int end) {
        if(start > end) return null;
        
        int mid = (start + end) / 2;
        
        // build left sub tree
        TreeNode left = buildTree(num, start, mid - 1);
        // build root of the subtree
        TreeNode node = new TreeNode(num[mid]);
        node.left = left;
        // build right sub tree
        node.right = buildTree(num, mid + 1, end);
        
        return node;
    }
}