[20.13] largest possible rectangle of letters

1. Example

maximal square
maximal rectangle
maximal possible sum
maximum rectangle letter

Example

From cat, car, ape, api, rep, tip we get the following rectangle (which is a square):

c a r
a p e
t i p

2. Implementation

WordGroup[] groupList = WordGroup.createWordGroups(list);
private int maxWordLength = groupList.length;
private Trie trieList[] = new Trie[maxWordLength];





public Rectangle maxRectangle()
{
     int maxSize = maxWordLength*maxWordLength;
     // NOTE: area
     for ( int z = maxSize; z > 0; z-- ) {
         // NOTE: length
         for ( int i= 1; i <= maxWordLength;i++ ) {
                if (  z%i==0  )
                {
                       int j = z / i ;
                      
                }
         }
     }
     

}




private Rectangle makeRectangle(int length, int height)
{


}





private Rectangle makePartialRectangle(int l, int h, Rectangle rectangle)
{


}

1. each row must be the same length and each column must have the same length.

So, let’s group the words of the dictionary based on their sizes.Let’s call this grouping D, where D[i] provides a list of words of length i.

3. Similar Ones
https://github.com/monkeylyf/interviewjam/blob/master/recursion/cap_Words_Rectangle.java
http://stackoverflow.com/questions/8512174/largest-possible-rectangle-of-letters

[20.12] largest submatrix sum in O(n^3)

[Updated 11/21]

import java.lang.*;

// Approach#1 O(n^6) time.
public class LargestSubmatrixSum {
//    Given an NxN matrix of positive and negative integers, write code to find the
//    submatrix with the largest possible sum.
    
    //brute force: O(n^6) time.
    //returns [r1, c1, r2, c2, sum] where (r1,c1),(r2,c2) represents 
    //the diagonal of submatrix
    static int[] findLargestSubmatrix(int[][] matrix) {
        int maxSum = Integer.MIN_VALUE;
        int[] ret = {-1, -1, -1, -1, 0};
        for (int r1 = 0; r1 < matrix.length; ++r1) {
            for (int r2 = r1; r2 < matrix.length; ++r2) {
                for (int c1 = 0; c1 < matrix[0].length; ++c1) {
                    for (int c2 = c1; c2 < matrix[0].length; ++c2) {
                        int sum = getSum(matrix, r1, c1, r2, c2);
                        if (sum > maxSum) {
                            maxSum = sum;
                            ret = new int[] {r1, c1, r2, c2, sum};
                        }
                    }
                }
            }
        }
        return ret;
    }
    
    static int getSum(int[][] matrix, int r1, int c1, int r2, int c2) {
        int sum = 0;
        for (int r = r1; r <= r2; ++r) {
            for (int c = c1; c <= c2; ++c) {
                sum += matrix[r][c];
            }
        }
        return sum;
    }

// Approach#1 O(n^4) time.    
    //preprocess matrix: O(n^4) time, reducing getSum to constant time.
    static int[][] processMatrix(int[][] m) {
        if (m == null) return null;
        int[][] sumMatrix = new int[m.length][m[0].length];
        sumMatrix[0][0] = m[0][0];
        for (int j = 1; j < m[0].length;j++){
            sumMatrix[0][j]=sumMatrix[0][j-1]+m[0][j];
            //System.out.println(0+","+j+" - "+sumMatrix[0][j]+",");
        }
        for (int i = 1; i < m.length;i++){
            sumMatrix[i][0]=sumMatrix[i-1][0]+m[i][0]; 
            //System.out.println(i+","+0+" - "+sumMatrix[i][0]+",");
        } 
        for (int i =1; i< m.length;i++) {
            for (int j=1; j < m[0].length;j++){
                sumMatrix[i][j] = sumMatrix[i-1][j]+sumMatrix[i][j-1]-sumMatrix[i-1][j-1]+m[i][j];
                //System.out.println(i+","+j+" - "+sumMatrix[i][j]+",");
            }
            
        }
        return sumMatrix;
        
        //for (int i = 0; i < m.length; ++ i) {
        //    int sumRowOne = 0; int sumColOne = 0;
        //    for (int j = 0; j < m[0].length; ++j) {
        //        if (i == 0) {
        //            sumRowOne += m[i][j];
        //            sumMatrix[i][j] = sumRowOne;
        //        }
        //        if (j == 0) {
        //            sumColOne += m[i][j];
        //            sumMatrix[i][j] = sumColOne;
        //        }
        //        if (i != 0 && j != 0) {
        //            sumMatrix[i][j] = m[i][j] + 
        //                    sumMatrix[i][j-1] + 
        //                    sumMatrix[i-1][j] - 
        //                    sumMatrix[i-1][j-1];
        //        }
        //        System.out.println(i+","+j+" - "+sumMatrix[i][j]+",");
        //    }
        //}
        //return sumMatrix;
    }
    
    static int getSum2(int[][] sumMatrix, int r1, int c1, int r2, int c2) {
  
       if (r1 == 0 && c1 == 0){
           return sumMatrix[r2][c2];
       }
       else if (r1 == 0){
           return sumMatrix[r2][c2]-sumMatrix[r2][c2-1];
       } 
       else if (c1 == 0 ){
           return sumMatrix[r2][c2]-sumMatrix[r1-1][c2];
       } else {
           return sumMatrix[r2][c2]-sumMatrix[r2][c1-1]-sumMatrix[r1-1][c2]+sumMatrix[r1-1][c1-1];
       }
      
       // return sumMatrix[r2][c2] - 
    //            sumMatrix[r1][c2] - 
    //            sumMatrix[r2][c1] + 
    //            sumMatrix[r1][c1];
    }

static int[] findLargestSubmatrix2(int[][] matrix) {
        int maxSum = Integer.MIN_VALUE;
        int[] ret = {-1, -1, -1, -1, 0};
        int[][] subMatrix = processMatrix(matrix);
        for (int r1 = 0; r1 < matrix.length; ++r1) {
            for (int r2 = r1; r2 < matrix.length; ++r2) {
                for (int c1 = 0; c1 < matrix[0].length; ++c1) {
                    for (int c2 = c1; c2 < matrix[0].length; ++c2) {
                        int sum = getSum2(subMatrix, r1, c1, r2, c2);
                        //System.out.println(r1+","+c1+";"+r2+","+c2+" - "+sum+",");
                        if (sum > maxSum) {
                            maxSum = sum;
                            ret = new int[] {r1, c1, r2, c2, sum};
                        }
                    }
                }
            }
        }
        return ret;
    }    

// Approach#3 O(n^3) time.    
/**
   * 
   * @param matrix
   * @return return the max.
   *   1,1,1 => row start
   *   2,2,2
   * + 3,4,5 => row end 
   * ________
   *   6,7,8 => one row thinking => find maximum subarray?
   *   check every end and sum so far
   *   row =0 end => 1,1,1 => find maximum subarray?
   *   row =1 end => 3,3,3 => find maximum subarray?
   *   row =2 end => 6,7,8 => find maximum subarray?
   */
  public static int maxSubMatrix(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
      return 0;
    }
    int max = Integer.MIN_VALUE;
    for (int start = 0; start < matrix.length; ++start) {//different row start form different submatrix
      int[] arr = new int[matrix[0].length];// a new array for storing column compressing sum
      for (int end = start; end < matrix.length; ++end) {// different end with same start form different submatrix
        // Construct a array
        for (int k = 0; k < matrix[0].length; ++k) {
          arr[k] += matrix[end][k];
        }
        // Find maximum subarray  
        max = Math.max(max, maxArea(arr));
      }
    }
    return max;
  }

  // use max subarray to find max
  private static int maxArea(int[] arr) {
    int local = 0;// NOTE: cannot Integer.MIN_VALUE
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length;i++){
        local = Math.max(arr[i], local+arr[i]);
        max= Math.max(local, max);
    }
    return max;
  }    
    
    
    //--------------------------------------
    public static void main(String[]args) {
        int[][]m = {
                {1,-2,3,1},
                {1,5,-4,1},
                {1,1,0,2},
                {-1,1,1,-8}};
        long start =  System.nanoTime();     
        int[] r = findLargestSubmatrix(m);//// Approach#1 O(n^6) time.
        long end = System.nanoTime();  
         System.out.println("Time:"+(long)(end-start)+"("+r[0]+", "+r[1]+") ("+r[2]+", "+r[3]+") sum: "+r[4]);
        long start2 = System.nanoTime();
        int[] r2 = findLargestSubmatrix2(m);//// Approach#2 O(n^4) time.
        long end2 = System.nanoTime();         
         System.out.println("Time:"+(long)(end2-start2)+"("+r2[0]+", "+r2[1]+") ("+r2[2]+", "+r2[3]+") sum: "+r2[4]);
        long start3 = System.nanoTime();
        int r3 = maxSubMatrix(m);//// Approach#3 O(n^3) time.
        long end3 = System.nanoTime(); 
        System.out.println("Time:"+(long)(end3-start3)+", sum:"+r3);
    }

}

[Old ] 1. Example



Area(x2,y2,x1,y1) = Area(x2,y2) - Area(x1,y2)- Area(x2,y1) + Area(x1,y1) 

sumMatrix[i][j] = 

 matrix[i][j] + sumMatrix[i - 1][j] + sumMatrix[i][j - 1] - sumMatrix[i - 1][j - 1] ;

if ( i==0 && j ==0 ) { 

 sumMatrix[i][j] = matrix[i][j]; } 

 else if ( j == 0 ) { 

 sumMatrix[i][j] = matrix[i][j] + sumMatrix[i-1][j]; } 

 else if ( i == 0 ) { 

 sumMatrix[i][j] = matrix[i][j] + sumMatrix[i][j-1]; }

 else { 

sumMatrix[i][j] = matrix[i][j] + sumMatrix[i-1][j] + sumMatrix[i][j-1] - sumMatrix[i-1][j-1]; }






if (i1== 0 && j1 ==0)// start from row 0, column 0 

 return sumMatrix[i2][j2];

 else if ( i1 == 0) // start at row 0

 return sumMatrix[i2][j2] - sumMatrix[i2][j1-1]; 

 else if ( j1 == 0 ) // start at column 0 

 return sumMatrix[i2][j2] - sumMatrix[i1-1][j2]; 

 else 

 return sumMatrix[i2][j2] - sumMatrix[i2][j1-1] - sumMatrix[i1-1][j2] + sumMatrix[i1-1][j1-1];


// A mini-window between Left and Right. Fixed Left Increment Right to adjust Window
// Sum all the value in row basis from left column to right column, get the number of row value

0 -2 - 7 0
 9  2  -6 2
-4  1  -4 1
-1  8   0 -2




For the above matrix, the largest sum submatrix is:


 9 2
-4 1
-1 8


2. Impelementation

// Time:O(n^4), Space:O(n^2)

public static int getMaxMatrix(int[][] original)
{




    // Important ! could be less than 0
    int maxArea = Integer.MIN_VALUE;
    int rowCount = original.length;
    int columnCount = original[0].length;
    int[][] matrix = precomputeMatrix(original);


     

    for (int  row1 =0; row1< rowCount; row1++ ){
       for (int row2 = row1; row2 < rowCount; row2++){
          for (int col1 = 0; col1 < colCount; col1++) {
              for(int col2 = col1; col2 < colCount; col2++;) {
                       maxArea = Math.max(maxArea, computeSum(martix, row1, row2, col1,col2) );
              }
          }
       }
    }





}            




private static int[][] preComputeMatrix(int[][] matrix)
{

     // NOTE : every thing returned A NEW OBJECT
     int[][] sumMatrix = new int[matrix.length][matrix[0].length];    



     for (int i = 0 ; i < matrix.length;i++){
       for (int j = 0; j < matrix[0].length;j++){
            if ( i==0 && j ==0 )
            {
                 sumMatrix[i][j] = matrix[i][j];
            }
            else if ( j == 0 )
            {
                 sumMatrix[i][j] = matrix[i][j] + sumMatrix[i-1][j];
            }
            else if ( i == 0 )
            {
                 sumMatrix[i][j] = matrix[i][j] + sumMatrix[i][j-1];
            }
            else 
            {
                sumMatrix[i][j] = matrix[i][j] + sumMatrix[i-1][j]  + sumMatrix[i][j-1] - sumMatrix[i-1][j-1];  
            }              
       }
     }

   
     return sumMatrix;


} 




private static int computeSum(int[][] matrix, int i1, int i2, int j1, int j2)
{
        
        if (i1== 0 && j1 ==0)// start from row 0, column 0
            return sumMatrix[i2][j2];
        else if ( i1 == 0) // start at row 0
            return sumMatrix[i2][j2] - sumMatrix[i2][j1-1];
        else if ( j1 == 0 ) // start at column 0
            return sumMatrix[i2][j2] - sumMatrix[i1-1][j2];
        else 
            return sumMatrix[i2][j2] - sumMatrix[i2][j1-1] - sumMatrix[i1-1][j2] + sumMAtrix[i1-1][j1-1];

}

// Time:O(n^3)
// A mini-window between Left and Right. Fixed Left Increment Right to adjust Window
// Kadane's algorithm finds sub-array with maximum sum in O(n) for 1D arrays

public static int findMaxSum (int[][] matrix)
{
    int maxSum=0;
    int numCols = matrix[0].length;
    int numRows = matrix.length;

    for (int left = 0; left < numCols; left++)
    {
        int temp[numRows] = {0};
 
        for (int right = left; right < numCols; right++)
        {
            // Find sum of every mini-row between left and right columns and save it into temp[]
            for (int i = 0; i < numRows; ++i)
                temp[i] += matrix[i][right];
 
            // Find the maximum sum subarray in temp[].
            int sum = kadane(temp, numRows);
 
            if (sum > maxSum)
                maxSum = sum;
        }
    }
 
    return maxSum;
}
 

http://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_07_-_Submatrix_with_largest_sum.jsp

3. Similar Ones
http://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_07_-_Submatrix_with_largest_sum.jsp

[20.11] (Maximal Square) Maximum subsquare such that all four borders are filled with black pixels

1. Example

At each column, we’re trying to create a square with that column as the left side. The largest such square we could possibly create is N - currentColumn. 

const int mmap[5][5]=

{
{1,1,0,0,1},
{0,1,0,1,1},
{1,1,1,0,1},
{1,1,1,0,1},
{1,1,1,0,1}
};

1 0 1 0 0 

1 0 1 1 1 

1 1 1 1 1 

1 0 0 1 0

// Approach#1: Time:O(N*N),SpacE:O(N*N)
int[][] dp = new int[][];
dp[i][j]   = matrix[i][j] = 1 ?   min(      min(dp[i-1][j], dp[i][j-1])  ,    dp[i-1][j-1]       )
                                              :    0;
              .
              .
        dp[i-1][j-1]  dp[i-1,j]
        dp[i,j-1]            1
max = Math.max(max, dp[i][j]);
return (int)Math.pow(max, 2);
NOTE: need [i-1][j-1] so initialize [0][j] and [i][0]

//Approach#2  Time:O(N*N),SpacE:O(N)

int[] heights = new int[matrix[0].length];  

heights[j] = (i==0)? matrix[i][j]
                              : height[j] + matrix[i][j]
int curArea = largestArea(heights);
maxArea = Math.max(curArea, maxArea);

NOTE:  stack keep those with smaller height
height = previous height SINCE smaller height would dominate
so keep the idnex with smaller height and 
width = current - precious precvious's index
if previous index is 0 then set is as -1
otherwise, previous precious index

h   1 2   3  4
                 |
             |   |
         |   |   |
     |   |   |   |
-----------------
i   0 1  2  3
height = h[0]
width = len -(-1)-1 = len
max= height* height since height < width

h   1 4   3  2
         |      
         |   |
         |   |   |
     |   |   |   |
-----------------
i   0 1  2  3

i = 2, h[2] <= h[1]
index = 1
height = h[1] =4
preIndex = 0;
width = 2(i)-0(preIndex)-1 = 1;
maxArea = 1*1=1
put 2 in stack

i=3
index = 2
height = h[2] = 3
preIndex = 0
width = 3 - 0 - 1 =2
maxArea = 2*2=4



2. implementation

//  Time:O(N*N),SpacE:O(N)

public int maximalSuqare(int[][] matrix)
{
    


       // validate the input
       if ( matrix == null || matrix.length ==0 || matrix[0].length ==0 )
            return 0;
 


       int[] heights = new int[matrix[0].length];
       int maxArea = 0;
      

      
       for (int i = 0 ; i < matrix.length; i++)
       {
             for (int j = 0 ; j < matrix[0].length ; j ++)
             {



                    if (matrix[i][j] ==1 )
                        heights[j] +=1;
                    else  
                        heights[j] = 0;



             }




             int curArea = largestArea(heights);
             maxArea = Math.max(curArea, maxArea);



       }
}



// Idea: Compare with previous height, if less than we calculate
private int largestArea(int[] heights)
{


      

       int maxArea = 0;
       LinkedList stack = new LinekdList();   




       
       for (int i = 0; i < heights.length; i++)
       {

             while (   !stack.isEmpty() && heights[i] <= heights[stack.peek()]  )
             {
NOTE:  stack keep those with smaller height

                     int index = stack.pop();
                     int height = heights[index];
                     int preIndex = stack.isEmpty() ?-1: stack.peek();
                     int width = i - preIndex -1;
                     maxArea = Math.max(maxArea, height < width? height*height: width:width);
             }
NOTE:  stack keep those with smaller height

             stack.push(i);
       }




       while (!stack.isEmpty())
       {
                     int index = stack.pop();
                     int height = heights[index];
                     int preIndex = stack.isEmpty() ?-1: stack.peek();
                     int width = heights.length - preIndex -1;
                     maxArea = Math.max(maxArea, height < width? height*height: width:width);

       }


       return maxArea;


}

//  Time:O(N*N),SpacE:O(N*N)

public int maximalSquare(int[][] matrix)
{
     




       // validate the input
       if (matrix == null || matrix.length ==0 )
            return 0;
       

        

       int[][] dp = new int[matrix.length][matrix[0].length];
       int max = 0;


   



        for (int i = 0; i < matrix.length; i++) {
            dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
            max = Math.max(max, dp[i][0]);
        }





        for (int j = 0; j < matrix[0].length; j++) {
            dp[0][j] = matrix[0][j] == '1' ? 1 : 0;
            max = Math.max(max, dp[0][j]);
        }
        




        
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                dp[i][j] = matrix[i][j] == '1' ? 
                Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1 : 0;
                max = Math.max(max, dp[i][j]);
            }
        }





       return max*max;      




}

public static SubSquare findSquare( int[] matrix )
{



     // validate the input
     if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
         return null;




     int N = matrix.length;




     int currentMaxSize = 0;
     SubSquare sq = null;
     int col = 0;



     
     // STEP1: iterate through each column from left to right
     while (  N - col > currentMaxSize  )
     {
            for (int row = 0; row < N; row++)
            {
                // strating from the biggest
                int size = N - Max.max(row, col);
                while ( size > currentMaxSize )
                {    
                    if (  isSquare(martix, row, col, size)  )
                    {

                          currentSize = size;
                          sq = new SubSquare(row, col,size);
                          break;
                    }


                    size--;


                }
            } 
            

        
            col++;

            

     }   



    
}



private static boolean isSquare (int[][] matrix, int row, int col, int size)
{                                                 





        // Check top and bottom border, --->,     down
        // Extend by offset (the size)
        // <------col------>
        // |
        // |
        // |
        for (itn j =  0; j < size ; j ++)
        {
               if ( matrix[row][col+j] == 1)
                    return false;
               if ( matrix[row+size-1][col+j]==1)
                    return false;

        }
        // Check left and right border
        // Extend by offset (the size)
        // ----->
        // |
        // |
        // |
        // --->
        for(int i =0; i < size -1;i++)
        {
               if ( matrix[row+i][col] == 1)
                   return false; 
               if ( matrix[row+i][col+size-1] ==1  )
                   return false;
        }        






        return true;




}

public class SubSquare
{
      public int row, column, size;
      public Subsquare(int r, int c, int s)
      {
           row = r;
           column = c;
           size = s;
      }
}

3. Similar Ones
http://massivealgorithms.blogspot.com/2014/07/maximum-size-square-sub-matrix-with-all.html
http://jeffmeng.com/imagine-there-is-a-square-matrix-with-n-x-n-cells-each-cell-is-either-filled-with-a-black-pixel-or-a-white-pixel-design-an-algorithm-to-find-the-maximum-subsquare-such-that-all-four-borders-are-fill/
http://massivealgorithms.blogspot.com/2014/07/maximum-size-square-sub-matrix-with-all.html

[20.10] word ladder

1. Example
Breadth First Search

http://rangerway.com/way/leetcode-word-ladder-ii/
start = hit
end = cog
dict =[hot,dot,dog,lot,log,dof,mit,sit,set,mog,mig,seg,nax,max]



level 1: [hit]
level 2: [mit, sit, hot]
level 3: [mig, set, dot, lot]
level 4: [mog, seg, dof, dog, log]
level 5: [cog]

Return

  [["hit","hot","dot","dog","cog"],
   ["hit","hot","lot","log","cog"],
   ["hit","mit","mig","mog","cog"]]

Input: DAMP, LIKE
Output: DAMP-> LAMP->LIMP->LIME->LIKE
 
http://www.programcreek.com/2012/12/leetcode-word-ladder/

25*L , L is the length of the string, every letter has 25 possibility
so there are total 25*L possibilities


2. Implementation

// Dictionary 26^L or size(dict)
// Time:O( min(26^L, size(dict)) ), Space:O( min(26^L, size(dict) )  ) 

// Time :O(m*m)

public List wordLadder(  String startWord, String stopWord, Set dictionary )
{



        List res = new ArrayList();
        //validate the input
        //if ( startWord == null || stopWord == null || dictionary == null )  
        if ( stratWord == null || stratWord.length() ==0 || stopWord == null || stopWord.length() ==0 || startWOrd.length() != stopWord.length() || dictionary == null )
             return res;




       
        startWord = startWord.toLowerCase();
        stopWord = stopWord.toLowerCase();
        LinkedList queue = new LinkedList();
        HashSet visited = new HashSet();
        int lastNum = 1;
        int curNum = 0;
        int level =1;
        queue.offer(startWord);
        visited.offer(startWord);


        


        while ( !queue.isEmpty() )
        {



             String cur = queue.poll();
             lastNum--;


             
             for ( int i = 0 ; i < cur.legnth(); i++ )
             {
                 char[] charCur = cur.toCharArray();
                 for ( char c='a'; c < 'z';c++ )
                 {
                     charCur[i] = c;
                     String temp = new String(charCur);



                     if (temp.equals(end))
                     {
                             list.add(end);
                             return list;
                             //return level+1;
                     }



                     if ( dict.contains(temp) && !visited.contains(temp) )
                     {
                          curNum++; 
                          queue.offer(temp);
                          visited.add(temp);
                          list.add(temp);
                     }




                 }

             }



             if (lastNum == 0)
             {
                  lastNum = curNum;
                  curNum = 0;
                  level++;
             }
        }


        
       
        return null;



}

3. Similar one
http://blog.csdn.net/linhuanmars/article/details/23029973

[20.9] Maintain Median value when new values are added

1. Example

 The default PriorityQueue is implemented with Min-Heap, that is the top element is the minimum one in the heap.
https://www.quora.com/How-do-I-calculate-the-median-of-given-sets-of-numbers-when-the-number-of-elements-in-a-list-are-changed

Example:
Starting configuration of heaps
Starting from the example you've considered, the heaps may look like this:
Left tree = max-heap, Right-tree = min-heap

Inserting an element in appropriate heap
Let's see, what happens if you get a new number, say 5:
Clearly, it's less than the root of max-heap, so we must insert it there.
Simply add it to the first available leaf in the tree.

Balancing the relevant heap
Now, successively swap until each parent is greater than its children (in case of min-heap, the condition is reversed; i.e. swap until each parent is smaller than its children)

Finding the median
Now, we see that difference in # of elements = 1, max-heap has more elements, therefore median = root of the max-heap = 6

Space-time complexity
For the heap approach, insertion and balancing takes O(log n). Looking up the median is O(1).

Below Value => max heap: 2,3,4,5(include median)
Above Value => min heap:6,10,11

A new value came in 
if larger than max heap => go to Above heap(min heap)
if smaller or equal to max heap => go to Below heap(max heap)
Odd number -> the size of below heap has one extra
Even number -> equal size on both heap


Get median => get max from max heap =>O(1)
Add number => heapify => O(logn) 

• A Comparator can be provided in the constructor when instantiating a PriorityQueue. Then the order of the items in the Queue will be decided based on the Comparator provided.
• If a Comparator is not provided, then the natural order (Comparable) of the Collection will be used to order the elements.

s={1,2,3,4,5} = > Median = 3
s= {1,2,3,4,5,6} => Median = (3+4)/2 = 3.5
s= {1,2,3,4,5,6,7}=>Median = 4

s= {4,5,6} = > Median =5
s=    {3,4,5,6}=>Median =4.5
s= {2,3,4,5,6,10}=> Median =4.5
s= {2,3,4,5,6,10,11}=> Median =5



Median = number of elements


2. Implementation
Q1: add a number larger than max
Q1: add a number smaller than min

// O(n) space, O(logn) time
public class Question9 {

  public static class MaxHeapComparator implements Comparator {
    public int compare(Integer first, Integer second) {
      return -first.compareTo(second);
    }
  }
  // max heap
  private PriorityQueue smallerHalf = new PriorityQueue(100, new MaxHeapComparator());
  // min heap
  private PriorityQueue largerHalf = new PriorityQueue();
  
  public void add(int newData) {

    largerHalf.add(newData);
    // always keep smallerHalf plus 1
    if (smallerHalf.size() < largerHalf.size()) {
      int elem = largerHalf.poll();
      smallerHalf.add(elem);
    }

  }

  public int median() {

     if ( smallerHalf.size() == 0  )
            return largerHalf.peek();
     else if ( largerHalf.size() == 0)
            return smallerHalf.peek();

    if (smallerHalf.size() + largerHalf.size() == 0) {
      return 0;
    }
    if (smallerHalf.size() == largerHalf.size()) { // even number
      return (smallerHalf.peek() + largerHalf.peek()) / 2;
    }
    return smallerHalf.peek(); // odd number, in add() always keep smallerHalf plus 1

  }

}

// Time:O(1) to get median, O(logn) to add a new number

private Comparator maxHeapComparator, minHeapComparator;
private PriorityQueue maxHeap, minHeap;

public void addNewNumber(int newNum)
{
       
      // Even
      if (maxHeap.size() == minHeap.size())
      {
           if ( minHeap.peek() != null && newNumber > minHeap.peek() )
           {
               // maintain maxHeap has one extra
               maxHeap.offer(minHeap.poll());
               minHeap.offer(newNumber);
           }
           else // if newNumber <= maxHeap.peek(), maxHeap suppose has one extra
           {
               maxHeap.offer(newNumber);
           }
      }
      // Odd( assume maxHeap has extra one)
      else 
      {
           // add to maxHeap, remove one to minHeap first
           if (  newNum < maxHeap.peek() )
           {
                  minHeap.offer( maxHeap.poll()  );
                  maxHeap.offer(  newNumber );
           }
           else 
           {
                  minHeap.offer(newNumber);
           }
      }
}



public static double getMedian ()
{



      if ( maxHeap.isEmpty()  )
            return minHeap.peek();
      else if ( minHeap.isEmpty() )
            return maxHeap.peek();
       


      if ( maxHeap.size() == minHeap.size() )
           return ( maxHeap.peek() + minHeap.peek() ) /2;
      else if ( maxHeap.size() > minHeap.size()  ) 
           return maxHeap.peek();
      else
           return minHeap.peek();

}

3. Similar Ones
http://javapapers.com/java/java-priorityqueue/
http://stackoverflow.com/questions/6065710/how-does-javas-priorityqueue-differ-from-a-min-heap-if-no-difference-then-why

[20.8] strsStr, find mutliple substring within a string

1. Example

Suffix Trie or LeetCode: Implement strStr

http://www.geeksforgeeks.org/pattern-searching-set-8-suffix-tree-introduction/

LeetCode: Implement strStr one-to-one()
public int strStr(String haystack, String needle) {
1.brute-force   :Time O(n*m),    SpaceO(1)
2.Rolling Hash:Time O(n)     ,    Space:O(1), concern: Big integer ('z'-'a')*26^8 
3.KMP             :Time O(n)     ,    Space:O(1)
where n is the length of haystack

CC150: Suffix tree  strsStr one-to-many()
public int[] strsStr(String haystack, String[] needles) {

1. suffix tree    : Time O(m), Space:O(n)where m is the length of needles

http://www.geeksforgeeks.org/pattern-searching-set-8-suffix-tree-introduction/

Let us consider an example text “banana\0″ where ‘\0′ is string termination character. Following are all suffixes of “banana\0″

banana\0
anana\0
nana\0
ana\0
na\0
a\0
\0

Build a standard Trie
f we consider all of the above suffixes as individual words and build a trie, we get following


Derive a Compressed Trie
If we join chains of single nodes, we get the following compressed trie, which is the Suffix Tree for given text “banana\0″


       0 1 2 3
A1: b i  b s

s
ibs
b s
    ibs
                         root
            /              |         \
           B   0,2     I   1      S 3
         /    \           |      
       I0      S2     B  1
       |                   |
       B0               S 1
       |
       S0

1. SuffixTree: all you need to do is search for each string in T in the suffix tree.

Note that if “B” were a word, you would come up with two locations

String testString = "mississippi";
String[] stringList = {"is", "sip", "hi", "sis"};

Implement strStr multiple times ( String needle, String hayStack )
multiple needles need to check if a substring of hayStack
2. KMP multiple times => KMP:O(m) * n
n smaller strings => n prefix table

2. Implementation

Q1: suffix tree for s (hayStack)
A1: bibs
 
s
ibs
b s
    ibs
Q1:
   

  public class Question {
  public static void main(String[] args) {
  String testString = “mississippi”;
  String[] stringList = {“is”, “sip”, “hi”, “sis”};
  SuffixTree tree = new SuffixTree(testString);
  for (String s : stringList) {
  ArrayList list = tree.getIndexes(s);
  if (list != null) {
  System.out.println(s + “: “ + list.toString());
  }
  }
  }
  }


// Create the tree with the root
 
public class SuffixTree {
 SuffixTreeNode root = new SuffixTreeNode();
 public SuffixTree(String s) {
 for (int i = 0; i < s.length(); i++) {
 String suffix = s.substring(i);
 root.insertString(suffix, i);
 }
 }
 
  public ArrayList getIndexes(String s) {
  return root.getIndexes(s);
  }
  }
 
  public class SuffixTreeNode {
  HashMap children = new
  HashMap();
  char value;
  ArrayList indexes = new ArrayList();
  public SuffixTreeNode() { }
 
  public void insertString(String s, int index) {
  indexes.add(index);
  if (s != null && s.length() > 0) {
  value = s.charAt(0);
  SuffixTreeNode child = null;
  if (children.containsKey(value)) {
  child = children.get(value);
  } else {
  child = new SuffixTreeNode();
  children.put(value, child);
  }
  String remainder = s.substring(1);
  child.insertString(remainder, index);
  }
  }
 
  public ArrayList getIndexes(String s) {
  if (s == null || s.length() == 0) {
  return indexes;
  } else {
  char first = s.charAt(0);
  if (children.containsKey(first)) {
  String remainder = s.substring(1);
  return children.get(first).getIndexes(remainder);
  }
  }
  return null;
  }
  }
 

3. Similar Ones

[20.7] find the longest word made of other words

1. Example

Sort By Length + LeetCode: Word Break 


Input from file :

"This" "is" "example" "an" "anexample" "Thisisanexample" "Thisistheexample"

Output :

"Thisisanexample" from "This" "is" "anexample" or "This" "is"  "an" "example"

2. Implementation
1.O(n log n) Sort the array by size, putting the longest word at the front
2.O(d) For each word, split it in all possible ways.
That is, for "test", split it into
{"t","est"}
{"te","st"}
{"tes","t"}
3.O(1) Then , for each pairing, check if the first half and the second both exist elsewhere in the array.
4. "Short circut" by returning the first string we find that fit condition #3
Time :O(n log n + n * d), Space:O(n) hashtable to find if the split string in array

1.O(n log n) Sort the array in alphabetical order
2.O( log n) Rather than looking up the word in a hash table, we would use binary search in the array
3. We would no longer be able to short circuit

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
public class HelloWorld{



//    Given a list of words, write a program to find the longest word made of other
//    words in the list.
//    EXAMPLE
//    Input: cat, banana, dog, nana, walk, walker, dogwalker
//    Output: dogwalker

    static String findLongestWord(String[] words) {
        if (words == null || words.length == 0) return null;
        HashSet map = new HashSet();
        for (String word : words) {
            map.add(word);
        }
        Arrays.sort(words, new Comparator() {
            @Override
            public int compare(String o1, String o2) {
                return ((Integer) o2.length()).compareTo(o1.length());
            }
        });
        for (String word : words) {
            if (isBreakable(word, map)) {
                return word;
            }
        }
        return "";
    }
    private static boolean isBreakable(String word, HashSet set){
        boolean[] res = new boolean[word.length()+1];
        res[0] = true;
        for (int i = 0 ; i < word.length();i++){
            StringBuilder str = new StringBuilder( word.substring(0,i+1) );
            for (int j=0;j <= i;j++){
                if (res[j] && set.contains(str.toString())){
                    res[i+1] = true;
                    break;
                }
                str.deleteCharAt(0);
            }
        }
        return res[word.length()];
    }
//
//    private static boolean isValid(String word, boolean isOriginal, //XXX: check originality!
//            HashSet map) {
//        if (!isOriginal && map.contains(word)) 
//           return true;
//        for (int i = 1; i < word.length(); ++i) {
//            String left = word.substring(0, i);
//            String right = word.substring(i);
//            if (isValid(left, false, map) && isValid(right, false, map))
//                return true;
//        }
//        return false;
//    }
//
    
    public static void main(String[]args) {
        String[]a= {"cat", "banana", "dog", "nana", "walk", "runner", "dogrunners", "s"};
        System.out.println(findLongestWord(a));
    }

}

// 1. Sort the array of string by length
class LengthComparator implements Comparator
{
      @Override
      public int compare (String s1 ,String s2)
      {
           if ( s1.length() > s2.length() ) return -1;
           if ( s1.length() < s2.length() ) return 1;
           return 0;
      }
}

public static void main (String[] args)
{
      BufferedReader br = null;
      try
      {




           // 1. Store the word from the file
           File file = new File(args[0]);
           br = new BufferedReader( new InputStreamReader(new FileInputStream(file)));
           Strign line = null;
           String[ ]words = new String[]{};
           while ( line=br.readLine() != null  )
                words = line.split("\\s+"); // splitting the string with spaces
             





           // 2. O(n log n) Sort the array by size, putting the longest word at the front

           Arrays.sort(  words, new LengthComparator() );





           // 3. O(1) Then , for each pairing, check if the first half and the second both exist elsewhere in the array.

           for (String str: words)
           {





                if ( str! =null )
                {
                String current = new String(str);
                for (String str2: words)
                {
                      // Note : not the same and str2 is a part of str
                      //        remove that part
                      if (  !str2.equals(current) && str.contains(str2) )
                            str = str.repalce(str2, "");
                }

                if ( str.length() == 0 )
                {
                      System.out.println(current);
                      break;
                }
                }







           }



         
      }
      catch(FileNotFoundException e)
      {
           System.out.println("File Not Found");
           return;
      }
      catch (IOException e)
      {
           e.printStackTrace();
      }
      finally
      {
           try
           {
                if (br != null)
                  br.close();
           }
           catch( IOException e)
           {
                e.printStackTrace();
           }
      }
}
// 2. Sort the array in alphabetical order
Arrays.sort( words );

3. similar Ones
http://stackoverflow.com/questions/29482947/substring-manipulation-in-java-find-the-longest-word-made-from-the-other-words http://stackoverflow.com/questions/29482947/substring-manipulation-in-java-find-the-longest-word-made-from-the-other-words