Sunday, August 3, 2014

Partition an array of integers into sub-arrays so that the difference of summaries (of sub-arrays) is minimal


Here is one solution (dynamic programming) for partition an array of integers into two sub-arrays so that the difference of summaries (of sub-arrays) is minimal.
// partition an array of integers into two sub-arrays so that the difference of summaries (of sub-arrays) is minimal
int balancePartitionTwoWays(int arr[], int n, int partition[2]) {

 if (n==2) {
  for (int i=0; i<2; i++) {
   partition[i]=arr[i];
  }
  return abs(partition[0]-partition[1]);
 }


 // loop through the array to find out the sum and maximum
 int sum=0;
 int maximum = -1;
 for(int i=0; i<n; i++){
  sum += arr[i];
  if (arr[i]>maximum) maximum = arr[i];
 }

 // allocate the matrix to remember
 bool memo[sum+maximum+1][2];
 for (int j = 0; j < 2; j++)
  for (int i = 0; i <= sum+maximum; i++)
    memo[i][j] = false;

 memo[0][0] = true;

 // mark memo[i][k] to true if there is a subset
    // of array [0..i-1] with sum equal to i
 for (int j = 0; j < n; j++) {
  for (int i = 0; i <= sum+maximum; i++) {

   if (memo[i][j%2]) {
    memo[i][(j+1)%2] = true;
    memo[i+ arr[j]][(j+1)%2] = true;

   }
  }
 }

 int max_diff = INT_MAX;
 int part[2];

 for (int i = 0; i <= sum+maximum; i++) {
  if (memo[i][n % 2]) {
   part[0]=i;
   part[1]=sum-i;
   int temp = abs(part[0]-part[1]) ;
   if (temp<max_diff) {
    max_diff = temp;
    partition[0] = part[0];
    partition[1] = part[1];
   }
  }
 }

 return max_diff;

}



// partition an array of integers into three sub-arrays so that the difference of summaries (of sub-arrays) is minimal
int balancePartitionThreeWays(int arr[], int n, int partition[3]) {

 if (n==3) {
  for (int i=0; i<3; i++) {
   partition[i]=arr[i];
  }
  return abs(partition[0]-partition[1]) + abs(partition[1]-partition[2]) + + abs(partition[2]-partition[0]);
 }


 // loop through the array to find out the sum and maximum
 int sum=0;
 int maximum = -1;
 for(int i =0; i<n; i++){
  sum += arr[i];
  if (arr[i]>maximum) maximum = arr[i];
 }

 // allocate the matrix to remember
 bool memo[sum+maximum+1][sum+maximum+1][2];
 for (int k = 0; k < 2; k++)
  for (int i = 0; i <= sum+maximum; i++)
   for (int j = 0; j <= sum+maximum; j++)
    memo[i][j][k] = false;

 memo[0][0][0] = true;

 // mark memo[i][j][k] to true if there is a subset
    // of array [0..i-1] with sum equal to i
 for (int k = 0; k < n; k++) {
  for (int i = 0; i <= sum+maximum; i++) {
   for (int j = 0; j <= sum+maximum; j++) {
    if (memo[i][j][k%2]) {
     memo[i][j][(k+1)%2] = true;
     memo[i+ arr[k]][j][(k+1)%2] = true;
     memo[i][j+ arr[k]][(k+1)%2] = true;
    }
   }
  }
 }

 int max_diff = INT_MAX;
 int part[3];

 for (int i = 0; i <= sum+maximum; i++) {
  for (int j = 0; j <= sum+maximum; j++) {

   if (memo[i][j][n % 2]) {
    part[0]=i;
    part[1]=j;
    part[2]=sum-i-j;

    //int temp = abs(part[0]-part[1]) + abs(part[1]-part[2]) + + abs(part[2]-part[0]);
    int temp = 0;
    for (int k=0; k<3; k++) {
     temp += abs(part[k%3]-part[(k+1)%3]);
    }
    if (temp<max_diff) {
     max_diff = temp;
     for (int k=0; k<3; k++) {
      partition[k]=part[k];
     }
    }
   }
  }
 }

 return max_diff;

}



Enjoy the journey. 

Sunday, April 6, 2014

O(n^2) solution to find out if and which 3 of them add up to 0

Here is a O(n^2) solution to find out if and which 3 of them add up to zero.

The Code is in Scala.

/**
 * O(n^2) solution to find out if and which 3 of them add up to 0
 * 
 */
object FindThreeNumbersSumToZero {
  
 def sort(arr:Array[Int]): Array[Int] =   
        if (arr.length<2) arr
        else {
            val pivot = arr (arr.length / 2)
            sort (arr filter (pivot>)) ++ 
            (arr filter (pivot == )) ++ sort (arr filter(pivot <))
        }
 
 def findThreeNumbersAddedToZero (arr: Array[Int]) : (Int, Int, Int) = {

  val a : Array[Int] = sort(arr);
  
  for(i <- 0 until a.length) {
    var iter = i+1;
    var reviter = a.length-1;
    while (iter < reviter) {
      var v = a(i) + a(iter) + a(reviter);
      if (v==0) 
        return (a(i), a(iter), a(reviter));
      else if (v<0)
        iter = iter + 1;
      else 
        reviter = reviter-1;
    }
  }
  return null;
 }
 
   def main(args: Array[String]) {
  
  val arr = Array(-11, 19, -2, 22, -4, 4, 10, 6,  12, 23)
  val tuple = findThreeNumbersAddedToZero (arr);
  println("array is [" + arr.mkString(" ") + "] ");
  println("tuple is " + tuple + "");
  
 }

}




Enjoy the journey. 

Friday, March 14, 2014

Given a number K, and an array of positive integers A, find two integers in the array which sum to K.

Problem: Given a number K, and an array of positive integers A, find two integers in the array which sum to K.

 Here we have two different algorithms to solve the problem.

Solution One:
Do an in-place merge sort on the array A;
Loop through each item A[i], use a binary search to check if K-A[i] is in the array;
If found, return the pair (A[i], K-A[i]);
If not found, return the null;

Time Complexity: O ( n * log(n) )
Space Complexity: O ( 1 )

Solution Two:
Allocate the array of size K;
Find the first element in the array A[s] that is less than K, and mark m[A[s] to 1
Loop through each remaining item A[i], check to see if m[K-A(i)] is 1
If m[K-A(i)] is 1, return the pair (A[i], K-A[i]);
If not found, return the null in the end.

Time Complexity: O ( n )
Space Complexity: O ( K )

The code is in Scala.

/**
 * 
 * Problem: Given a number K, and an array of positive integers A, find two integers in the array which sum to K.
 */

object FindPairSumToK {

 /*
  * Solution One:
  * Do an in-place merge sort on the array A;  
  * Loop through each item A[i], use a binary search to check if K-A[i] is in the array;
  * If found, return the pair (A[i], K-A[i]);
  * If not found, return the null;  
  * 
  * Time Complexity: O ( n * log(n) )
  * Space Complexity: O ( 1 ) 
  */
 def findPairSumToKwithSort(A: Array[Int], K: Int)  : (Int, Int) = {
     mergeSort(A, 0, A.length-1);
     for(i <- 0 until A.length){
       var t : Int = K - A(i);
       if (t>0) {
        var idx : Int = binarySearch(A, t);
        if (idx>=0) {
          return (A(i), A(idx));
        }
       }
     }
     return null;
   }
    
 /*
  * Solution Two:
  * 
  * Allocate the array of size K;
  * Find the first element in the array A[s] that is less than K, and mark m[A[s] to 1    
  * Loop through each remaining item A[i], check to see if m[K-A(i)] is 1
  * If m[K-A(i)] is 1, return the pair (A[i], K-A[i]);
  * If not found, return the null in the end.
  * 
  * Time Complexity: O ( n )
  * Space Complexity: O ( K ) 
  *       
  */
 def findPairSumToKwithDynamicProgramming(A: Array[Int], K: Int)  : (Int, Int) = {
        var m: Array[Int] = new Array[Int](K);
        var s : Int = 0;
      while (s<A.length && A(s)>=K) {
        s = s + 1;
      }
      m(A(s)) = 1;
     for(i <- s until A.length){
       var target : Int = K - A(i);
       if (target>=0 && m(target) ==1) {
        return (A(i), target);
       }
     }
     return null;
   }
    
   def reverse(a: Array[Int]): Unit = {
     if (a.length<=1) return;
     
     var i : Int = 0;
     var j : Int = a.length-1;
     while (i<j) {
      a(i) = a(i) + a(j);
      a(j) = a(i) - a(j);
      a(i) = a(i) - a(j);
      i=i+1;
      j=j-1;
    }
 }
   
   def binarySearch(A: Array[Int], target : Int) : Int = {
    var low : Int = 0;
    var high: Int = A.length-1;
    while (low<high) {
     var mid = (low + high) / 2;
     if (target==A(mid)) 
       return mid;
     else if (target<A(mid))
       high = mid-1;
      else 
        low = mid+1;
    }
    return -1;
   }
   
    def mergeSort(a : Array[Int] ) : Unit = {
    mergeSort(a, 0, a.length-1);
 }


    def mergeSort(A: Array[Int], low: Int, high: Int) : Unit = {
  if (low >= high) {
   return;
  }
  var mid = (low + high) / 2;
  mergeSort(A, low, mid);
  mergeSort(A, mid + 1, high);
  merge(A, low, mid, high);
 }

   def merge(a: Array[Int], Low: Int, Mid: Int, High : Int) : Unit = {
    var low = Low;
    var mid = Mid;
    var high = High;

  var i : Int = mid;
  var j : Int = mid + 1;
    while ((low <= i) && (j <= high)) {
   if (a(low) < a(j)) {
    low = low+1;
   } else {
    // shift from j to low
    var t = a(j);
    for (k <- j-1 to (low, -1) ) {
     a(k+1) = a(k);
    }
    a(low) = t;
    low = low + 1;
    i = i+1;
    j = j+1;
   }
    }
   }
   

 def print(a: Array[Int]): Unit = {
    println(a.mkString(" "))
 }
  
 def main(args: Array[String]) {
     
     val a = Array( 2, 5, 6, 1, 2, 3, 8, 16, 27, 23, 9, 17, 12, 14, 9, 11);
     var p = findPairSumToKwithSort(a, 19);
     println("p=" + p);
     p = findPairSumToKwithSort(a, 99);
     println("p=" + p);
     
     val aa = Array( 2, 5, 6, 1, 2, 3, 8, 16, 27, 23, 9, 17, 12, 14, 9, 11);
     p = findPairSumToKwithDynamicProgramming(aa, 19);
     println("p=" + p);
     p = findPairSumToKwithDynamicProgramming(aa, 99);
     println("p=" + p);
 }
}





Enjoy the journey. 

Saturday, February 8, 2014

Find Lowest Common Ancestor (LCA) using Range Minimum Query (RMQ) in O(N) Time


RMQ of A(i,j) – returns the index of the smallest element in the subarray A[i...j]

Given the Array E below, RMQ of E(2,7) is 3.















LCA of Tree (u,v) – given nodes u,v in Tree, returns the node furthest from the root that is an ancestor of both u and v.

Given the tree below, LCA("5", "9") is node "4". 




Suppose an algorithm has preprocessing time of f(n) and query time of g(n).

Notation for the overall complexity of an algorithm <f(n), g(n)>


Here we can reduce LCA problem to RMQ: If there is <f(n), g(n)> solution for RMQ, then there is an <f(2n-1)+O(n), g(2n-1)+O(1)> solution for LCA. 


The Euler tour of a tree is the path through the tree that begins at the root and ends at the root, traversing each edge exactly twice : once to enter the subtree, and once to exit it. The Euler tour of a tree is essentially the depth-first traversal of a tree that returns to the root at the end. The correspondence between a tree and its Euler tour is shown in the Figure above. Euler tour size is 2n-1 for a tree with n node. 

The LCA of nodes u and v is the shallowest node encountered between the visits to u and to v during a depth first search traversal (Euler tour) of Tree. Well, 
otherwise it will contradiction to the DFS tour.

On an input tree T with n nodes, we build 3 arrays.


Euler array E[1,..,2n-1]  The nodes visited in an Euler tour of T. E[i] is the label of the i-th node visited in the tour.


Level array L[1,..2n-1]  The level of the nodes we got in the tour. L[i]  is the level of node E[i]. (level is defined to be the distance from the root)


Representative array R[1,..n] – R[i] will hold the index of the first occurrence of node i in E[i]. 

R[v] = minimum of i where E[i] = v. 


To get LCA of Tree(x,y): 


All nodes in the Euler tour between the first visits to x and y are E[R[x],..,R[y]] assume that R[x] < R[y]. The shallowest node in the sub-tour is at index RMQ of L(R[x],R[y]), since L[i] stores the level of the node at E[i]. RMQ will return the index, thus we output the node at E[RMQ of L(R[x],R[y])] as LCA of Tree(x,y).



Preprocessing Complexity: L,R,E – Each is built in O(n) time, during the DFS run. Preprocessing L for RMQ is f(2n-1). 

Query Complexity: RMQ query on L is g(2n-1) and array references is O(1)
Overall Complexity: <f(2n-1)+O(n), g(2n-1)+O(1)>. 



Solution One - Dynamic Programming <O(n^2), O(1)>:










Overall Complexity




Here is the code implementation:




static private class FindRMQWithDynamicProgramming<T> implements FindRMQInterface <T> {
  private int[] A;
  private int[][] M;
  private int N;
  
  public FindRMQWithDynamicProgramming( int[] L) {
   super();
   this.A = L;
   this.N = L.length;
   this.M = new int[N][N];
   process(this.M, this.A, this.N);
  }


  /**
   * 
   * Dynamic Programming
   * 
   * M[i][j] = M[i][j - 1] if A[M[i][j - 1]] < A[j]
   * or M[i][j] = j 
   * @param M
   * @param A
   * @param N
   */
  private void process(int[][] M, int[] A, int N) {
   int i, j;
   for (i =0; i < N; i++)
    M[i][i] = i;
   
   for (i = 0; i < N; i++)
    for (j = i + 1; j < N; j++)
     if (A[M[i][j - 1]] < A[j])
      M[i][j] = M[i][j - 1];
     else
      M[i][j] = j;
  }
  
  public int rmq(int i, int j) {
   return this.M[i][j];
  }
 }




Solution Two - Sparse Table <O(n log(n), O(1)>:



Preprocess sub arrays of length of














With dynamic programming, the table M can be built in O( n log(n) ) time.

To get M[i,j] for arbitrary i and j, select two blocks that entirely cover the subrange [i...j], and let k = (int) log(j - i + 1), so that 2^k is the largest block that fits [i...j]. 














Overall Complexity



Here is the code implementation:


 static private class FindRMQWithSparseTable<T> implements FindRMQInterface <T> {
  private int[] A;
  private int[][] M;
  private int N;
  
  public FindRMQWithSparseTable( int[] L ) {
   super();
   this.A = L;
   this.N = L.length;
   this.M = new int[N][N];
   process(this.M, this.A, this.N);
  }
  
  private void process(int[][] M, int[] A, int N) {
         // initialize M for the intervals of length one
         for (int i = 0; i < N; i++)
             M[i][0] = i;

         // compute values from smaller to bigger
         for (int j = 1; 1 << j <= N; j++) {
             for (int i = 0; i + (1 << j) - 1 < N; i++) {
                 if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
                     M[i][j] = M[i][j - 1];
                 else
                     M[i][j] = M[i + (1 << (j - 1))][j - 1];
             }
         }
     }
  
  public int rmq(int i, int j) {
   int k = (int) Math.log(j - i + 1);
   if (A[M[i][k]] <= A[M[j - (1 << k) + 1][k]])
    return M[i][k];
   else
    return M[j - (1 << k) + 1][k];
  }
 }




Solution Three - <O(n), O(1)> algorithm for restricted RMQ.












































Overall Complexity: <O(n), O(1)>


Here is the code implementation:


 static private class FindRestrictedRMQWithSparseTable<T> implements FindRMQInterface <T> {
  private int[] A;
  private int[] B;
  private int[] T;
  private int [] Bl;
  private int N;
  private int blockSize;
  //private int blockNum; 
  private FindRMQWithSparseTable<T> blockRMQSparseTable = null;
  
  // construct the binary blocks 
  private int [] buildBlockArray(int[] L, int b, int n) {
   // round size of B to n blocks with size b
   int [] blocks = new int[(n*b)];
   blocks[0] = L[0];
   for (int i=1; i<L.length; i++) {
    blocks[i] = L[i] - L[i-1];
    if ( blocks[i]<0 ) blocks[i] = 0;
   }
   for (int i=L.length; i<blocks.length; i++) {
    blocks[i] = blocks[i-1] + 1;
   }
   return blocks;
  }

  public FindRestrictedRMQWithSparseTable(int [] L) {
   super();
   this.A = L;
   this.N = L.length;
   
   int b = (int) Math.ceil ( ( Math.log(N)/Math.log(2) ) / (double) 2 );
   this.blockSize = b;
   int n = (int) Math.ceil (  (double) N / (double) b ) ;
   //this.blockNum = n;

   // build the binary array
   this.B = buildBlockArray(L, b, n);

   // build the lookup table 
   this.T = buildLookupTable(this.B, b, n);

   buildMinIndexLookupTable(b, n);
   
//   System.out.println("Bl=" + Arrays.toString(Bl));
//   System.out.println("T=" + Arrays.toString(T));
   
  }

  private void buildMinIndexLookupTable(int b, int n) {
   this.Bl = new int[ n ] ;
   int [] blT = new int[ n ] ;
   for (int i=0; i<n; i++) {
    int idx = getIndex(B, i*b, b);
    int s = ( idx * ( (b) * (b+1) /2 ) );
    Bl[i] = i*b + T[s+2];
    blT[i] = A[Bl[i]];
   }
   blockRMQSparseTable = new FindRMQWithSparseTable<T> (blT);
  }

  // construct the lookup table 
  private int [] buildLookupTable(int [] blocks, int b, int n) {
   int sizeT = (int) Math.pow(2, b) * ( (b) * (b+1) /2 );
   int [] table  = new int[ sizeT ] ;
   for (int k=0; k<table.length; k++) {
    table[k]=-1;
   }
   
   for (int i=0; i<n; i++) {
    for (int j=0; j<b; j++) {
     int idx = getIndex(blocks, i*b, b);
     int [][] m = preProcess(blocks, i*b, b);
     int s = ( idx * ( (b) * (b+1) /2 ) );
     if ( table[s] < 0 ) {
      for (int k=0; k<b; k++) {
       for (int l=k; l<b; l++) {
        table[ s ] = m[k][l];
        s++;
       }
      }
     }
    }
   }
   
   return table;
  }

  
  
  private int [][] preProcess(int[] A, int start, int n) {
   int [][] matrix = new int[n][n];
   int i, j;
   for (i =0; i<n; i++)
    matrix[i][i] = i;
   
   for (i = 0; i < n; i++) {
    for (j = i + 1; j < n; j++) {
     int a = A[ start + matrix[i][j - 1]];
     int b = A[ start + j];
     if ( a < b ) {
      matrix[i][j] = matrix[i][j - 1];
     } else if ( a > b ) {
      matrix[i][j] = j;
     } else if ( a == b ) {
      matrix[i][j] = j;
     }
    }
   }
       
   return matrix;
  }

  
  private int getIndex(int[] A, int start, int len) {
     int idx = 0;
     for (int i = start; i<start+len; i++) {
      idx = idx * 2;
      idx += A[i];
     }
     return idx;
     }

  
  public int rmq(int i, int j) {
   int i1 = (int) (  (double) i / (double) this.blockSize ) ;
   int j1 = (int) Math.ceil (  (double) i / (double) this.blockSize ) ;
   int i2 = (int) (  (double) j / (double) this.blockSize ) ;
   int j2 = (int) Math.ceil (  (double) j / (double) this.blockSize ) ;
   
   int blockMinimum = -1;
   if ( (j1) < (i2) ) {
    blockMinimum = Bl[blockRMQSparseTable.rmq(j1, i2)];
   } 
   int idx1 = getIndex(B, i1*this.blockSize , this.blockSize);
   int idx2 = getIndex(B, i2*this.blockSize , this.blockSize);
   
   int s1 = ( idx1 * ( (this.blockSize) * (this.blockSize+1) /2 ) );
   int s2 = ( idx2 * ( (this.blockSize) * (this.blockSize+1) /2 ) );
   int jT1 = s1 + ( (this.blockSize) * (this.blockSize+1) /2 ) * ( i- i1*blockSize)  +  ( i2- i )  ; 
   int iT2 = s2 + ( j- j2*blockSize)  ;
   
   int firstBlockMinimum = i1 * this.blockSize + T[jT1];
   int lastBlockMinimum = i2 * this.blockSize + T[iT2];

   int[] indexes = new int[] {blockMinimum, firstBlockMinimum, lastBlockMinimum};
   int index = findMinimumIndex( indexes );
   
   return indexes[index];
  }

  
  public int findMinimumIndex(int[] idx) {
   int minIndex = Integer.MAX_VALUE;
   for (int i=0; i<idx.length; i++) {
    if (idx[i]>=0) {
     if (A[i]<minIndex) minIndex = i;
    }
   }
   return minIndex;
  }

 }
 



That is it, folks. Enjoy the journey.