Wednesday, March 30, 2016

Convert String to ZigZag Bottom Up

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/zigzag-conversion-problem/.


Problem

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

Example


P   A   H   N
A P L S I I G
Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".


Solution

Method 1 - Use list to save the substrings


A straightforward solution is to actually build up the zigzag character matrix and read the matrix into a string.
Here is the basic algo:
  • Maintain down boolean which tells whether you are going up or down in zig zag order.
  • As soon as rows = 0 means you need to go down now and as soon as rows = nRows - 1 you need to go up now
  • Just keep on doing this until whole string is exhausted
  • Using StringBuilder list/array to store elements in zig zag order and in the end just append all characters from each StringBuilder to return output.
Here is the code in java:
import java.util.ArrayList;

public class Solution {
    public String convert(String s, int nRows) {
        if(s == null || s.length() <= 1 || nRows <= 1){
            return s;
        }
        
        ArrayList<StringBuilder> list = new ArrayList<StringBuilder>();
        for(int i = 0; i < nRows; i++){
            list.add(new StringBuilder());
        }
        
        int i = 0;
        boolean down = false;
        int row = 0;
        
        while(i < s.length()){
            list.get(row).append(s.charAt(i));
            if(row == 0){
                down = true;
            }else if(row == nRows - 1){
                down = false;
            }
            
            if(down){
                row++;
            }else{
                row--;
            }
            
            i++;
        }
        
        i = 0;
        StringBuilder output = new StringBuilder();
        while( i < list.size()){
            output.append(list.get(i).toString());
            i++;
        }
        return output.toString();
    }
}


Though time complexity is good O(n), but the space is complexity is O(nRows*Max_column_in_a_row) = O(n)

Method 2 - Append the character on the fly

Another way is to calculate the corresponding index on the fly and append the character into a string.
Take convert("PAYPALISHIRING", 4) as an example. The matrix will look as follows :
P   I   N
A L S I G
Y A H R
P   I

which can be expended as below (You will see why we rewrite like this soon.).
P   I   N
A   S   G
Y   H
P   I
A   R
L   I

Some useful properties:
  • For any full columns, the odd ones have nRows characters, even ones have (nRows - 2) characters.
  • For the first and last rows, we read one single character from each expended column;
  • For the rest of rows, we read two characters, one from top part and one from bottom part, from each expended column.
  • One edge case is that nRows = 1, where (nRows*2 - 2) becomes 0. In this case, we should simply return the original string.
public String convert(String s, int nRows) {  
  if (nRows == 1) return s;  
  
  StringBuilder ss = new StringBuilder();  
  int n = nRows + nRows - 2;  
  // rest rows  
  for (int i = 0; i < nRows; ++i) {  
    int cur = i;  
    while (cur < s.length()) {  
      ss.append(s.charAt(cur));  
      cur += n;  
      if (i > 0 && i < nRows - 1 && (cur - i - i) < s.length()) {  
        ss.append(s.charAt(cur - i - i));  
      }  
    }  
  }  
  return ss.toString();  
}  


Thanks.
Reference
http://www.params.me/2014/04/leetcode-zigzag-conversion-in-java.html
http://n00tc0d3r.blogspot.in/2013/06/zigzag-conversion.html
https://leetcode.com/problems/zigzag-conversion/

Friday, March 11, 2016

Growth Rate - The Importance of Asymptotics

It really is true that if algorithm A is o(algorithm B) then for large problems A will take much less time than B.

Definition: If (the number of operations in) algorithm A is o(algorithm B), we call A asymptotically faster than B.

Example:: The following sequence of functions are ordered by growth rate, i.e., each function is little-oh of the subsequent function.
log(log(n)), log(n), (log(n))2, n1/3, n1/2, n, nlog(n), n2/(log(n)), n2, n3, 2n, 4n, n!

One way to compare 2 functions, is using L'Hospital rule. Here is good explanation:
Growth Rates of Functions and L'Hospital's Rule

Here is the snapshot of how the growth looks in increasing order
1 loglogn logn n nlogn n2 2n n! nn

Reference
https://cs.nyu.edu/courses/fall02/V22.0310-002/class-notes.html

http://www.cs.odu.edu/~cs381/cs381content/function/growth.html


Asymptotic Notation

Its been a while, since I have blogged. To start with I am posting a basics of asymptotic analysis of algorithm, which we study at the start of the course.
Now we are going to be less precise and worry only about approximate answers for large inputs.

The Big-Oh Notation

Definition: Let f(n) and g(n) be real-valued functions of a single non-negative integer argument. We write f(n) is O(g(n)) if there is a positive real number c and a positive integer n0 such that f(n)≤cg(n) for all n≥n0.
What does this mean?
For large inputs (n≤n0), f is not much bigger than g (f(n)≤cg(n)).
Examples to do on the board
  1. 3n-6 is O(n). So, what f(n) = 3n-6 <= c*n. For example, c=4. Some less common ways of saying the same thing follow.
  2. 3x-6 is O(x).
  3. If f(y)=3y-6 and id(y)=y, then f(y) is O(id(y)).
  4. 3n-6 is O(2n)
  5. 9n4+12n2+1234 is O(n4).
  6. innerProduct is O(n)
  7. innerProductBetter is O(n)
  8. innerProductFixed is O(n)
  9. countPositives is O(n)
  10. n+log(n) is O(n).
  11. log(n)+5log(log(n)) is O(log(n)).
  12. 1234554321 is O(1).
  13. 3/n is O(1). True but not the best.
  14. 3/n is O(1/n). Much better.
  15. innerProduct is O(100n+log(n)+34.5). True, but awful.
A few theorems give us rules that make calculating big-Oh easier.

Theorem (arithmetic): Let d(n), e(n), f(n), and g(n) be nonnegative real-valued functions of a nonnegative integer argument and assume d(n) is O(f(n)) and e(n) is O(g(n)). Then
  1. ad(n) is O(f(n)) for any nonnegative a
  2. d(n)+e(n) is O(f(n)+g(n))
  3. d(n)e(n) is O(f(n)g(n))
Theorem (transitivity): Let d(n), f(n), and g(n) be nonnegative real-valued functions of a nonnegative integer argument and assume d(n) is O(f(n)) and f(n) is O(g(n)). Then d(n) is O(g(n)).
Theorem (special functions): (Only n varies)
  1. If f(n) is a polynomial of degree d, then f(n) is O(nd).
  2. nx is O(an) for any x>0 and a>1.
  3. log(nx) is O(log(n)) for any x>0
  4. (log(n))x is O(ny) for any x>0 and y>0.

Definitions: (Common names)
  1. If a function is O(log(n)) we call it logarithmic.
  2. If a function is O(n) we call it linear.
  3. If a function is O(n2) we call it quadratic.
  4. If a function is O(nk) with k≥1, we call it polynomial.
  5. If a function is O(an) with a>1, we call it exponential.
Remark: The last definitions would be better with a relative of big-Oh, namely big-Theta, since, for example 3log(n) is O(n2), but we do not call 3log(n) quadratic.

1.2.2 Relatives of the Big-Oh

Big-Omega and Big-Theta

Recall that f(n) is O(g(n)) if for large n, f is not much bigger than g. That is g is some sort of upper bound on f. How about a definition for the case when g is (in the same sense) a lower bound for f?
Definition: Let f(n) and g(n) be real valued functions of an integer value. Then f(n) is Ω(g(n)) if g(n) is O(f(n)).
Remarks:
  1. We pronounce f(n) is Ω(g(n)) as "f(n) is big-Omega of g(n)".
  2. What the last definition says is that we say f(n) is not much smaller than g(n) if g(n) is not much bigger than f(n), which sounds reasonable to me.
  3. What if f(n) and g(n) are about equal, i.e., neither is much bigger than the other?
Definition: We write f(n) is Θ(g(n)) if both f(n) is O(g(n)) and f(n) is Ω(g(n)).
Remarks We pronounce f(n) is Θ(g(n)) as "f(n) is big-Theta of g(n)"
Examples to do on the board.
  1. 2x2+3x is θ(x2).
  2. 2x3+3x is not θ(x2).
  3. 2x3+3x is Ω(x2).
  4. innerProductRecutsive is Θ(n).
  5. binarySearch is Θ(log(n)). Unofficial for now.
  6. If f(n) is Θ(g(n)), the f(n) is &Omega(g(n)).
  7. If f(n) is Θ(g(n)), then f(n) is O(g(n)).

Little-Oh and Little-Omega

Recall that big-Oh captures the idea that for large n, f(n) is not much bigger than g(n). Now we want to capture the idea that, for large n, f(n) is tiny compared to g(n).
If you remember limits from calculus, what we want is that f(n)/g(n)→0 as n→∞. However, the definition we give does not use limits (it essentially has the definition of a limit built in).

Definition: Let f(n) and g(n) be real valued functions of an integer variable. We say f(n) is o(g(n)) if for any c>0, there is an n0 such that f(n)≤g(n) for all n>n0. This is pronounced as "f(n) is little-oh of g(n)".

Definition: Let f(n) and g(n) be real valued functions of an integer variable. We say f(n) is ω(g(n) if g(n) is o(f(n)). This is pronounced as "f(n) is little-omega of g(n)".
Examples: log(n) is o(n) and x2 is ω(nlog(n)).


Properties of Notations


Notations
Reflexive
Transitive
Symmetric
Transpose Symmetric
O
Yes
Yes
No
No
Ω
Yes
Yes
No
Yes
 
Yes i.e. f(n) = O(g(n)), iff    g(n) = Ω(f(n))
Θ
Yes
i.e.f(n) =
Θ (f(n))

Yes
f(n)=Θ(g(n)) and g(n)=Θ(h(n))
 implies f(n) =
Θ(h(n))
Yes
No
o
No
Yes
No
No
ω
No
Yes
No
No



Source
https://cs.nyu.edu/courses/fall02/V22.0310-002/class-notes.html

Friday, September 4, 2015

Given a BST with 2 nodes swapped, fix it

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/recover-binary-search-tree-problem/.

Problem

Given a BST with 2 nodes swapped fix it.

Example
Consider the BST:
Following is the correct BST 
         10
        /  \
       5    20
      / \
     2   8


Now we swap  8 and 20, and BST is changed.

Input Tree:
         10
        /  \
       5    8
      / \
     2   20

In the above tree, nodes 20 and 8 must be swapped to fix the tree.  

In the previous post, we saw how many pairs in the input tree violate the BST property. Here we will fix it.

1. The swapped nodes are not adjacent in the inorder traversal of the BST.
 For example, Nodes 5 and 25 are swapped in {3 5 7 8 10 15 20 25}. 
 The inorder traversal of the given tree is 3 25 7 8 10 15 20 5 
If we observe carefully, during inorder traversal, we find node 7 is smaller than the previous visited node 25. Here save the context of node 25 (previous node). Again, we find that node 5 is smaller than the previous node 20. This time, we save the context of node 5 ( current node ). Finally swap the two node’s values.
2. The swapped nodes are adjacent in the inorder traversal of BST.
  For example, Nodes 7 and 8 are swapped in {3 5 7 8 10 15 20 25}. 
  The inorder traversal of the given tree is 3 5 8 7 10 15 20 25 
Unlike case #1, here only one point exists where a node value is smaller than previous node value. e.g. node 7 is smaller than node 8.

How to Solve? We will maintain three pointers, first, middle and last. When we find the first point where current node value is smaller than previous node value, we update the first with the previous node & middle with the current node. When we find the second point where current node value is smaller than previous node value, we update the last with the current node. In case #2, we will never find the second point. So, last pointer will not be updated. After processing, if the last node value is null, then two swapped nodes of BST are adjacent.

code:
 private void swap(Node a, Node b) {  
   if (n1 == null || n2 == null)  return;
   int tmp = a.val;  
   a.val = b.val;  
   b.val = tmp;  
 }  
   
 public void recoverTree(Node root) {  
   Node cur = root, pre = null, first = null, second = null;  
   // in order travesal should return a sorted list  
   Stack stack = new Stack();  
   while (cur != null) { // find the left most child  
     stack.push(cur);  
     cur = cur.left;  
   }  
   while (!stack.isEmpty()) {  
     cur = stack.pop();  

     // is it wrong?  
     if (pre != null && cur.val < pre.val) {  
       if (first == null) {  
         // the first wrong item should be the bigger one  
         first = pre;  
         second = cur; // there is a chance that the two were swapped  
       } else {  
         // the second wrong item should be the smaller one  
         second = cur;  
         break;  
       }  
     }  

     // go to right child and repeat  
     pre = cur;  
     cur = cur.right;  
     while (cur != null) {  
       stack.push(cur);  
       cur = cur.left;  
     }  
   }  
   
   swap(first, second);  
 }  


References

Given a binary search tree with 2 nodes swapped find number of pairs not following BST properties

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/given-a-binary-search-tree-with-2-nodes-swapped-find-number-of-pairs-not-following-bst-properties/.

Problem

Given a binary search tree with 2 nodes swapped, give the number of nodes not following bst property. Follow up - Fix the BST, in the next post.

Example
Consider the BST:
Following is the correct BST 
         10
        /  \
       5    20
      / \
     2   8


Now we swap  8 and 20, and BST is changed.

Input Tree:
         10
        /  \
       5    8
      / \
     2   20

In the above tree, nodes 20 and 8 must be swapped to fix the tree.  

Now number of pairs not following BST property are 3. The reason is :
  • 10-20
  • 10-8
  • 20-8

 Solution

Method 1 - Using in-order traversal
We can have following solution:
  1. Find the inorder traversal of the input tree. Example - 2, 5, 20, 10, 8
  2. Find the number of inversions in the inorder traversal. That is the answer. Here the inversions are 20-10, 20-8, and 10-8. 
Time complexity - O(n logn) as O(n) time for inorder traversal and O(nlogn) for number of inversions in the sorted array.

For a Given node of a binary tree, print the K distance nodes.

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/all-nodes-distance-k-in-binary-tree-problem/.
Problem
You are given a function printKDistanceNodes which takes in a root node of a binary tree, a start node and an integer K. Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted order. Distance can be upwards or downwards.

Example
start node = 18, k = 2 , then output = 2, 19, 25
start node = 18, k = 3,  then output = -4, 3

Solution

We have already seen a similar problem, where we have to find k distance from the root and k distance from the leaf. Find the distance from root is easy. In the second case of printing from bottom to top (k distance from leaves), we know the direction, i.e. we have to go up. But here we have to find the k elements even going upwards.

Note :- Parent pointer is not given.

Method 1 - Using the recursion

(Printing nodes at a disance of K  downwards  is easy). Its a simple recursive function.So moving to nodes which are in upwards direction.

There are two types of nodes to be considered.
1) Nodes in the subtree rooted with target node. For example if the target node is 18 and k is 2, then such nodes are 19 and 25.
2) Other nodes, may be an ancestor of target, or a node in some other subtree. For target node 18 and k is 2, the node 2 comes in this category.

Finding the first type of nodes is easy to implement. Just traverse subtrees rooted with the target node and decrement k in recursive call. When the k becomes 0, print the node currently being traversed (See this for more details). Here we call the function as printkdistanceNodeDown().

How to find nodes of second type? For the output nodes not lying in the subtree with the target node as the root, we must go through all ancestors. For every ancestor, we find its distance from target node, let the distance be d, now we go to other subtree (if target was found in left subtree, then we go to right subtree and vice versa) of the ancestor and find all nodes at k-d distance from the ancestor.
// Recursive function to print all the nodes at distance k in the
// tree (or subtree) rooted with given root. See  
void printkdistanceNodeDown(Node root, int k)
{
    // Base Case
    if (root == null || k < 0)  return;
 
    // If we reach a k distant node, print it
    if (k==0)
    {
        System.out.println(root.data);
        return;
    }
 
    // Recur for left and right subtrees
    printkdistanceNodeDown(root.left, k-1);
    printkdistanceNodeDown(root.right, k-1);
}
 
// Prints all nodes at distance k from a given target node.
// The k distant nodes may be upward or downward.  This function
// Returns distance of root from target node, it returns -1 if target
// node is not present in tree rooted with root.
int printkdistanceNode(Node root, Node target , int k)
{
    // Base Case 1: If tree is empty, return -1
    if (root == null) return -1;
 
    // If target is same as root.  Use the downward function
    // to print all nodes at distance k in subtree rooted with
    // target or root
    if (root == target)
    {
        printkdistanceNodeDown(root, k);
        return 0;
    }
 
    // Recur for left subtree
    int dl = printkdistanceNode(root.left, target, k);
 
    // Check if target node was found in left subtree
    if (dl != -1)
    {
         // If root is at distance k from target, print root
         // Note that dl is Distance of root's left child from target
         if (dl + 1 == k)
            System.out.println(root.data) endl;
 
         // Else go to right subtree and print all k-dl-2 distant nodes
         // Note that the right child is 2 edges away from left child
         else
            printkdistanceNodeDown(root.right, k-dl-2);
 
         // Add 1 to the distance and return value for parent calls
         return 1 + dl;
    }
 
    // MIRROR OF ABOVE CODE FOR RIGHT SUBTREE
    // Note that we reach here only when node was not found in left subtree
    int dr = printkdistanceNode(root.right, target, k);
    if (dr != -1)
    {
         if (dr + 1 == k)
            System.out.println(root.data) endl;
         else
            printkdistanceNodeDown(root.left, k-dr-2);
         return 1 + dr;
    }
 
    // If target was neither present in left nor in right subtree
    return -1;
}


Method 2 - Using the queue

Use a queue of size K to store the root to node path.
Now since, the queue is of size K.As soon as we find the NODE  in tree, the node at front of queue is at a distance K from NODE. It can be the case that the front node is less than K distant from NODE.
So, maintain a counter.

Now start popping a node from queue which is at distant  i from NODE, and print all downwards nodes at distance K-i  in its other subtree.We only need to print the nodes in other  subtree to avoid Error.

Note :- Since we need to print the nodes in sorted order, we can maintain a priority queue to store the nodes and after processing the nodes, we can print it.

References

Print all nodes that are at distance k from a leaf node

Problem

Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node.

Here the meaning of distance is different from previous post. Here k distance from a leaf means k levels higher than a leaf node. For example if k is more than height of Binary Tree, then nothing should be printed. Expected time complexity is O(n) where n is the number nodes in the given Binary Tree.




Example
(Please ignore the empty node, and consider it null)

k = 1, Answer = 2, 19 , 21
k = 2, Answer = 5, 18 , 19

Solution

The idea is to traverse the tree. Keep storing all ancestors till we hit a leaf node. When we reach a leaf node, we print the ancestor at distance k. We also need to keep track of nodes that are already printed as output. For that we use a boolean array visited[].

// This function prints all nodes that are distance k from a leaf node
//   path[] - Store ancestors of a node
//   visited[] - Stores true if a node is printed as output.  A node may be k
//                 distance away from many leaves, we want to print it once 
void kDistantFromLeafUtil(Node node, int path[], bool visited[],
                          int pathLen, int k)
{
    // Base case
    if (node==null) return;
 
    // append this Node to the path array 
    path[pathLen] = node.data;
    visited[pathLen] = false;
    pathLen++;
 
    // it's a leaf, so print the ancestor at distance k only
    // if the ancestor is not already printed  
    if (node.left == null && node.right == null &&
        pathLen-k-1 >= 0 && visited[pathLen-k-1] == false)
    {
        System.out.print(path[pathLen-k-1] + " ");
        visited[pathLen-k-1] = true;
        return;
    }
 
    // If not leaf node, recur for left and right subtrees 
    kDistantFromLeafUtil(node.left, path, visited, pathLen, k);
    kDistantFromLeafUtil(node.right, path, visited, pathLen, k);
}
 
// Given a binary tree and a nuber k, print all nodes that are k
//   distant from a leaf
void printKDistantfromLeaf(Node node, int k)
{
    int[] path = new int[MAX_HEIGHT];
    boolean[] visited = new boolean[MAX_HEIGHT];
    //all the elements false in visited
    Arrays.fill(visited, false);
    kDistantFromLeafUtil(node, path, visited, 0, k);
}


References