[Sum][Two Pointers] 4Sum

1. Example

s=[1, 0 ,-1, 0, -2 ,2] and target sum is 0
A solution set is :
(-1,0,0,1)
(-2,-1,1,2)
(-2,0,0,2)

2. Implementation
Q1: 4 sum take 4 number to sum over and get zero value
A1: size of array less than 4 would be return
Q1: According to rule, fix one and use two pointers to get other two numbers by using two sum, how about 4 ?
A1: We fix two and get other two by twoSum
Q1: how to fix two
A1: fix the last two, or using 4Sum call 3Sum and then call 2Sum

// Time:O(n^3), Space:O(n)
public List> fourSum (int[] num, int target)
{
      List> res = new ArrayList>();
      // validate the input
      if ( num == null || num.length <4 data-blogger-escaped-3="" data-blogger-escaped-always="" data-blogger-escaped-and="" data-blogger-escaped-arrays.sort="" data-blogger-escaped-element="" data-blogger-escaped-fix="" data-blogger-escaped-from="" data-blogger-escaped-i="" data-blogger-escaped-in="" data-blogger-escaped-keep="" data-blogger-escaped-last="" data-blogger-escaped-left="" data-blogger-escaped-note:="" data-blogger-escaped-num="" data-blogger-escaped-one="" data-blogger-escaped-order="" data-blogger-escaped-res="" data-blogger-escaped-return="" data-blogger-escaped-so="" data-blogger-escaped-solution="" data-blogger-escaped-start="" data-blogger-escaped-the="" data-blogger-escaped-we=""> 2)
      for (int i = num.length -1; i > 2 ; i--)
      {
            // NOTE: when iterating, rule out the duplicate
            if ( i == num.length -1 || num[i] != num[i+1] )
            {
                   List> curRes = threeSum(num, target - num[i], i-1);
                   for (int j = 0; j < curRes.size();j++)
                   {
                        curRes.get(j).add(num[i]);
                   }
                   res.addAll(curRes);
            }
      }

     
      return res;

}


private List> threeSum (int[] nums, int target, int end)
{
       List> res = new ArrayList>();
      //@ validate the input 
      if ( nums==null || nums.length < 3 )
      {
           return res;
      }




      // NOTE: start and end
      for (int i = end; i > 1; i--)
      {    
           // avoid dupliate
           if ( i == end || num[i] != num[i+1] ) 
           {
                 // NOTE : ref = object(new keyword)
                 List> curRes = twoSum(num, target - num[i], i-1);
                 for(int j = 0; j < curRes.size();j++)
                 {
                      curRes.get(j).add(num[i]);
                 } 
                 res.addAll(curRes);
           }
      }

      
      return res;
}


private List> twoSum(int[] num, int target, int end)
{ 
      List> res = new ArrayList>();
      //@ validate the input
      if (  num==null || num.length < 2   )
      {
           return res;
      }


      int l = 0;
      int r =end;
      // NOTE: l and r two separate values
      while(  l < r )
      {
          if ( num[l] + num[r] == target)
          {
                List item = new ArrayList();
                item.add(num[l]);
                item.add(num[r]);
                res.add(item);
                l++;
                r--;
                // Avoid duplicate, should have different solution
                while ( l < r && num[l] == num[l-1] )
                {
                    l++;
                } 
                while ( l < r && num[r] == num[r+1])
                {
                    r--;
                }
          } 
          else if ( num[l] + num[r] > target)
          {
                r--;
          }
          else 
          {
                l++;
          }
      }
      
      return res;

}

3. Similar Ones
Combination Sum II
2Sum
3Sum
3Sum Closest

[Matrix] Rotate Image

1. Example
rotate an 2D matrix by 90 degrees (clockwise)

[
[1,2,3],
[4,5,6],
[7,8,9]
]
==>
[
[7,4,1],
[8,5,2],
[9,6,3]
]

[
[1,   2,   3,  4]
[5,   6,   7,  8]
[9,  10,11,12]
[13,14,15,16]
]

2. Implementation
Complexity:Time: O(m*n) Space:O(1) in-place
keep 1
1->7[2,0]
7->9[,2,2]
9->3[0,2]
3->  1[0,0]

keep2
2->4[1,0]
4->8[2,1]
8->6[1,2]
6->  2 [0,1]
Q1: how many times?
A1: for n/2 layer, we do n/2 number of times rotate for each layer, they follow the same rule
Q1: how to iterate?
A1: we iterate to the element before boundary element (not included)
FOLLOW UP: What if a matrix nxm matrix, which means not square matrix?

// Time:O(m*n), Space:O(1)
public void rotate (int[][] matrix)
{



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




     int layer = n >>1;
     for (int row = 0 ; row < layer; row++)
     {
          // NOTE:  col start from layer
          for (int col = row ; col < matrix[0].length-1;col++ )
          {     
                // NOTE: the first element for each layer (row index)
                // 4 value (4 corner) top<-left data-blogger-escaped--="" data-blogger-escaped--col="" data-blogger-escaped-1="" data-blogger-escaped-bottom="" data-blogger-escaped-col="" data-blogger-escaped-int="" data-blogger-escaped-matrix.legnth-1="" data-blogger-escaped-matrix="" data-blogger-escaped-right="" data-blogger-escaped-row="" data-blogger-escaped-temp="matrix[row][col];" data-blogger-escaped-top=""> 7 4 1, col has sth to do with row, cur ROW== next COL
                matrix[(matrix.length-1) - col][row] = matrix[(matrix.length-1)-row][(matrix.length-1) - col];//  e.g., 7 8 9 (bottom)-> 7 8 9(left), row has sth to do with col, cur ROW==next COL
                matrix[(matrix.length-1)-row][(matrix.length-1) - col] = matrix[col][(matrix.length-1)-row];// e.g., 3,6,9 => 9,6,3, col ~ row, cur ROW==next COL
                matrix[col][(matrix.length-1)-row] = temp;// 1,2,3(top)->1,2,3(right)
          }
     }



}

// 1234 // 5678 //=> // 51 // 62 // 73 // 84

public int[][] rotate(int[][] matrix)
{
    // NOTE: there is no way to do in-place, so create a new matrix
    int[][] newmatrix = new int[matrix[0].length][mtrix.length];
    // validate the input
    if ( matrix == null || matrix.length ==0 || martix[0].length == 0)
         return newmatrix;

   
    
    for (int i = 0; i < matrix.length; i++)
        for (int j = 0 ; j < matrix[0].length; j++)
              newmarix[j][(matrix.length-1) - i] = matrix[i][j];
    return newmatrix;
}

3. Similar Ones
Spiral Matrix I
Spiral Matrix II
http://www.careercup.com/question?id=5667482614366208

[Search][BinarySearch][Matrix] Search a 2D Matrix

1. Example
each row is sorted
the first integer of each row is greater than the last integer of previous row
[
[1,3,5,7],
[10,11,16,20],
[23,30,34,50]
]

Given target = 3, return true


2. Implementation
Complexity:O(log(m)+log(n)), Space:O(1)
Binary Search
First locate which row, BS to find the target is between two value and choose previous one's row
=> Search Insert Position, its goal is to find two indexes which are two bound for the target value

public boolean searchMatrix(int[][] matrix, int target)
{



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





     int l=0;
     int r= matrix.length-1;
     while(l<=r) 
     {
          int m = (1+r)>>1;
          if ( matrix[m][0] == target)
          {
              return true;
          }
          else if ( matrix[m][0] > target )
          {
              r = m-1;
          }
          else 
          {
              l = m+1;
          }
     }
 




     // NOTE: if target larger than first integer in the last row, l=m+1 out of bound, so we take r value
     // NOTE: if target less than second integer in the second row, 
l= m+1 point to second row, so we take r value
     if (  r < 0 )
     {
         return false;// target is less than the first integer of the first row
     }
     int row = r;
     int l = 0;
     int r = matrix[0].length -1;
     while (l<=r)
     {
         int m = (l+r)>>1;
         if ( matrix[row][m] == target)
         { 
             return true;
         }
         else if ( matrix[row][m] > target )
         {
             r = m-1;   
         }
         else 
         {
             l = m+1;
         }
     }




     return false;




}

3. Similar Ones
 Search for a Range
 Search Insert Position
 Search in Rotated Sorted Array I and II

 Set Matrix Zeroes
 Spiral Matrix I and II
 Rotate Image

[Search][Binary Search] Search for a range

1. Example
idx 0 1 2 3 4  5
s= [5,7,7,8,8,10] and target value is 8
return [3,4]


2. Implementation
Complexity Time:O(log(n)) Space:O(1)
BS to search for a target value
Q1: how to know it is left bound or right bound
A1: since it is sorted, we can iterating right or left until non-target value is hit. More Specifically,

For the left bound, we use this formula
num[m] < target , l = m+1
num[m] >= target, r = m-1
When value equal happen, we keep decreasing the right bound until nums[m] < target happen.
When num[m] < target happen, l == r and m = (r+l)>>1 = l = r, so we take l = m+1 and while loop stop since l > r(m+1 > m) and l is our left bound

For the right bound, we use  the formula
num[m] > target, r = m-1
num[m] <= target, l=m+1
When value equal happen, we keep increasing the left bound until num[m] > target happen.
When num[m] > target happen, l==r and m = (r+l)>>1 = l=r, so we take r = m-1 and while loop stop
since l > r(m > m-1) and r is our right bound

Note: left bound and right bound. manipulate BS
if ( nums[m] >= target ) { r = m-1; } else { l_leftbound =m+1; }

if ( nums[m] <= target ) { l = m+1; } else { r_rightbound= m-1; }

// Time:O(log(n)) ,Space:O(1)
public int[] searchRange (int[] nums, int target)
{


     int[] res = new int[2];
     res[0] =-1;
     res[1] =-1;
     // validate the input 
     if ( nums == null || nums.length == 0)
     {
         return res;
     }




     int l_leftbound = 0;
     int r = nums.length -1;
     //int foundIndex = -1;
     while( l <= r )
     { 
          int m = (l+r) >>1;
          //if ( nums[m] == target )
          //{
          //    foundIndex = m;
          //}
          //else if (  nums[m] > target )
          if (  nums[m] >= target ) 
          {
              r = m-1;
          } 
          else 
          {
              l_leftbound =m+1;
          }
     }
     

     

     int l = 0; 
     int r_rightbound = nums.length -1;
     while (  l<=r )
     {
         int m = (1+r) >> 1;
         if ( nums[m] <= target )
         {   
            l = m+1;
         }
         else 
         { 
           r_rightbound = m-1;
         }
     }

  

    
     if (l_leftbound <= r_rightbound )
     {
          res[0] = l_leftbound;
          res[1] = r_rightbound;
     }
     return res;


}

3. Similar Ones
(M)  Search Insert Position

[Search][Rotate][Binary search] Search in Rotated Sorted Array ||

1. Example
Duplicate is allowed in Search in Rotated Sorted Array I duplicate is not allowed.
s=[4,5,6,7,0,1,2] and target is 7
Return true


2. Implementation
Thought1: linear O(n)

Thought2: Binary Search O(log(n))
but rotated, search the part is sorted
Q1: how to know which part is sorted ? rotated pivot?
A1: middle element compare to start and end
Q1: rotated?
A1: big part close to start and small part close to end, end value < start value
Q1: diff btw bs and roated?
A1: num[l] vs num[m] , care the part is sorted
//NOTE:

if (nums[l] < nums[m])
else if (nums[l] > nums[m]){
}
else { // duplicate l++; }

// Time:O(n), Space:O()
// Input:
//[1], 1
//Output:
//false
// Input:
//[1,3], 3
//Output:
//false
//Expected:
//true
//Input:
//[1,3,5], 1
//Output:
//false
//Expected:
///true
// Input:
//[3,5,1], 1
//Output:
//false
//Expected:
//true
// Input:
//[1,3], 3
//Output:
//false
//Expected:
//true
public boolean search(int[] nums, int target)
{

      // validate the input
      if ( nums == null || nums.length = 0)
      {
        return false;
      }
      



      int l = 0; 
      int r = nums.length-1;
      // NOTE: [1],1, so consider equal. The other reason is Big chance in the left-most or right-most
      while (l <= r)
      {
          int m = l + (r-l)>>1;
          if ( nums[m] == target )
          {
               return true;
          }




           


 if (nums[l] < nums[m])
 {
 // left part in order and target in range
 if ( target >= num[l] && target < nums[m] )
 {
 r = m-1
 }
 else 
 {
 l = m+1;
 }
 }
 else if ( nums[l] > nums[m] )
 {
 // right part in order and target among them
 if ( target > num[m] && target <= nums[r] )
 {
 l = m+1;
 }
 else 
 {
 r = m-1;
 }
 }
 else 
 { 
 // duplicate
 l++;
 }
 /*
 else if ( nums[m] > target )
 { 
 // NOTE: normally we just search left part means r = m-1 
 // case 4567 012 search 0 go right side 
 if ( nums[l] < nums[m] && nums[l] >= target ) 
 {
 r = m-1;
 }
 else 
 {
 l = m+1;
 }
 }
 else 
 { // case: 531 search 1/ go left side
 if ( nums[m] < nums[r] && nums[r] >= target)
 {
 l = m+1;
 }
 else 
 {
 r = m-1;
 }
 }
 */

}
    return false;
}

idx 0123   456
  s=4567   012
 
search 0
m = 3 s[m] =7 > 0
      s[m]=7 > s[0]=4

3. Similar Ones
(H) Search in Rotated Sorted Array
       Search insert position
       Search for a Range
       Search a 2D matrix
       Find minimum in Rotated Sorted Array I
       Find minimum in Rotated Sorted Array II

[Path][DP] Unique Path

1. Example

[
  [start,a,b],
  [c,d,e],
  [f,g,end]
]

Unique path:
[start, a,b,e,end]
[start,c,f,g,end]
[start,q,d,g,end]

2. Implementation
Thought 1 recursive
Q1: how to start ?
A1: start from right or down
Q1: how to make sure unique?
A1: since at every point we only have option to move right or down, so there is no chance to move back to already explored point
Q1: hot to stop?
A1: when you hit the right-bottom corner the point (m-1, n-1), we stop

Thought 2 permutation and combination mathematics
top-left to bottom-right needs m+n steps to travel
Within m+n steps, there must be m step belong to down move and n steps belong to right move.
Take down move or right move first, Use Mathematics, given m+n steps, take m belong to down,
assume m = 3 and n = 7, we can take step 1, 4, 6 as down and  the rest are right

Cn r = n! / (n-r)! *r!
Q1: how to calculate r! ?
A1: r1 = 1x2x3x..r, use factorial
Q1: any fast way to calculate C n r ?
A1: C nr = (r+1)x(r+2)..xn / 1x2x3x..(n-r)

// Time:O(min(m,n)), Space:O(1)
public int uniquePaths(int m, int n)
{

    //Cnr = nx..x(n-r) / 1x2x..xr
    double num = 1;
    double denom = 1;


    // NOTE: already at (0,0) choose m-1 and n-1
    big = (m>n)?m-1:n-1;
    small = (m>n)?n-1:m-1;

    for (int i =1 ; i <= small;i++)
    {
        denom *=i;
        num*= (small + big -1) - i;
    }
    return (int) num/denom;
}

// Time:O(2^n), Space:O(n) Time Exceed Limit
public int uniquePaths(int m, int n)
{
     // validate the input 
     if (m == 0 || n == 0)
     {
         return 0;  
     }
     int[] res = new int[2];
     helper(0,0, m,n,res);
     return res[0];
}

//private void helper (int i, int j,int m, int n, int[] res)
private int helper (int i, int j,int m, int n)

{
     // base case to stop
     if (i == m-1 && j == n-1)
     {
          //res[0]++;
          //return;
           return 1;
     }
     //if (i==m || n = n)
     if (i > m-1 || j > n-1) 
     {
          //return;
          return 0;
     }
     // recursive call (any check condition)
     //if ( i < m-1)
     //  helper(i+1,j,m,n,res);
     //if ( j < n-1)
     //  helper(i, j+1,m,n,res);

     return helper(i+1,j,m,n) + helper(i,j+1,m,n);
}

helper(0,0,..)
  helper(1,0,..)
     helper(2,0,..)
      ..
        helper(m-1,0,..)
        retrun;
        helper(m-1,1,..)
           helper(m-1,2,..)
             ..
               helper(m-1, n-1,..)
               count++
               return
             helper(m-1, n-2,..)
WHEN BACKTRACKING, no way to stop it 
assume m =4 n =4
helper(0,0,..)
   helper(1,0)                                        +        helper(0,1,.)
   helper(2,0)                + helper(1,1)                    h(1,1)+              h(0,2)
   h(3,0)+       h(2,1)         h(2,1)+          h(1,2)        h(2,1)+h(1,2)        h(1,2)+h(0,3)
   h(3,1)+h(2,2) h(3,1)+h(2,2)  h(2,2)+h(1,3)    h(2,2)+h(1,3) 
                 h(3,2)+h(2,3)  
                 h(4,2)+h(3,3)  h(3,3)+h(2,4)
       
 

3. Similar Ones
(M) Unique Path II
(M) Minimum Path Sum
(H)  Dungeon Game
        Path Sum
        Path SumII
        Binary Tree Maximum Path Sum

[Search][Binary search] Search Insert Position

1. Example

[1,3,5,6], insert 5 at index 2
[1,3,5,6], insert 2 at index 1
[1,3,5,6], insert 7 at index 4
[1,3,5,6], insert 0 at index 0


2. Implementation
Thought 1: find out two adjacent number which are most close left bound and right bound for the target value.
Q1: how to find these two number
A1: try to find a number first, we can redefine this question like find the target value
Q1: any best way to find a target value?
A1: Binary search  will do the job just right
Q1: BS criterion?
A1: sorted array
Last executed input: [1], 0 if r != m-1 Last executed input: [1], 2 if l != m+1
NOTE: 
while ( l <= r )
 else if ( nums[m] > target )
 {
 r = m-1;
 }
 else
 {
 l=m+1;
 }

// Time :O(log(n)), Space:O(1)
public int searchInsert(int[] nums , int target)
{


     // valid the input
     if (nums == null || nums.length == 0)
     {
         return 0; // first element
     }




     int l = 0;
     int r = nums.length-1;
     // NOTE: when l increment to length-1 (==r) and the value there still less than target, left increment to length and (1 > r) return 
     // NOTE: when r change to 0 (==l) and the value there still larger than target, r change to -1(l>r) and return left
     while (  l <= r  )
     {
           int m = l + (r-l)>>1;
           if ( nums[m] == target )
           {
                return m;
           }
           else if ( nums[m] > target )
           {
                // NOTE:  for the case [1], 0, if r= m instead of m-1 then m always 0 and l always 0, infinite loop
                //r = m;
                r = m-1;
           }
           else 
           {
                l=m+1;
           }
     }
     return l;



}

3. Similar Ones
(M) Search for a range
       Search a 2D matrix