Find the Kth smallest element in an unsorted array.

Find the Kth smallest element in an unsorted array.

Thoughts:
We can solve it by Divide and Conquer.
First, select an element as pivot and split the array into two sub-arrays, smaller (A) and greater (B) than pivot.
Then,
If the length of A is greater than k, we delegate the task to this array.
If the length of A is smaller than k, we delegate the task to array B, and to find the (k-|A|)th smallest number in B.
Otherwise, return the pivot value.

Code:

public static int kthSmall(int[]a, int k){
    if(k == a.length)   
        return a[a.length-1];
    
    else
        return kthSmall(a, k, 0, a.length-1);
}


public static int kthSmall(int[] a, int k, int start, int end){
    int j = start;
    int i = j-1;
    
    int pivot = a[end];
    
    for(;j<end;j++){
        if(a[j] < pivot){
            i++;
            swap(a, i, j);
        }
    }
    
    i++;
    swap(a, i, end);
  
    int small = i-start+1;
    if(small == k){
        return a[i];
    }else if(small > k){
        return kthSmall(a, k, start, i-1);
    }else{   //small is less than k
        return kthSmall(a, k-small, i+1, end);
    }
}

public static void swap(int[] a, int i, int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

Time Complexity:
O(kN), which is effective when k is small.

Sorted insert for circular linked list

Thoughts:

There are three cases:
1. The Linked List is empty.
2. The input number is smaller than the data of head.
3. Find the node that node.next.data is larger than the number. Insert it behind the node.

For the second case, we first might want to insert the number before head. But if so, we have to find the last node of the linked list to make the linked list circular. So we may swap data of the new node with head node, then insert the new node behind head.

code:

Node* sortedInsert(Node* head, int num){
    Node* n = new Node(num);
    
    if(head == NULL){   
        head = n;
        head->next = head;
    }else if(num <= head->data){ // num is smaller than the first element
        n->data = head->data;    //swap n->data with head->data
        head->data = num;
        
        n->next = head->next;     //insert n behind head
        head->next = n;
    }else{
        Node* current = head->next;
        
        while(current->next!=head && current->next->data < num){
            current = current->next;
        }
        
        n->next = current->next;
        current->next = n;
    }
    
    return head;
}

Construct Tree from given Inorder and Preorder traversals

Construct Tree from given Inorder and Preorder traversals

Thoughts:
Let us consider the below traversals:

Inorder sequence: D B E A F C
Preorder sequence: A B D E C F

In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.

                 A
               /   \
             /       \
           D B E     F C

We recursively follow above steps and get the following tree.

         A
       /   \
     /       \
    B         C
   / \        /
 /     \    /
D       E  F

Algorithm:
1) Pick an element from Preorder.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder, inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.

Code:

static int preIndex = 0;

public static TreeNode BuildTree(int[] in, int[] pre){
    return BuildTree(in, pre, 0, in.length-1);
}

public static TreeNode BuildTree(int[] in, int[] pre, int start, int end){	//start and end are only for inorder
    if(start > end)
        return null;

    int num = pre[preIndex];
    TreeNode n = new TreeNode(num);
    preIndex++;	//we construc the tree by pre order, so we add node to tree by the order of pre[]

    int index = findIndex(in, num, start, end);

    n.left = BuildTree(in, pre, start, index-1);
    n.right = BuildTree(in, pre, index+1, end);

    return n;
}

public static int findIndex(int[] in, int num, int start, int end){    //find index in in[]
    for(int i=start; i<=end; i++){
        if(in[i] == num)
            return i;
    }
    return -1;
}

Time Complexity: O(n^2). Worst case occurs when tree is left skewed.

References:
http://www.geeksforgeeks.org/archives/6633

Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

Method 1:
If each node contains a parent pointer which links to its parent, we can use the way to check intersection node of two linked list. Like (1)using hash table; (2)get height of two nodes in the tree, move the higher node pointer to same height with the other one, then move up together to find the intersection.

Method 2:

Thoughts:
Each node doesn’t contain a parent pointer which links to its parent.
We may use the way similar with checking LCA in BST.
1. If the two nodes are both on the left of the node, branch left to look for the LCA.
2. If the two nodes are both on the right of the node, branch right to look for the LCA.
3. If the two nodes are no longer on the same side, the node would be the LCA.
4. If one of the two nodes is the ancestor of the other, it would be the LCA.

And we can write a cover() method to check if a node is on the subtree of anther node.

Code:

public static TreeNode BT_LCA(TreeNode root, int a, int b){
			if(!coverNode(root, a) || !coverNode(root, b))
					return null;
			
			return commonAncestor(root, a, b);
}
   
public static TreeNode commonAncestor(TreeNode root, int a, int b){
    if(root==null)
        return null;
    
    if(root.value == a || root.value == b)
        return root;
        
    boolean a_left = coverNode(root.left, a);
    boolean b_left = coverNode(root.left, b);
    
    if(a_left != b_left)
        return root;
    
    TreeNode next = a_left==true? root.left: root.right;
    
    return commonAncestor(next, a, b);
}

public static boolean coverNode(TreeNode root, int num){
    if(root == null)
        return false;
    if(root.value == num)
        return true;
        
    return coverNode(root.left, num) || coverNode(root.right, num);
}

Time Complexity: O(N) when the tree is balanced.

Lowest Common Ancestor in a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the BST.

Example:

         6
      /     \
     2       8
   /   \   /   \
  1    4  7     9

The LCA of nodes 2 and 8 is 6.
The LCA of nodes 2 and 4 is 2. (According the definition in Wikipedia)

Thoughts:
There’s only four cases you need to consider:
1. Both nodes are to the left of the tree, so the LCA must be in its left subtree.
2. Both nodes are to the right of the tree, so the LCA must be in its right subtree.
3. One node is on the left while the other is on the right, the current node must be the LCA.
4. When the current node equals to either of the two nodes, this node must be the LCA.

Code:

public static TreeNode BST_LCA(TreeNode root, int a, int b){
    if(root==null)
        return null;
    
    if(root.value>a && root.value>b){  //LCA is in left subtree
        return BST_LCA(root.left, a, b);
    }else if(root.value<a && root.value<b){  //LCA is in right subtree
        return BST_LCA(root.right, a, b);
    }else{    //root.data==a || root.data==b || root.data in between a and b
        return root;
    }
}

References:
http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-search-tree.html
http://www.geeksforgeeks.org/archives/1029

Printing a Binary Tree in Zig Zag Level-Order

Given a binary tree, print out the tree in zig zag level order. Output a newline after the end of each level.

     3
   /  \
  9   20
     /  \
    15    7

The zig zag level order output:
3
20 9
15 7

Thoughts:
Queue is not helpful here. You might want to consider using Stack instead.

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 (When currentLevel is empty).

Code:

public static void ZigZagTraversal(TreeNode root){
    Stack current = new Stack();
    Stack next = new Stack();
    boolean leftToRight = true;

    current.push(root);

    while(!current.isEmpty()){
        TreeNode n = current.pop();

        System.out.print(n.value + " ");

        if(leftToRight){
            if(n.left!=null)
                next.push(n.left);
            if(n.right!=null)
                next.push(n.right);
        }else{
            if(n.right!=null)
                next.push(n.right);
            if(n.left!=null)
                next.push(n.left);
        }

        if(current.isEmpty()){
            //swap the stacks
            Stack temp = current;
            current = next;
            next = temp;

            System.out.println();
            leftToRight = !leftToRight;
        }
    }
}

References: http://www.leetcode.com/2010/09/printing-binary-tree-in-zig-zag-level_18.html

Finding the minimum in a sorted, rotated array

Given an array that is sorted increasing and then rotated right by an unspecified numnber of times, find its minimal element efficiently.

Thoughts:

1. If the array just has one element, then return the element.
2. If the array has two elements, then return the smaller one.
3. If the left most element is smaller than the right most element, then we can know the array is sorted like never be rotated. Just return the left one.
4. By the method of Binary Search, we get the middle element of array, a[mid]. If a[mid] > a[left], then the left half of array is sorted. we then search the right half, including a[mid]. Otherwise we search the left half, including a[mid].

Code: (Without Duplicate Elements)

public static int findMin(int[] a, int left, int right){
    
    //one element
    if(left == right){
        return a[left];
    }
    
    //two elements
    if(left == right-1){
        return a[left]<a[right]? a[left]: a[right];
    }
    
    //the array is ordered
    if(a[left] < a[right]){
        return a[left];
    }
    
    int mid = (left+right)/2;
    
    if(a[mid] >= a[left]){
        return findMin(a, mid, right);
    }else{
        return findMin(a, left, mid);
    }
    
}

Time Complexity: O(lgN)

Code: (With Duplicate Elements)

//with duplicate
public static int findMin2(int[] a, int left, int right){
    
    //one element
    if(left == right){
        return a[left];
    }
    
    //two elements
    if(left == right-1){
        return a[left]<a[right]? a[left]: a[right];
    }
    
    //the array is ordered
    if(a[left] < a[right]){
        return a[left];
    }
    
    int mid = (left+right)/2;
    
    if(a[mid] > a[left]){
        return findMin(a, mid, right);
    }else if(a[mid] < a[left]){
        return findMin(a, left, mid);
    }else{ //when a[mid] == a[left], we have to search both side
        return Math.min(findMin(a, mid, right), findMin(a, left, mid));
    }
    
}

Time Complexity: O(N) is the worst case

References:
http://codereview.stackexchange.com/questions/1514/finding-the-minimum-in-a-sorted-rotated-array

Find the First Missing Positive Integer

Given an unsorted integer array, find the first missing positive integer.

For example,
{1, 2, 0} return 3,
{3, 4, -1, 1} return 2.

Your algorithm should run in time and uses constant space.

Thoughts:
For sorted array, like [1,2,3], we know 4 is missing, or [1, 8, 3, 4] then we know 2 is missing.
So, if all numbers are in their correct positions, a[i] = i+1, the problem can be easily solved in constant time.
Our goal is to rearrange those numbers to their correct positions.
For example:
[3, 4, -1, 1]
a[0], 3: should be in a[2]. swap a[0] with a[2], then
[-1, 4, 3, 1]
now a[0] is -1, it’s not positive number, so we just leave it here.
a[1], 4, should be in a[3]. swap a[1] with a[3], then
[-1, 1, 3, 4]
now a[1] = 1, which should be in a[0]. swap a[0] with a[1], then
[1, -1, 3, 4]
Then we can know 2 is missing.

Codes:

public static int firstMissingPositive(int[] a){
    for(int i=0; i<a.length; i++){
        while(a[i]!=i+1){
            //a[i] == a[a[i]-1] when the two swaped nums are same
            if(a[i]<=0 || a[i]>=a.length || a[i] == a[a[i]-1])
                break;
            //swap
            int temp = a[i];
            a[i] = a[temp-1];
            a[temp-1] = temp;
        }
    }

    for(int i=0; i<a.length; i++){
        if(a[i]!=i+1)
            return i+1;
    }

    return a.length+1;
}

Time Complexity: O(N)

References: http://tianrunhe.wordpress.com/2012/07/15/finding-the-1st-missing-positive-int-in-an-array-first-missing-positive/

Sort an array of 0s, 1s and 2s

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Thoughts:
We can solve this problem in O(N).
Three flags should be used for pointing the last of 0, the last of 1, and the first of 2.

Init: low = -1; mid = 0; high = A.length;
We can use mid as cursor,
while mid < high do
Invariant: a[0..low]=0 and a[low..mid-1]=1 and a[high..N]=2; a[mid..high-1] are unknown.
case a[Mid] in
0: swap a[low+1] and a[mid]; mid++
1: mid++
2: swap a[mid] and a[high-1]; mid stay, because we don’t know which number swaps to here

Codes:

public static void sort012(int[] a){
    int low = -1;
    int mid = 0;
    int high = a.length;

    while(mid < high){
        if(a[mid] == 0){
            low++;
            swap(a, low, mid);
            mid++;
        }else if(a[mid] == 1){
            mid++;
        }else if(a[mid] == 2){
            high--;
            swap(a, mid, high);
        }else{
            System.err.println("Error!");
            return;
        }
    }
}

public static void swap(int[] a, int i, int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

Time Complexity: O(N)

References: http://www.geeksforgeeks.org/archives/8133

Merge Sort for Linked Lists

Merge sort is often preferred for sorting a linked list. The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.

Thoughts:
MergeSort(head)
1) If head is NULL or there is only one element in the Linked List
then return head.
2) Else divide the linked list into two halves.
(May use two pointer fast and slow, head points to the head of left half,
slow points to the head of right half)
3) Sort the two halves a and b.
left = MergeSort(a);
right = MergeSort(b);
4) Merge the sorted a and b and the head of merged linked list.
return SortedMerge(left, right);

Codes:

public static LinkedListNode mergesort(LinkedListNode node){
    //if null or there is just one element
    if(node==null || node.next==null){
        return node;
    }
    
    LinkedListNode fast = node;
    LinkedListNode slow = node;
    
    while(fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;
    }
    
    LinkedListNode n = node;
    while(n.next!=slow){
        n = n.next;
    }
    n.next = null;  //split the left and right
    
    //node is the head of left half, slow is the head of right half
    LinkedListNode left = mergesort(node);
    LinkedListNode right = mergesort(slow);
    
    //merge the sorted linked lists
    return sortedMerge(left, right);
}

public static LinkedListNode sortedMerge(LinkedListNode l1, LinkedListNode l2){
    if(l1==null)
        return l2;
    if(l2==null)
        return l1;
    
    LinkedListNode n = null;    
    if(l1.data < l2.data){
        n = l1;
        n.next = sortedMerge(l1.next, l2);
    }else{
        n = l2;
        n.next = sortedMerge(l1, l2.next);
    }
    
    return n;
}

Time Complexity: O(nLogn)

References:
http://www.geeksforgeeks.org/archives/7740