Wednesday, September 2, 2015

[Sort][Interval] Insert Interval

1. Example

s= [ [1,3], [6,9] ]
insert [2,5]
=>s= [  [1,5], [6,9]  ]

s= [  [1,2], [3,5], [6,7], [8,10], [12,16]  ]
insert [4,9]
=> s= [ [1,2], [3,10], [12,16]  ]

[4,9] overlaps [3,5], [6,7], [8,10]



2. Implementation
Q1: can we reuse merge interval?
A1: insert interval first and do the merge
Q1: how to insert ?
A1: check start if start equal , check end
// Add those less than newInterval.start
 int i = 0; while ( i < intervals.size() && intervals.get(i).end < newInterval.start) { res.add(intervals.get(i)); i++; } 
// Add newInterval
 if ( i < interval.size()) newInterval.start = Math.min(newInterval.start, intervals.get(i).start); res.add(newInterval); 
// Add the rest less than interval.end 
while(i < intervals.size() && intervals.get(i).start <= newInterval.end) { newInterval.end = Math.max(newInterval.end, intervals.get(i).end); i++; }

// Time:O(n), Space:O(n) List
public List insert(List intervals, Interval newInterval)
{
          
       

       
       
        List res = new ArrayList();




        // validate the input
        if ( intervals == null || intervals.size() ==0 )
        {
               res.add(newInterval);
               return res;
        }     
        if (newInterval == null )
        {
               return intervals;
        }





        // Insert newInterval
        List resTemp = new ArrayList();
        resTemp.add(newInterval);
        for (int i =0 ; i < intervals.size(); i++ )
        {
              if (resTemp.get(resTemp.size()-1).start > intervals.get(i).start)
              {
                    int pos=resTemp.size()-1;
                    Interval temp = resTemp.get(pos);
                    resTemp.set(pos, intervals.get(i));
                    resTemp.add(temp);
              }        
              else 
                 resTemp.add(intervals.get(i));
        }   





        // Merge Interval
        res.add(resTemp.get(0));
        for (int i =1; i < resTemp.size(); i++)
        {
              if(   res.get(res.size()-1).end >= resTemp.get(i).start  )  
                    res.get(res.size()-1).end = Math.max( res.get(res.size()-1).end, resTemp.get(i).end  );
              else
                    res.add(resTemp.get(i));
        }



       
        return res;       
       
       


}
public List insert (List intervals, Interval newInterval)
{




      List res = new ArrayList();




      if (intervals.size() == 0)
      {
           res.add(newInterval);
           return;
      }




      // Add those less than newInterval.start
      int i = 0;
      while ( i < intervals.size() && intervals.get(i).end < newInterval.start)
      {
         res.add(intervals.get(i));
         i++;
      }





      // Add newInterval
      if ( i < interval.size())
           newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
      res.add(newInterval);





      // Add the rest less than interval.end
      while(i < intervals.size() && intervals.get(i).start <= newInterval.end)
      {
           newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
           i++;
      }




      // Add the rest 
      while ( i < intervals.size())
      {
             res.add(intervals.get(i));
             i++;
      }
 



      return res;
 
           
}
3. Similar ones
Merge Interval
Sort Color
Sort List

[Sort] Merge Interval

1. Example
Change end in-place
Given [1,3][2,6][8,10][15,18]
return [1,6],[8,10],[15,18]

2 .Implementation
Q1: sort ?
A1: sort the intervals int[][2] X, List<Interval>
collection.sort(List, new IntervalComparator() );
public int IntervalComparator(Itnerval intervalA, Interval intervalB) implements comparator
{
       if (intervalA.start - intervalB.start  < 0 )
            return -1;
       else
            return 1;
};
Q1: after sorting , how to do the merge ? Detect Merge?
A1: previous's end is larger than next's start, create a new Interval to merge with start from previous's start and end from next's end. list Add and Remove
Q1: Comparator Interface Class? Comparable class  Interface?
A1: interface using implement keyword, class using extend keyword
Comparator<T> comp = new Comparator<T>()
{
         @Override
         public int compare(T t1, T t2)
        {
                return t1.data - t2.data;
        }
};
Collections.sort(  DS, comparator)??
// NOTE:
if (res.get(res.size()-1).end >= intervals.get(i).start ) 

//Interval item = new Interval(intervals.get(i).start, intervals.get(i+1).end); 
//res.add(item); 
//i++; 
res.get(res.size()-1).end = Math.max(res.get(res.size()-1).end ,intervals.get(i).end);
 }
/*
 Time:O(nlogn+n), Space:O(1)
 
 
 Input:
[[1,3]]
Output:
[]
Expected:
[[1,3]]
 
 Input:
[[1,4],[5,6]]
Output:
[[1,4]]
Expected:
[[1,4],[5,6]]
 
 
 http://codeganker.blogspot.com/2014/03/merge-intervals-leetcode.html
 */
public class Solution {
    public List merge(List intervals) {
                List res = new ArrayList();        





         // validate the input
         if (intervals == null || intervals.size() == 0 )
             return res;






         // Comparator is a class
         Comparator comp = new Comparator()
         {
             @Override
             public int compare(Interval a, Interval b)
             {
                 // NOTE: start are the same
                 if (a.start == b.start)
                     return a.end - b.end; // means a.end < b.end => return -1
                 return a.start - b.start;        
             }
         };








         
         //Collections.sort(intervals, new IntervalComparator());
         Collections.sort(intervals, comp);








         //for ( int i =0 ; i < intervals.size() -1 ;i++)
         res.add(intervals.get(0));
         for (int i = 1; i < intervals.size(); i++)
         {
                //if ( intervals.get(i).end >= intervals.get(i+1).start )
                if (res.get(res.size()-1).end >= intervals.get(i).start )
                {
                    //Interval item = new Interval(intervals.get(i).start, intervals.get(i+1).end);
                    //res.add(item);
                    //i++;
                    res.get(res.size()-1).end = Math.max(res.get(res.size()-1).end ,intervals.get(i).end);
                }
                else 
                {
                    res.add(intervals.get(i));
                }
         }





        
         return res; 




    }
}

//public int IntervalComparator(Interval a, Interval b) implements //Comparator
//{
//    if (a.start < b.start)
//         return -1;
//    else 
//         return 1;
//}

3. Similar ones
[sort] Sort Color
[sort] Sort List

[Two Poitners] Container With Most Water

1. Example
Two Pointer , width need two index
s= [3,4,5,6,7,0,3]

|                 7
|              6  |
|           5 ~  |
|         4 ~    |
|      3   ~     |     3
|      |    ~     | 1
| __ |__~__ | ____


2. Implementation
Q1: for a ladder shape ?  X ,  Most Water ?
A1: calculate the area of that shape, the one with largest area contain most water X
Water can not be tilt, so inly calculate rectangular shape

Q1: any two vertical lines can form a ladder shape ? how to pair?
A1: nested for loop O(n^2) + area calculation. pair vertical line with any vertical line before it
e.g., line 3 ,line2 and  line3 ,line1 and line3 ,line0
X Q1: Under increasing array, more index, more area. If not increasing ?
X A1: stop at the not increasing one
X Q1: DP[i] = max(max)
Q1: largest height with largest width?
A1: maintain a width right-left, try to find the largest height.
Q1:  3 5
        0 4  =>4w*3 = 12
        4 5
        1 4  => 3w*4h= 12
        5 5
        2 4 = > 2w*5h = 10
left move to right if left is smaller , looking for larger height,even width just decrease 1
right move to left if right is smaller, looking for larger height, even width just decrease 1
// time:O(n), Space:O(1)
public int maxArea (int[] height)
{

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



     //int max = 0;
     //for ()
     //{
     //
     //}

      

     int l = 0;
     int r = height.length -1;
     int max = 0;
     while( l < r )
     {
          
          max = Math.max( max, Math.min(height[l],height[r])* (r-l));
           
          if (  height[l] < height[r] )
          {
              l++;  
          }
          else 
          {
              r--;
          }
     }


     return max;

}
3. Similar Ones
(H) Trapping Rain Water
Maximum Rectangle
Maximum histogram

[DFS] Construct Binary Tree from Preorder and Inorder Traversal

1. Example

in-order sequence: 4 2 5 (1) 6 7 3 8
pre-order sequence: (1) 2 4 5 3 7 6 8
The constructed tree is

                       1
                   /        \
                  2         3
               /    \       /   \
             4      5    7    8
                          /
                         6

2. Implementation
Q1: inorder ?
A1: root in the middle
Q1: preorder?
A1: root in the first element (arr, left , right), root.left ,and root.right

//NOTE: // validate the input
 if (preorder == null || inorder == null)
 return null;


// Time:O(n), Space:O(n)
public TreeNode buildTree(int[] preorder, int[] inorder)
{

     //NOTE:
     // validate the input
     if (preorder == null || inorder == null)
       return null;

     

     HashMap map = new HashMap();
     for (int i = 0 ; i < inorder.length ; i++)
          map.add(inorder[i], i);




     return buildTree(preorder, 0, preorder.length-1, inorder ,0 , inorder.length -1, map);




}

public TreeNode buildTree(int[] preorder, int preL, int preR, int[] inorder, int inL, int inR, HashMap map)
{
         
        // Base Case, only one element any increment decrement would out of boundary
        if (preL > preR || inL > inR)
           return null;

         
         TreeNode root = new TreeNode(preorder[preL]);
         int index = map.containsKey(root.val);
         root.left = buildTree(preorder,preL+1, preL+(index-inL), inorder, inL, index-1,map);
         root.right = buildTree(preorder,preR-(inR-index-1) ,preR,inorder, index+1, inR, map);

         return root;
}

3. Similar ones
(M) Construct Binary Tree from Inorder and Postorder Traversal

[Sort][Two Pointers] Sort Color

1. Example
n obejcts colored red(0), white(1), or blue(2)
sort them so that the objects of the same color are adjacent.

s=[0,1,2,0,1,2,0,0,1,1,2,2]
sorted s = [0,0,0,0,1,1,1,1,2,2,2,2]

Follw Up: n Colors?
2. Implementation
Q1: merge sort, quick sort ?
A1: it takes O(n log(n))
Q1: only 3 elements, using counting sort = > O(n)
A1: count[0] = .. ,count[1] = .., count[2] =..
Q1: how to do it in-place?
A1: replace existing elements
Q1: [0,1,2,0,1,2,0,0,1,1,2,2]
[0] = 4
[1] =4
[2] =4
0, 0,0,0, 1,1,1,1,2,2,2,2
    2 1 0  3 2 1 0 3 2 1 0
// NOTE:
// consumes 0 first and then 1 and then..n

// NOTE:
// KEEP the last colored element and change the other two kind
if (nums[i] == 0) { 
nums[i] =2; 
nums[idx1++] = 1; // the reason idx1++ is because when insert 0 at idx0, idx1 would be push next. idx1 = idx0 + # of 1 
nums[idx0++] = 0; // overwrite 1 
else if ( nums[i] == 1) { 
nums[i]=2; 
nums[idx1++] =1;
 }

// Time:O(n), SpacE:O(k) array with size of k
public void sortColors(int[] nums)
{




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


      int[] count = new int[3];
      for (int i = 0 ; i < nums.length; i++)
      {
            count[nums[i]]++;
      }





      for (int i = 0 ; i < nums.length;i++)
      {
            if (nums[i] == 2)
            {
                  if ( count[0] != 0)
                  {
                      nums[i] = 0;
                      count[0]--;
                  } 
                  else if ( count[1] != 0)
                  {
                      nums[i] =1;
                      count[1]--;
                  }
                  else if (count[2] != 0)
                      count[2]--;
            } 
            else if ( nums[i] == 1)
            {
                  if (  count[0] != 0 )
                  {
                      nums[i] = 0;
                      count[0]--;
                  }
                  else if ( count[1] != 0)
                  {
                      count[1]--;
                  }
                  else if ( count[2] != 0)
                  {
                      nums[i] =2;
                      count[2]--;
                  }
            }
            else 
            {
                  if (count[0] != 0)
                     count[0]--;
                  else if (count[1] != 0)
                  {
                     nums[i] = 1;
                     count[1]--;
                  }
                  else if ( count[2] != 0)
                  {
                     nums[i] = 2;
                     count[2]--;
                  }
            }
      
      }




}
[0,1,2,0,1,2,0,0,1,1,2,2]

                 2 2 2
 3 2 1 0 3 2 1 0 3 2 
// Time :O(n), Sapce:O(k)
if (nums== null || nums.length == 0)
    return;



int idx0 = 0; // array index for element 0
int idx1 = 0; // array index for element 1




for ( int i = 0 ; i < nums.legnth;i++)
{
     
     // KEEP the last colored element and change the other two kind
     // move 0 forward according to current array index for Zero
     if (nums[i] == 0)
     {
          nums[i] =2;
          nums[idx1++] = 1; // the reason idx1++ is because when insert 0 at idx0, idx1 would be push next. idx1 = idx0 + # of 1
          nums[idx0++] = 0; // overwrite 1
     }
     else if ( nums[i] == 1)
     {
          nums[i]=2;
          nums[idx1++] =1;
     }

}
3. Similar Ones
(M) Sort List (Divide and Conquer) (Merge Sort)

[Binary Search] Find Minimum in Rotated Sorted Array

1. Example
Find the minimum element
No Duplicate exist in the array
s= [0 1 2 4 5 6 7]
s' = [4 5 6 7 0 1 2]

2. Implementation
Q1: Find minimum ?
A1: Binary search can do the job, why rotated sorted array?
Q1:
A1:
s=[4  5  6  7  0  1  2]
     0  1  2  3  4  5  6
l=0, r=6,m = (0+6)/2 = 3  
    7 >4 but 4 > 2   [l] < [m] && [l]  <  [r]
   l=m+1 = 4                r = m-1;
                             else
                                    l = m+1;
l=4, r=6, m =5
    5 > 0 but 0  < 2  [l] < [m] && [l] < [r]
  r = m-1=4                 r = m-1;
l=4, r=4                 else
                                  l=m+1;
                              [l] == [m]
  l ==r , return l

   
  r= m-1




Input:[2,1]
Output:2
Expected:1




Runtime Error Message:Line 113: java.lang.ArrayIndexOutOfBoundsException: -1
Last executed input:[1]
// NOTE:
int min = nums[0];

while ( l < r-1 ) 

else ( nums[l] > nums[m] ) 
 { 
 min = Math.min(nums[m], min); 
 r= m-1; 
 }

min = Math.min(nums[r], min); 
 min = Math.min(nums[l], min);



// Time:O(log(n)), Space:O(1)
public int findMin(int[] nums)
{
      
      
     // validate the input
     if ( nums==null || nums.length == 0 )
          return -1;


   

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


   

     int l = 0;
     int r = nums.length -1;


     int min = nums[0];



     while ( l < r-1 )
     {
          int m = (l+r) >>1;
          if ( nums[l] < nums[m] )
          {
               min = Math.min( nums[l], min);// for sorted side, we know leftmost is smallest and proceed comparison, and then search the other side
               l= m+1; 
          }
          else (  nums[l] > nums[m] ) 
          {
               min  = Math.min(nums[m], min);
               r= m-1;
          }
          else 
               l++;
     }



     min = Math.min(nums[r], min);
     min = Math.min(nums[l], min);
     return min;



}
}
public int findMin(int[] nums)
{
    return findMin(nums, 0, nums.legnth-1);
}
public int findMin(int[] nums, int left, int right)
{



    if (left == right)
       return nums[left];
    if ((right-left) ==1)
       return Math.min(nums[left], nums[right]);





    int m = left +(right-left)>>1;




    // not rotated
    if ( nums[right] > nums[left])
        return nums[left];
    else if (  nums[m] > nums[left] )
        return findMin(nums,m, right);
    else
        // [3,1,2] => [1]
        return findMin(nums, left, m);



}
// Time:O(log(n))
// *** The minimum element is the only element whose previous element is greater than it
public int findMin (int[] nums, int low, int high)
{


     // this condition is needed to handle the case when array is not rotated at all
     if (  high < low )
        return nums[0];
     // If there is only one element left
     if ( high == low)
        return nums[low];

     


     int mid = low+(hight-low)>>1;



     if ( mid < high && nums[mid+1] < nums[mid] )
        return nums[mid+1];

     if ( mid > low && nums[mid]  < nums[mid-1] )
        return nums[mid];





     if ( nums[high] > nums[mid] )
        return findMin(nums, low, mid-1);
     else 
        return findMin(nums, mid+1, high);
} 
3. Similar Ones
[Binary Search] Find Peak Element
[Binary Search] Search Insert Position
[Binary Search] Search for a Range
[Binary Search] Search for a 2D Matrix
[Binary Search] Search in Rotated Sorted Array


Tuesday, September 1, 2015

[Binary Search] Find Peak Element

1. Example
peak element in an array = > Binary Search
A peak element is an element that is greater than its neighbors
Given an input array where num[i] != num[i+1], find a peak element and return its index.
Imagine num[-1] = num[n] = -INF

s= [1,2,3,1]
Return index number 2 where 3 is a peak element


2. Implementation
Q1: peak element ? global or local?
A1: greater than its neighbors , local maximum
Q1: multiple peaks ?
A1: return any of them
Q1: how to find peak?
A1: [0] > [1] or not, [n-1] > [n-1] or not
i =1~ n-2
 [i] > [i-1] && [i] > [i+1]
[1,2,3,1]
i=0   1 > 2 X
i=1   2 >1 , 2 <3 X
i=2  3>2, 3 >1 O
i=3   1 > 3X


// Time:O(log(n))
public int findPeakElement(int[] nums)
{
      if (nums.length == 0|| nums == null)
         return -1;
 
     
      int l = 0; 
      int r = nums.length -1;
      while (l <= r)
      {
           if (l == r)
               return l;
           int m = (l+r) >>1;
           if (  nums[m] > nums[m+1] )   //3 >2
               r = m;
           else // 1 < 3
               l = m+1;
      }



      return l;


}
// Time: O(n) 
public int findPeakElement(int[] nums)
{


      // validate the input
      if (  nums == null || nums.length == 0)
         return -1;

      


      //for (int i = 0; i < nums.length -1; i++)
      //{
      //     if( i==0 && nums[i] > nums[i+1])
      //          return i;
      //     else if (i == num.length-1 && nums[i] > nums[i-1])
      //          return i;
      //     else if (i>0 && i < nums.length-1 && nums[i] > nums[i-1] && nums[i] > nums[i+1])
      //          return i;
      //}

       

      // NOTE: nums[0] as first comparison to save a iterating index and csn separate from index 1 to len-2
      int max = num[0];
      int index = 0;
      for (int i = 1; i < num.length -1; i++)
      {

            int cur = nums[i];
            int prev= nums[i-1];
            int next = nums[i+1];
            if ( cur > prev && cur > next && cur > max)
            {
                   max = cur;
                   index = i;
            }
      }




      if (max < nums[nums.length -1])
            return nums.length -1;

      

      return index;
      
}
3. Similar ones
[Binary Search] Search for a Range
[Binary Search] Search in Rotated Sorted Array I /II
[Binary Search] Search a 2D Matrix
[Binary Search] Search Insert Position
Find ... Element

[Matrix] Spiral Matrix II

1. Example
Spiral Matrix II "Fill in"
Filled a square matrix with elements from 1 to n^2 in spiral order
Given  n =3,
you should return the following matrix:
[
[1,2,3],
[8,9,4],
[7,6,5]
]

2. Implementation
Q1: using the technique used in Spiral order ?
A1: just using a count as a value to fill in the matrix,
top->             matrix[levelNum][j],   j >= levelNum  , j  < matrix[0].length -levelNum -1
right->           matrix[i][matrix[0].length-1-levelNum],  i>= levelNum, i < matrix.length-1-levelNum
bottom->       matrix[matri.length-1-levelNum][j], j < = matrix[0].length-1-levelNum ,  j > levelNum
left     - >       matrix[i][levelNum],   i <= matrix.length -1 -levelNum , i  > levelNum
Q1: what about rotate image ?
A1:

for (int levelNum= 0 , levelNum < size/2; levelNum++)
for (int j = levelNum; j< matrix.length-1-levelNum; j++)
int temp = matrix[levelNum][j];
matrix[levelNum][j] = matrix[matrix.length-1-j][levelNum];//topleft<-bottomleft
matrix[matrix.length-1-j][levelNum]= matrix[matrix.length-1-levelNum][matrix.length-1-j]// bottomleft<-bottomright
matrix[matrix.length-1-levelNum][matric.length-1-j] = matrix[j][matrix.length-1-levelNum]// botomright<-topright
matrix[j][matrix.length-1-levelNum] =temp;

// Time:O(nxn), Space:O(1)
public int[][] generateMatrix(int n)
{


        
      int[][] res = new int[n][n];




      // validate the input
      if ( n < 0)
           return matrix;




      int k =1;
      for (int levelNum = 0; levelNum < n/2; levelNum++)
      { 
             // top
             for (int j = levelNum ; j < n - 1 -levelNum; j++)
                   res[levelNum][j] = k++;
             // right
             for (int i = levelNum; i < n-1-levelNum; i++)
                   res[i][n-1-levelNum] = k++;
             // bottom
             for (int j = n-1-levelNum; j > levelNum;j--)
                   res[n-1-levelNum][j]= k++;
             // left
             for (int i= n-1 -levelNum; i > levelNum; i--)
                   res[i][levelNum] = k++;
      } 


      
      // Fro Square Matrix, odd length only got one element left inner most layer
      if (n%2 ==1)
          res[n/2][n/2] = k;




      return res;




}

int [][] res = new int[n][n];
int k=1;
int top = 0, bottom = n-1, left = 0, right = n-1;








while (left < right && top < bottom)
{




     for (int j = left; j < right;j++)
           res[top][j] = k++;
     for (int i =top; i < bottom; i++)
           res[i][right] = k++;
     for (int j = right ; j > left; j--)
           res[bottom][j] = k++;
     for (int i = bottom; i > top)
          res[i][left] = k++;



left++;
right--;
top++;
bottom--;

}




      if (n%2 ==1)
          res[n/2][n/2] = k;




return res;
3. Similar ones
(M) Spiral Matrix
Rotate Image

[Matrix] Spiral Matrix

1. Example
Spiral Matrix I "print out"
Return all elements of the matrix in spiral order
matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
]
You should return [1,2,3,6,9,8,7,4,5]

2. Implementation
Q1: spiral order?
A1: top->right->bottom->left and layer
Q1: layer , layer = max(m,n)
3X5 matrix, layer =5/2 =2
12345
67890
32456
layer 1: 123450654236
layer 2: 789 start from layer 2, top->right
5X3 matrix, layer =5/2 =2
123
456
789
064
235
layer 1: 123694532074
layer2: 586 start from layer 2
Q1: how to define 123 69 or 12 36 98
A1: I mean the start position of each direction, we move to len -2 and next direction start from index
Q1: layer 1 [0,layer1],[0,1< len-1],    [0,2],[1< len-1,2]   [2,len-1][2,len-2],    [len-1][0],[len-2][0]
A1: so layer 2 [layer1, layer1]

//[[1,2,3,4,5,6,7,8,9,10]] 1x10 matrix, layer 10/2 =5??? or 1ayer 1/2 =0 

 //int size = Math.max(matrix.length, matrix[0].length);
 int size = Math.min( matrix.length, matrix[0].length );

// NOTE:
if (size%2 ==1) { 
for (int i = size/2; i < matrix.length -size/2;i++) {
   for (int j = size/2; j < matrix[0].length - size/2; j++) { 
       res.add(matrix[i][j]); 
   } 
}
// Time:O(m*n), Space:O(m*n) an m*n array

public List spiralOrder (int[][] matrix)
{




      List res = new ArrayList();




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




      // NOTE:Runtime Error Message:
      //Line 28: java.lang.ArrayIndexOutOfBoundsException: 1
      //Last executed input:
      //[[1,2,3,4,5,6,7,8,9,10]] 1x10 matrix, layer 10/2 =5??? or 1ayer 1/2 =0 
      //int size = Math.max(matrix.length, matrix[0].length);
      int size = Math.min( matrix.length, matrix[0].length );
      for (   int level = 0; level < size/2 ;level++)
      {

            // top, col iterate
            for (int j = level; j < matrix.length[0]-1-level; j++)
                  res.add( matrix[level][j] );
            // right, row iterate
            for (int k = level; k < matrix.length -1-level ; k++)
                  res.add(  matrix[k][matrix[0].length-1-level] );
            // bottom, col iterate
            for (int j = matrix[0].length-1-level; j >level; j--)
                  res.add( matrix[matrix.length-1-level][j]  );
            // left, row iterate
            for (int k = matrix.length-1-level; k > level; k--) 
                  res.add( matrix[k][level] );
      }






      if (size%2 ==1)
      {
            for (int i = size/2; i < matrix.length -size/2;i++)
            {
                 for (int j = size/2; j < matrix[0].length - size/2; j++)
                 {
                       res.add(matrix[i][j]);
                 }
            }
            /*
            // column size > row size 5x9
            if ( matrix.length < matrix[0].length )
            {
                for ( int i = levelNum; i < matrix[0].length - levelNum ; i++)
                {
                    result.add(matrix[levelNum][i]);
                }
            }
            // row size > column size 9X5
            else 
            {
                for ( int i = levelNum ; i < matrix.length - levelNum; i++)
                {
                    result.add(matrix[i][levelNum]);
                }
            }
            */
      }
        
     


      return res;



}
[1,2,3],
[4,5,6],
[7,8,9]
size = 3 layer =3/2 =1
for (i=0 i<1 data-blogger-escaped-2="" data-blogger-escaped-for="" data-blogger-escaped-j="3-1-0;j" data-blogger-escaped-k="">0;j--)
    for (k = 3-1-0; k>0;k--)
if (size%2==1)
     for (i= size/2;i< len-size/2;)  1; 3-1 count to end
         for (j=size/2; j < len-size/2) 3-1 count to end


3. Similar Ones

Spiral Matrix II
Set Matrix Zero
Rotate Image

[Combination][Backtracking] Subsets II

1. Example
Contain Duplicate

s=[1,2,2], a solution set is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]


2. Implementation
Q1: distinguish addition?
A1: num[index] or num[i] will have duplicate, so adding to existing solution would result duplicate subsets. Avoid?
make sure  num[index] or num[i] are not the same as their previous one and do the addition
Q1: BUT you also avoid the cases like [c,c] or [a,c,c] except avoiding cases such as [a,c](from[a]), [c](from[]). How to fix?
A1: item[], item[a] should be avoided. How do you record that, record the start of adding position
Suppose [1,1,2]
When [] you got addFromIndex = res.size()=0 res=[ ]
when [1] you got addFromIndex = res.size() = 1, res=[ [] ]
when [2] you got addFromIndex  = res.size()=2, res=[ [],[1] ]
when [2] you got addFromIndex = res.size() =4 ,res = [ [], [1], [2], [1,2]] . We use second 2's addFromIndex 2 as a base existing solution and add on [2],[1,2] =>[2,2], [1,2,2]




Input:[1,1]
Output:[[],[1],[1],[1,1]]
Expected:[[],[1],[1,1]]

// Recursive
// adding into existing, base case []
// Time:O(2^n), Space:O(2^n)
public List> subsetsWithDup(int[] nums)
{


       
       List> res = new ArrayList>(); 

      

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



       Arrays.sort(nums);



       // NOTE: record start adding position for each num[index]
       List lastSize = new ArrayList();
       lastSize.add(0); 
       return helper(nums, nums.length - 1, lastSize);



}
private List> helper(int[] nums, int index, List lastSize)
{




       
       // Base case 
       if (index = -1 )
       {
             List item = new ArrayList();
             List> res = new ArrayList>();
             res.add(item);
             //positionSet.add(res.size());
             return res;
       }





       List<List<Integer>> res = helper(nums, index -1);


       

 
       // NOTE: SubsetsII newly added compare to subset I to avoid duplicate set
       int start = 0;
       // NTOE: inside helper, out index start from -1,0,1...to len-1
       //if ( index != nums.length -1 && nums[index] == nums[index+1] )
            //start = positionSet.get(index+1);
        if (  index > 0 && nums[index] == nums[index-1] )            start = lastSize.get(0);






       int size_unchanged = res.size();
       // NOTE: SubsetsII
       for (int j = start ; j < size_unchanged; j++)
       { 






           // NOTE:
           //if ( index != nums.length -1 && nums[index] != nums[index+1]  )
           //{
                 List<Integer> item = new ArrayList<Integer>(  res.get(j) );
                 item.add( nums[index] );
                 res.add(item);
           //}
       


       }




       //lastSize.add(res.size());
       lastSzie.set(0, size_unchanged);
       return res;




}

// Iterative
// nested loop and adding into existing, add [] in the very first
// Time:O(2^n), Space:O(2^n)
public List<List<Integer>> subsetsWithDup(int[] nums)
{


   List<List<Integer>> res = new ArrayList<List<Integer>>();
   


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



   Arrays.sort(nums);      




   List<Integer> lastSize = new ArrayList<Integer>();
   lastSize.add(0);
   int size_unchanged = 0;    
   for (int i = 0 ; i < nums.length ;i++)   
   {        




          // NOTE: subsets II
          int start = 0;
          if ( i >0 && nums[i] == nums[i-1] )
                 start = lastSize.get(0);


        

           int size_unchanged = res.size();
           for (int j = start; j < size_unchanged; j++)
           //for (int j = 0; j< size_unchanged; j++)          
           {                 
               List<Integer> item = new ArrayList<Integer>(res.get(j));
               item.add(nums[i]); 
               res.add(item);

           }


           lastSize.set(0,size_unchanged);

    }


     return res;

}
3. Similar Ones
Subsets I
Combination Sum I/II (random combination sum equal to target value)

Monday, August 31, 2015

[Greedy] Jump Game

1. Example
Basic Idea: do you still have moves >= 0
You are positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index
s = [2,3,1,1,4] , return true
s= [3,2,1,0,4], return false

2. Implementation
Q1: jump? reach the last index?
A1: last Index =< current Index + s[current Index]. So s[i]+i is the maximum you can get
Q1:[2,A,B] ?
A1: you can go A and start from there or you can go B and start from there
Q1:[2,0,1,2]
A1: if you go to 0, unable to reach des. If you go to 1, you are able to do it.
total index 3
idx0 2 = 2 max
idx1 0 = 0 2 max-1 = 1 > 0
idx2 1 = 3 1max-1 = 0 < 3 max
idx3 2 = 5 3max-1= 2
out of loop true
 [3,2,1,0,4]
total index 4
idx0 3 =3 max
idx1 2 =3  3max- 1=2 ==2
idx2 1 =1   2max-1 =1 ==1
idx3 0        1mx-1 =0 == 0
idx4 4         0mx-1 < 0 false


// Time:O(n) ,Space:O(1)
public boolean canJump(int[] nums)
{
       // validate the input
       if ( nums == null || nums.length == 0)
            return false;
 


       int maxJump = nums[0];
       for (int i =1 ; i < nums.length; i++)
       {
            maxJump--;
            if (maxJump < 0)
                return false;
            if ( nums[i] > maxJump )
                maxJump = nums[i];

       }



       return true;



}


int reach = 0;// start from index 0
for (int i =0; i<= reach; && i < nums.length -1; i++)
{
      reach = Math.max(nums[i]+i, reach);
}



if ( reach < nums.length -1) // need to equal or larger than len-1 = last index
{
   return false;
}
else 
   return true; 


// Time:O(n^2)
nested loop 
for (i = 0; i< )
  for (j = 1; j< num[i])
3. Similar Ones

[Greedy] Best Time to Buy and Sell Stock II

[combination] [Backtracking][Bit manipulation] Subsets

1. Example
Sub +Set = distinguish set
nums = [1,2,3], a solution is:

[
[],

[1],
[2],
[3],

[1,2],
[1,3],
[2,3],

[1,2,3]

]

2. Implementation
Q1: combination?
A1: 2^n, n is the length of array
Q1: how to start? recursive ? avoid repeated element ?
A1: (nums, index+1), base case
Step1:

item = [], res=[    []    ], recursive call h: index from 0
for loop add single element i = 0,1,2
           i=0, item=   []+[1] , res [  [], [1]  ], recursive call h:  [1], index from 1
           for loop add single element 1,2
                   i=1, item = [1]+[2] , res =[ [], [1], [1,2] ], recursive call h:  [1], index from 2
                   for loop, i = 2
                          i =2, item = [1,2] +[3], res =[ [], [1], [1,2] , [1,2,3]  ]
                          out of loop return !!!!!!!!!!!
                   i=2, item = [1]+[3]
           i=1, item =  []+[2], recursive call h: [2] , index from 2
           for loop add single element 1,2
                  i=2, item =  [2] + [3]   
           i=2, item =  []+[3]
Distinguish/Separate element additon, every time add specific and different element by using existing solution
// NOTE: Recursive

if (index == -1 ) { 
 List<Integer> res = new ArrayList(); 
 List item = new ArrayList();
 res.add(item); 
 return res;
 }

List<Integer> res = helper(nums, index -1);

int size_unchanged_with_res = res.size();
 for(int i = 0; i < size_unchanged_with_res ; i++) { 
 List item = new ArrayList(res.get(i)); 
// NOTE: we add one item into multiple existing solution 
 item.add( num[index] ); 
 res.add( item ); 
 }

// NOTE: Iterative
for (int i = 0; i < nums.length; i++) {

int size = res.size(); 
 for ( int j = 0 ; j < size; j++) { 
 List item = new Arraylist(res.get(i)); 
 item.add(nums[i]); 
 res.add(item); 
 }
// NOTE: we add one item into multiple existing solution
           item.add(   num[index]  );
// NOTE:
Arrays.sort(nums);


// Recursive, bottom-up approach, h(h(h(h(-1))))
// Time:O(2^n), Space:O(2^n) list>

public List> subsets (int[] nums)
{

      List> res = new ArrayList>();
      


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



      //List item = new ArrayList();
      //res.add(item); // like pascal's triangle, for loop numberofRows and core prev[i] = prev[i] + prev[i-1], i-1 >=0 
      // NOTE: merge into recursive call

      
      Arrays.sort(nums);




      //helper(nums, 0,item,res);
      // NOTE: adopt bottom-up approach
      res = helper( nums, nums.length-1 );


      return res;



}
//private void helper(int[] nums, int start, List item, List> res)
private List>  helper(int[] nums, int index)
{
   



      //for (int i = start; i < nums.length; i ++)
      //{
      //        List newItem = new ArrayList (   item.add(nums[i]) );
      //        res.add(newItem);
      //        helper(nums, i+1, newItem ,res);
      //}
      //return;


      // Base case
      // NOTE: bring first case in main function into helper as base case
      if (index == -1 )
      {
           List> res = new ArrayList();
           res.add(new ArrayList());
           return res;
      }



       
      List> res = helper(nums, index -1);


  
      int size_unchanged_with_res = res.size();
      for(int i = 0; i < size_unchanged_with_res ; i++)
      {
            List item = new ArrayList(res.get(i));
            // NOTE: we add one item into multiple existing solution
            item.add(   num[index]  );
            res.add( item );
      }


     
      return res;



}
// Iterative approach: top down , from [] to [1,2,3]
public List> subsets(int[] nums)
{


        List> res = new ArrayList>();

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


         
       res.add( new ArrayList());
       Arrays.sort(nums);

      
       for (int i = 0; i < nums.length; i++)
       {
             int size = res.size();
             for ( int j = 0 ; j < size; j++)
             {
                    List item = new Arraylist(res.get(i));
                    item.add(nums[i]);
                    res.add(item);
             }
       }

     

       return res;

}
suppose [1,2,3]
[]
i = 0, add[1]
j = 0
[]+[1] =[1]
[],[1]
i = 1, add[2]
j = 0
[]+[2] = [2]
j = 1
[1]+[2] =[1,2]
[],[1],[2],[1,2]
i = 2,  add[3]
j=0
j=1
j=2  
3. Similar Ones
combination =>  sort
subsets II

[Recursive][DFS] Construct Binary Tree from Inorder and Postorder Traversal

1. Example

Inorder sequence    :   4 2 5 (1) 6 7 3 8
Postorder sequence:   4 5 2 6 7 8 3 (1)
The constructed BT is

                       1
                   /        \
                  2         3
               /    \       /   \
             4      5    7    8
                          /
                         6

2. Implementation
Q1: Binary Tree?
A1: node have val, left node, right node.
Step1: a root
Step2: root.leftsubtree, root.rightsubtree, 3 nodes form a small tree
Step3:  left subtree, right subtree
Step4: find each subtree's root
Q1: inorder?
A1: root in the middle.
Q1: postorder?
A1: root in the end.


public TreeNode buildTree(int[] inorder, int[] postorder)
{




      // validate the input
      if (inorder == null || postorder == null || inorder.length ==0 || postorder.length == 0)
            return new TreeNode();






       HashMap map = new HashMap<>();
       for (int i = 0 ; i < inorder.length; i++)
       {
            map.put(inorder[i], i);
       }





      // Find the root
      //return helper(inorder, 0, inorder.length-1, postorder, 0, postorder.length -1);
      return helper(inorder, 0, inorder.length-1, postorder, 0, postorder.length -1, map);
}

private TreeNode helper(int[] inorder, int inL, int inR, int[] postorder, int postL, int postR, HashMap map)
{




      // Base case
      //if (  inL < 0 || inR < 0 ||  postL <0 data-blogger-escaped-if="" data-blogger-escaped-inl="" data-blogger-escaped-null="" data-blogger-escaped-postr="" data-blogger-escaped-return=""> inR || postL > postR)
         return null;





      TreeNode root = new TreeNode( postorder[postR] );
      int rootIndex = map.get(root.val);
      root.left = helper(inorder,inL ,rootIndex-1 , postorder ,postL ,postL+(rootIndex-inL)-1,map);
      root.right = helper(inorder , rootIndex +1, inR, postorder ,postR -(inR- rootIndex), postR -1,map);



      
      return root; 



}
//O(log(n)) improve to O(1) using hashmap
private int binarySearch (int[] arr,int start, int end, int target)
{
      // validate the input
      if ( arr == null || arr.length == 0)
          return -1;
      int l = start;
      int r = end;
      while (l <= r )
      {
          int m = (l+m)/2;
          if ( arr[m] == target )
             return m;
          else if ( arr[m] > target ) 
             r = m-1;
          else 
             l = m+1;
      }
}
3. Similar Ones
(M) Construct Binary Tree from Preorder and Inorder Traversal

[Recursive][BackTracking][DFS] Word Search

1. Example
board =
[

["A B  C  E"],
["S  F  C  S"],
["A D  E  E"]

]

word = "ABCCED", -> return true
word= "SEE"          , -> return true
word ="ABCB"      , -> return false

2. Implementation
Q1: word search ?
A1: blind search form every character [i][j], search direction up, left, down, right
Q1: no repeated?
A1: when proceed search form certain character, we CANNOT go thru the start character again. MARKED it
Q1: Recursive?
A1: start nowhere and dig in through => DFS =>recursive
Q1: use index?
A1: index is like a trie, we can avoid some not wanted word in early stage

// NOTE: string matching if ( item == word) {
// NOTE: item don't have to backtracking since we get a new String every time we call helper()


// NOTE
if ( index == word.length() ) { return true; }

// NOTE
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || visited[i][j] || 
board[i][j] != word.chatAt(index) )

// NOTE
boolean res = helper(board, i+1,j,word, index+1,visited) || helper(board, i-1,j,word, index+1,visited) || helper(board, i,j-1,word, index+1, visited) || helper(board, i, j+1, word, index+1, visited)
// Backtracking, only visited for search from start node 
visited[i][j] = false;


// Time:O(m*n)=O(E+V) whole board, Space:O(m*n) call stack
public boolean exist (char[][] board, String word)
{



       // validate the input
       if (board == null || board.length ==0 || board[0].length == 0)
          return false;
       word.trim();
       // NOTE: string.length()
       if (word == null || word.length() == 0)
          return true;




       boolean[][] visited = new boolean[board.length][board[0].length];
       for ( int i = 0; ; i< board.length;i++ )
       {
            for (  int j = 0; j < board[0].length; j++ )
            {  
              //if (   helper(board,i,j, word, new string() )  )
             if (  helper(board,i,j,word,0, visited)  )
                   return true;
            }
       }

     

       return false;


}


//private boolean helper(char[][] board, int i, int j, String word, String item)
private boolean helper(char[][] board, int i, int j, String word, int index, boolean[][] visited)
{




       //item = item + board[i][j];
       
       // base case to stop
       // NOTE: string matching
       //if ( item == word)
// NOTE : use index to check word match
      if ( index == word.length()   )
       {
           return true;
       }







       //if (i < 0 || j < 0 || i > board.length || j > board[0].length )
        //   return false; // out of bound and still no word match
        // NOTE: i+1 = len if i = len -1 
       if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || visited[i][j]  || board[i][j] != word.chatAt(index)   )
           return false; // out of bound and still no word match




        visited[i][j] = true
       // recursive call to recursive
       // NOTE: move to top if equal, save the below checking effort
       //item = item + board[i][j];
       //if (helper(board, i+1, j, word, new String(item))
       //    || helper(board, i-1, j, word, new string(item))
       //    || helper(board, i, j+1, word , new String(item))
       //    || helper(board, i, j-1, word , new String(item))
       //   )
       //      return true;
       // NOTE: we need to return false, for nested for loop to go on
      
       boolean res = helper(board, i+1,j,word, index+1,visited)
           || helper(board, i-1,j,word, index+1,visited)
           || helper(board, i,j-1,word, index+1, visited)
           || helper(board, i, j+1, word, index+1, visited);

       // Backtracking, only visited for search from start node
       visited[i][j] = false;
       // NOTE: item don't have to backtracking since we get a new String everytime we call helper()






       return res;



}

3. Similar ones
 (H) Word Search II    
        Word Break II  

[DP][Subarray] Maximum Product Subarray

1. Example

s= [2,3,-2,4]
the contiguous subarray [2,3] has the largest product = 6

2. Implementation
Q1: what if negative * negative become the largest?
A1: keep an lastNegativeNumber to record the previous product is negative, if positive, we just erase it and assign 0 to it
Q1: subarray + maximum = > local , global ? what is global here? what is local here?
A1: global : maximum subarray product
local: previous product * current , current
e.g., [1,-2,3]
i=1
local = max(1*-2,-2) = -2
lastNeg = -2
global = max(1, -2)   =  1
i=2
local =max( -2*3,3)      =  3
lastNeg = -6
global = max(1,3)     =  3
Ans: the largest product is 3 form [3]

e.g., [1,-2,3,-4]
i =3
local = max(3*-4, -4) = -4
if ( curr < 0 && lastNeg <0)
  lastNeg * cur =  -6*-4 =24
  local = max(-4, 24) = 24
global = max(3,-4) = 3   X
global = max(24, 3) = 24
Ans: the largest product is 24 form [1,-2,3,-4]

Input:[-2,3,-4]
Output:16
Expected:24

// NOTE: snippet
int local_unchanged_copy = local;

local = Math.max( Math.max(local*nums[i], nums[i]), min_local*nums[i] );

min_local = Math.min( Math.min(nums[i]*local_unchanged_copy, nums[i]), nums[i]*min_local );



public int maxProduct (int[] nums)
{




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


     

     int global = nums[0];
     int local = nums[0];
     //int lastNeg = 0;
     // NOTE: min local = lastNeg
     int min_local = num[0];
     for (int i =1; i< nums.length ; i++)
     {
          //local = Math.max(local*nums[i], nums[i]);
          //lastNeg =(local < 0) ? local:0;
          //if ( nums[i] < 0 && lastNeg < 0 )
          //{
          //      local = Math.max(lastNeg*nums[i], local);
          //}

          int local_unchanged_copy = local;
          local = Math.max(  Math.max(local*nums[i], nums[i]),  min_local*nums[i]  );   
          min_local = Math.min(  Math.min(nums[i]*local_unchanged_copy, nums[i]),  nums[i]*min_local  );   
          global = Math.max(local, global);
     }
 



     return global;


}

3. Similar Ones
Subarray (continuous) + maximum => DP
(M) Best Time to Buy and Sell Stock
(M) Maximum Subarray
(M) Product of Array Except Self

Saturday, August 29, 2015

[DP][Divide and Conquer] Maximum Subarray

1. Example

Find  the contiguous subarray with the largest sum

s= [-2,1,-3,4,-1,2,1,-5,4]
the contiguous subarray [4,-1,2,1]
Return the largest sum 6

2. Implementation
Q1: sum => sorted?
A1: the answer require contiguous subarray, so we cannot break the original order
Q1: contiguous + maximum => DP
A1: DP[i] = max(DP[i-1] + s[i] , s[i]) ,since array may include negative number, so there is a chance current element value is greater than previous sum.
However, there is a a possibility DP[i-1] + s[i] < DP[i].
DP[i]  = max( DP[i-1]+s[i],s[i]), DP[i] the maximum sum including  i element
max= max(max, DP[i])
Q1: DP ?
A1: when there is a sense to pick up from start or pick up from anywhere and go on
FOLLOW UP: maximum product subarray
product have an chance to Negative* Negative become the largest
keep negative as a tempLastProduct and check every time
Q1: s=[-2,1,-3,4,-1,2,1,-5,4]
-2= -2            
-1=-2,1
-4=-2,1,-3
0=-2,1,-3,4
..
1=1
-2=1,-3
2=1,-3,4
..
-3 X
4
res[i] = the largest sum till i
i = 0 res[0] = -2
i =1 res[1] = max(res[0], 1, res[0]+1)

 // NOTE:
int local = num[0]; // NOTE: local keep tracking accumulated value or pervious value, but max just keep max which could be the last few element like first element, e.g., 10, -3,-2,-1 max =10, local = 10+-3+-2+-1

local = Math.max(local+nums[i], nums[i]); 

public int maxSubArray( int[] nums )
{
       // validate the input
       if (nums == null || nums.length ==0)
       {
           return Integer.MIN_VALUE;
       }



      
       // NOTE: don't have to keep an array to record each maximum so far, we just need the maximum value
       int global = nums[0];
       // NOTE: 
       int local = num[0];
       for (int i = 1; i < nums.length; i++)
       {
            //int local = Math.max(max+nums[i], nums[i]);
            // NOTE: local keep tracking accumulated value or pervious value, but max just keep max which could be the last few element like first element, e.g., 10, -3,-2,-1 max =10, local = 10+-3+-2+-1
            local = Math.max(local+nums[i], nums[i]);
            global = Math.max(global, local);
       }






       return global;



}
[-2,1,-3,4]
i =1 
-2+1,1 => 1 
1,-2 =>1 max

i=2
1+-3, -3=>-2
1,-3=>1 max

i=3
1+4, 4=>5
1,5 =>5
3. Similar Ones
(M)Best Time to Buy and Sell Stock
(M)Maximum Product Subarray

Friday, August 28, 2015

[DP][Path Sum][Triangle] Triangle

1. Example
Each step you may move to adjacent numbers on the row below.
[
     [2],
    [3,4],
  [6,5,7],
[4,1,8,3]
]
the minimum path sum from top to bottom is 11 (i.e.,   2+3+5+1 = 11)

2. Implementation
Q1: adjacent number ?
A1: last row i => next row i and i+1
Q1: minimum path , start from top, go left or go right
A1: e.g,, [2],
               [X,4]        1 from 0
               [2],
               [3,X]        0 from 0

               [3,X],      
               [6,X,X]    0 from 0
               [3,4],      
               [X,5,X]    1 from 0 or 1
               [X,4],      
               [X,X,7]    2 from 1
             
               [6,X,X],
               [4,X,X,X]   0 from 0
               [6,5,X],
               [X,1,X,X]     1 from 0 or 1
               [X,5,7],
               [X,X,8,X]     2 from 2 or 1
               [X,X,7],
               [X,X,X,3]      3 from 2
for every row you can keep a minimum
return sum so when return = > hit last row and last element
res[row.size()]

for (row =0 ~3)
 for ( i =0 ; i < row+1)
    i=0     res[ row ] += list.get(row).get(0) ,  min => res[row] = minimum
    i>0     min( res[row-1]+list.get(row).get(i),  row[row]+list.get(row).get(i) )
    i = row res[row-1]+list.get(row).get(row)

Q1: recursive?
A1:
1. base case                                   start > row's size => row+1,   row==last row return
2. for start from any point and      0 from 0, end from end-1, middle from middle or middle-1
combination sum, word breaker 1-D array
triangle => 2-D array

Q1: how to make it O(n)?
A1:

res[i] = res[i-1]+triangle.get(i).get(i);

res[0] = triangle.get(0).get(0);

 for (int i =1; i < triangle.size();i++)




//NOTE: res[i] in case the final res[0] value instead of the first one 

 //res[i] = res[i-1]+triangle.get(i).get(i); 
 res[0]+= triangle.get(i).get(0);





if (i == triangle.size()-1)
res[j] = triangle.get(i).get(j);

// Time:O(mxn), Space:O(n) rowNumbers
// NOTE: int[][] is a square array or fixed size 
// for size not determined use List>
public int minimumTotal(List> triangle)
{
     

      // invalidate the input
      if ( triangle == null || triangle.size() == 0)
      {
          return 0; // since all positive numbers
      }




      // NOTE: size() =1, avoid the below computation
      if ( triangle.size() == 1)
         return triangle.get(0).get(0);




      
      //int[] res = new int[triangle.size()];
      //res[0] = triangle.get(0).get(0);
      //for (int i = 1 ;i < triangle.size();i++)
      //{
      //    res[i] = res[i-1] + triangle.get(i).get(0);
      //}
      
      // NOTE: how to use a array to represent first index and last index at the same time, so res[row.size()] ides WRONG!
      // NOTE: WE can brute force like minimum path sum, but time complexity would be O(mxn), which means need for for loop
        


      // Must go to leaves, 4 minimum value , an array of size 4
      int[] res = new int[triangle.size()];
      // NOTE: merge
      //for (int i =0 ; i < triangle.size();i++)
      //{
      //    res[0]+= triangle.get(i).get(0);
      //}
      
   


      res[0] = triangle.get(0).get(0);
      for (int i =1; i < triangle.size();i++)
      //for (int i = 0 ; i < triangle.size()-1; i++)
      {
 


         
         res[i] = res[i-1]+triangle.get(i).get(i);





         //for (int j = 1 ; j < triangle.get(i).size()-1; j++)
         //for (int j = 1 ; j < i-1; j++)
         for (int j = i-1 ; j >= 1; j--)
             res[j] = Math.min(res[j], res[j-1] ) + triangle.get(i).get(j);  




         //NOTE: res[i] in case the final res[0] value instead of the first one 
         //res[i] = res[i-1]+triangle.get(i).get(i);
         res[0]+= triangle.get(i).get(0);



      
     }
      


      // NOTE: Merge
      ////for (int i=0; i < triangle.size();i++)
      // for (int i=1; i < triangle.size();i++)
      //{
      ////     res[i] += triangle.get(i).get(i);
      //       res[i] = res[i-1]+triangle.get(i).get(i);// previous row so res[i-1]
      //}




      //int min = Integer.MAX_VALUE;
      int min = res[0];
      //for (  int i = 0; i < triangle.size(); i++)
      for (int i =1 i < triangle.size();i++)
      {
           if (res[i] < min)
              min = res[i];
      }
     



      return min;




}
// Bottom-Up    Time:O(mxn), Space:O(n) res array
public int minimumTotal(List> triangle)
{
      




      // validate the input
      if ( triangle == null || triangle.length == 0)
      {
          return 0;// since all positive numbers
      }





      int[] res = new int[triangle.size()];
      for (int i = triangle.size()-1; i>=0; i--)
      {
           for (int j = i; j > = 0; j--)
           {
                if (i == triangle.size()-1)
                   res[j] = triangle.get(i).get(j);

                res[j] = Math.min( res[j], res[j+1] ) + triangle.get(i).get(j);
           }
      }



            
      return res[0];


}
i = 3
res[3]  =3
res[2]  =8
res[1]  =1
res[0]  =4
i = 2
res[2]  = min(res[2],res[3]) +7 = 10
res[1]  = min(res[1],res[2]) +5 = 6
res[0]  = min(res[0],res[1]) +6 = 7
i = 1
res[1]  = min(res[1], res[2]) + 4 = 10
res[0]  = min(res[0], res[1]) + 3 = 9
i=0
res[0] = min(res[0],res[1]) +2 = 11


Recursive Idea:
1.Base i i) helper(i+1,j)
2.for (j)
helper(i,j)


3. Similar Ones
path sum + minimum + continue => DP
1-D DP
[
Unique Path I and II
Minimum Path Sum
Buy and Sell stock at the Best Time
Maximum Subarray
]
Path Sum series
Triangle Series

[Recursvie][Combination][Sum][Backtracking] Combination Sum

1. Example

s= [2,3,6,7] and target 7
A solution set is :
[7]
[2,2,3]
repeated number is allowed

2. Implementation
Q1: From Combination Sum II, ?
A1: recursive + backtracking . add  recursive call .remove
2.for (i; i < ; i ++)
    .add(i)
    helper(i)
    .remove(size()-1)
return
1.Base Case
1-1 target == 0 return list of integers
1-2 target < 0 return
//1-3 i > len return
// NOTE: not len-1 since when i == len -1 we need to add
// no need for i > len since every time we call helper(i) with the same i which is bounded by the loop condition and never be greater than len


//NOTE: new ArrayList res.add( new ArrayList(item) );

// NOTE: like twoSum, threeSum need sorted Arrays.sort(candidates);

// NOTE: no duplicate start if ( i = 0 || candidates[i] != candidates[i-1]) {


// Time:O(n) over array, Space:O(n) list>
public List> combinationSum (int[] candidates, int target)
{


      List> res = new ArrayList>();
      // validate the input 
      if ( candidates == null || candidates.length == 0 )
      {
           return res;
      }

      // NOTE: like twoSum, threeSum need sorted 
      Arrays.sort(candidates);


      
      helper(candidates, 0, target, new ArrayList() ,res);
      


      return res;
}
private helper(int[] candidates, int start, int target, List item, List> res)
{     



      if ( target < 0)
         return;
      if (target == 0)
      {
         //NOTE: new ArrayList
         res.add( new ArrayList(item) );
         return;
      }




      for (int i = 0 ; i < candidates.length ; i++)
      {
          // NOTE: no duplicate start
          if ( i = 0 || candidates[i] != candidates[i-1])
          {
               item.add(candidates[i]); 
               helper(candidates, i, target - candidates[i], item, res);
               item.remove(item.size()-1);
          }
      }



      return;



}
3. Similar Ones
(M) Combination Sum II
(M) Combination Sum III
(M) Letter Combinations of a Phone Number
(M) Combinations
(M) Factor Combinations

[DP][Min][Path Sum] Minimum Path Sum

1. Example
[
[1,5,5]
[1,1,5]
[7,1,1]
]

minimum path =
[
[1,5,5]
[1,1,5]
[7,1,1]
]
Return sum = 5

2. Implementation
Q1: can we use the idea got from Unique Path?
A1: they use res[j] = res [j] + res[j-1] or 0 (if obstacle). We can just change total path number value into current cell value.
Q1: Still only move down or right, and how to formulate?
A1: path sum = res [i,j] = Math.max( res[i-1,j] + grid[i][j] , res[i][j-1] +grid[i][j] )
Q1: could have a case, current grid cell value is greater than previous sum?
A1: no worry, since assume non-negative number . so will only become larger and larger when move to current grid cell and add into path sum
Q1: if res[i,j] , the complexity for Time:O(mxn) and Space:O(mxn), any improvement?
A1: res[i] = min (   res[i-1] + grid[i][j],   res[i]+grid[i][j]   )
[
[1,5,5]
[1,1,5]
[7,1,1]
]
row =0
res[0] =1
res[1] =5
res[2] =5
row =1
res[0] = 1+1 =2
res[1] = min( res[0]+1, res[1]+1  ) = min(3,6) = 3
res[2] = min(res[1]+5, res[2]+5) = min(8, 10) = 8
row =2
res[0]= res[0]+7 = 9
res[1]=min(res[0]+1, res[1]+1) = min(10,4) =4
res[2] = min(res[1]+1, res[2]+1) = min(5,9)=5
return 5

Q1 :recursive?
A1:unique path  helper(i+1,j) + helper(i,j+1) ===>
                 min (  helper(i+1,j) +grid[i,j],   helper(i,j+1) + grid[i][j] )
 and base case would be i == m- 1 && j == n-1 return value otherwise return MAX
[
[1,5,5]
[1,1,5]
[7,1,1]
]
helper(0,0)
helper(1,0)+ 1,                                                                                helper(0,1)+1
    helper(2,0) + 1,                              helper(1,1) +1                        helper(1,1)+5,      helper(0,2)+5
    h(3,0)X+7, h(2,1)+7                      h(2,1)+1, h(1,2)+1
                       h(3,1)X+1 h(2,2)+1 ! h(3,1)X+1, h(2,2)+1

// NOTE: res[j] = min(res[j]+cell , res[j-1]+cell) i >1, so we init j = 0 first

// NOTE: if loop from i = 0, init value for all res array is 0 and could get wrong minimum value

//
NOTE: Base Case
 if ( i > grid.length -1 || j > grid[0].length -1) 
return Integer.MAX_VALUE;
 if ( i == grid.length-1 && j == grid[0].length-1) 
{ return sum + grid[i][j]; //return grid[i][j]; }
// DP 
// prev info + base case + init value
// Time :O(mxn) all cells, Space:O(n) array
public int minPathSum(int[][] grid)
{
    // validate the input
    if ( grid == null || grid.length ==0 || grid[0].length==0  )
    {
         return 0; // since all positive number
    }






    int[] res = new int[grid[0].length];
    // NOTE: res[j] = min(res[j]+cell , res[j-1]+cell) i >1, so we init j = 0 first
    res[0] = grid[0][0];
    //for (int j = 0 ; j < grid[0].length; j++)
    for (int j =1; j < grid[0].length; j++)
    {
         //res[j] = grid[0][j];
         res[j] = res[j-1] + grid[0][j];
    }




    // NOTE: if loop from i = 0, init value for all res array is 0 and could get wrong minimum value
    for (int i = 1 ; i <  grid.length ;i++)
        for ( int j = 0; j < grid[0].length;j++ )     
            res[j] = (j==0)? res[j] + grid[i][j]: Math.min( res[j-1], res[j] ) + grid[i][j];




    
    return res[grid[0].length -1];




}
public int minPathSum(int[][] grid)
{
     //validate the input
     if ( grid == null || grid[0].length == 0 || grid.length == 0)
     {
          return 0; // since all positive numbers
     }
     

     return helper(0,0,grid,0);


}
private int helper(int i, int j, int[][] grid, int sum)
//private int helper(int i, int j, int[][] grid)
{
     // validate the input
     ..





     // Base Case
     if ( i > grid.length -1 || j > grid[0].length -1)
        return Integer.MAX_VALUE;
     if ( i == grid.length-1 && j == grid[0].length-1)
     {
         
         return sum + grid[i][j];
         //return grid[i][j];
     } 





     return Math.min(  helper(i+1, j, grid, sum+grid[i][j]), helper(i,j+1, grid, sum+grid[i][j])    );
     //return Math.min(   helper(i+1,j,grid),helper(i,j+1, grid)  ) + grid[i][j];





}
helper(0,0)
h(1,0, "1"), h(0,1, "1")
h(2,0, "1,1"),h(1,1, "1,1")
              h(2,1,"1,1,1") h(1,2,"1,1,1")
              h(2,2,"1,1,1,1"), h(3,1)
              return "1,1,1,1,1" ,  return"MAX" ==> "1,1,1,1,1"
3. Similar Ones
DP= grid + max or min

(M)          Unique Paths I/II
(H)           Dungeon Game
[Tree]       Path Sum
[Tree]       Path Sum II
[Tree]       Binary Tree Maximum Path Sum
[Tree]       Sum Root to Leaf Numbers

Thursday, August 27, 2015

[Sum][Two Pointers] 3Sum Closest

1. Example

s = [-1,2,1,-4] and target =1
A closest sum is  2
(-1+2+1 = 2 )


2. Implementation
Q1: 3Sum check exactly equal, how about closest?
A1: Equal means diff = 0, closest means diff is min. So we calculate the difference and choose the minimum
int min = (num[0]+num[1]+num[2]) - target ;
int diff = twoSum(nums, i-1, target - num[i]);
if ( Math.abs(diff) < Math.abs(min) )
if ( nums[l] + nums[r] == target ) { // Exactly one solution // NOTE: return diff return 0; }
return min;
return target + diff;





// time:O(n^3), Space:O(1)

public int threeSumClosest(int[] nums, int target)
{
    

     // validate the input
     if ( nums == null || nums.length < 3 )
     {    
          // sum may be zero, so we return min
          //return 0;
          return Integer.MIN_VALUE;
     }




     Arrays.sort(nums);






     int min = (num[0]+num[1]+num[2]) - target ;
     // NOTE :  i-1, so starting point 2
     for(int i = nums.length -1; i > 1 ;i--)
     {       
           // Exactly one solution, no need to avoid duplicate   
           //if ( i == num.length -1 || num[i] != num[i+1])
           //{
                    //int threesum = num[i] + twoSum(nums, i-1, target- nums[i]);
                    //int diff =  threesum - target  ;
                    
                    int diff = twoSum(nums, i-1, target - num[i]);
                    if (   Math.abs(diff) < Math.abs(min)  )
                    {
                        min = diff;
                    } 
           //}
     }
     



     // NOTE : even for two sum diff = num[l]+num[r] - target', where target' = target - num[i], so diff = num[l] + num[r] + num[i] - target
     return target + diff;



}


private int twoSum (int[] nums, int end, int target)
{





     if (  nums== null | nums.length < 2)
     {
           return Integer.MIN_VALUE;
     }

     


     int min =  (num[0] + num[end]) - target ;
     int l = 0; 
     int r = end;
     while(   l < r  )
     {
              int diff = (num[l]+num[r]) - target  ;
              if ( nums[l] + nums[r] == target )
              {
                    // Exactly one solution
                    // NOTE: return diff
                    return 0;
              }
              else if (  nums[l] + nums[r] > target )
              {
                    r--;
              }
              else 
              {
                    l++;
              }
              if ( Math.abs(diff)  < Math.abs(min)  )
              {
                    min = diff;
              }
     }


     return min;
     //return target + diff;



}
3. Similar ones
3Sum
3Sum Smaller

[Permutation] Next Permutation

1. Example

Rearrange number into the lexicographically next greater permutation of numbers
e.g., 1,2,3 -> 1,3,2
e.g., 1,1,5 -> 1,5,1
e.g., 1,2->2,1
If such arrangement is not possible, it must rearrange it as the lowest possible order(i.e., sorted in ascending order)
e.g., 3,2,1-> 1,2,3
e.g., 2,7, 6,3    ,5,4,1 -> 2,7,6,   4   1,3,5

2. Implementation
Not possible case: number is in ascending order from backward, the solution is reverse it
e.g., 3,2,1
Possible case: number is not in ascending order from backward, the solution is record the one where first non ascending occur.
e.g., 1,2,3 -> first non ascending occur is in length-2
e.g., 1,1,5 -> first non ascending occur is in length-2
Q1: what to do after find out non-ascending index?
A1: find the least greater number to replace it
Q1: After replacing, your number become greater but is that the next smallest?
A1: Not yet. there is one part you can still optimize -  Reverse the backward ascending part into forward ascending one.

Input:[1,3,2]
Output:[3,2,1]
Expected:[2,1,3]

Input:[1,2,3]
Output:[3,2,1]



Expected:[1,3,2]
Runtime Error Message:Line 124: java.lang.ArrayIndexOutOfBoundsException: -1
Last executed input:[1]
int nonAscendingIndex = nums.length -2;


while (nonAscendingIndex >=0 && nums[nonAscendingIndex] >= nums[nonAscendingIndex+1] ) { 
          nonAscendingIndex--; 
}
int leastGreaterIndex = nonAscendingIndex+1;
int leastGreaterIndex = nonAscendingIndex+1;

while( leastGreaterIndex < nums.length && nums[leastGreaterIndex] > nums[nonAscendingIndex] ) 
          leastGreaterIndex++; 
leastGreaterIndex--;


// Time:O(n), Space:O(1)
//Runtime Error Message:
//Line 139: java.lang.ArrayIndexOutOfBoundsException: -1
//Last executed input:
//[1,2]
// Input:
//[1,2]
//Output:
//[1,2]
//Expected:
//[2,1]
public void nextPermutation(int[] nums)
{


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

     



      // NOTE :start from back
      int nonAscendingIndex = nums.length -2;
      while (nonAscendingIndex >=0 && nums[nonAscendingIndex] >= nums[nonAscendingIndex+1] )
      {
          nonAscendingIndex--;
      }





      // NOTE: case all backward ascending will both end up i = -1
      if ( nonAscendingIndex >= 0 )
      {
          // [1,2,3] -> [1,3,2] not [3,1,2]
          int leastGreaterIndex = nonAscendingIndex+1;
          while(  leastGreaterIndex < nums.length && nums[leastGreaterIndex] > nums[nonAscendingIndex] )
          {
               leastGreaterIndex++;
          }
          leastGreaterIndex--;
          swap(nums, nonAscendingIndex,leastGreaterIndex);
      }
 
      
      // case1: backward in descending case
      // case2: only one element
      // case3: regular case, after swap
      reverse(nums,i+1, num.length-1);
}

public void swap(int[] nums, int l, int r)
{
      //validate the input
      if ( nums == null || nums.length ==0 )
      {
         return;
      }


      int temp = nums[l];
      nums[l] = nums[r];
      nums[r] = temp;
}

public void reverse (int[] nums, int start , int end)
{

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


       int l = start;
       int r = end;
       while (l < r)
       {
             int temp = nums[l];
             nums[l] = nums[r];
             nums[r] = temp;
             l++;
             r--;
       }
}

3. Similar Ones (M) Permutations (H) Permutations II (M) Permutation Sequence (M) Palindrome Permutation II

[Sum][Backtracking] Combination Sum II

1. Example

-All numbers (including target) will be positive integers.
-Elements in a combination(solution) must be non-descending order. ( i.e, a1<=a2<=a3<=..<=ak)
-No duplicate combinations(solutions).

s= [ 10,1,2,7,6,1,5] and target 8
A solution set is :
[1,7]
[1,2,5]
[2,6]
[1,1,6]



2. Implementation
Q1: Like 3Sum or 4Sum?
A1: In 3Sum or 4Sum, we fixed one or two elements and get the other two from 2Sum. However, the number of elements in a combination is non-determined.
Q1: Elements in a combination must be non-descending order ?
A1: Sorted array and pick up the number from the start
Q1: how do we backtracking ?
A1: suppose today you have an combination 1,2,5  how to back to 1 and continue look up other elements to form 1,7. So we start from every element like Word Breaker II
E.g.,
c
ca
cat + reset start and continue from s(sanddog)
E.g.,
1,1,2,5,6,7,10
1
List<Integer> item
target == 8 STOP res.add(item) => Base Case
>8 return


// Time:(2^n), Space:O(n) list>
public List> combinationSum2(int[] candidates, int target)
{
                
          List> res = new ArrayList>();
          // validate the input 
          if ( candidates == null || candidates.length == 0)
          {
              return res;
          }
          
        

          Arrays.sort(candidates);

 

          
          //for(int i = 0 ; i < candidates.length; i++)
          //{
          //       if (i==0 || candidates[i] != candidates[i-1])
          //       {
          //           List item = new ArrayList();
          //           item.add(candidates[i]);
          //           helper(candidates, i+1,target-candidates[i],item,res);
          //       }
          //}


          // NOTE: do same thing above for loop with helper, so merge it into helper for loop
          // NOTE: use new in parameter to save declare and initialize
          helper(candidates, 0, target, new ArrayList(), res);

          

          return res;
      

}

private void helper(int[] candidates,int start ,int target, Listitem, List> res)
{


          // Base Case 
          // Input:
          // [1], 1
          //Output:
          //[]
          //Expected:
          // [[1]]
          // NOTE: some solution include last element which happen in case start == length, so we have to avoid that
          if (target < 0 || start > candidates.length)
          {
                return;
          }
          if (target == 0 )
          {
                // NOTE: item is an object defined in for loop, for that one object we may have different combination
                //List newItem = new ArrayList(item);
                //res.add(newItem);
                // NOTE: inner List already create a ref, so we just need to new an object and put in
                res.add(new ArrayList(item));
                return;
          }
          





          //if (target > 0)
          //{
                for ( int i = start; i < candidates.length;i++)
                {
                    // NOTE: avoid duplicate 
                    //if (i > start && candidates[i] == candidates[i-1])
                    //{
                    //    continue;
                    //}
                    if ( i == start || candidates[i] != candidates[i-1])
                    {
                       item.add(candidates[i]);
                       helper(candidates, i+1, target - candidates[i], item, res);
                       item.remove(item.size()-1);
                    }
                }
                return;
          //}
          //return;




}

idx 0 1 2 3 4 5 6

s   1,1,2,5,6,7,10

h(1,7,"1")
     helper(2,6,"1,1")
        helper(3,4,"1,1,2")
           helper(4,-1,"1,1,2,5") return remove5
           helper(5,-2,"1,1,2,6") return remove6
           helper(6,-6,"1,1,2,10") return remove10
        return
        remove 2 
        helper(4,0,"1,1,6") Solution!
        return
        remove6
        helper(5, -1 "1,1,7")
        return 
        remove 7
        helper(6, -4 "1,1,10")
        return 
        remove 10
     return
     remove 1
     helper(3,5,"1,2")
h(2,7,"1") skip
h(3,6,"2")
h(4,3,"5")
h(5,2,"6")
h(6,1,"7")
      helper(7,-9,"7,10") return
      remove 10
return      
h(7,-2,"10") return
3. Similar Ones
Combination Sum
3Sum
4Sum

Wednesday, August 26, 2015

[DP] Best Time to Buy and Sell Stock

1. Example

s is array of price at each day
s = [$10, $50, $60, $20, $45, $100]
Find the maximum profit?
Only one transaction

2. Implementation
two nested for loop to compare i=0 - len-1 j = i+1 - len-1
Q1: only one transaction
A1: fins the lowest point and highest point but may not in chronological order, so do transaction in chronological order and compute the maximum
Q1: how to accumulate ?
A1: suppose $0 $10 $40 we want $ 0 and $40 so we can accumulate two section $10-$0 + ($40 -$10) to get .
A1: suppose $10 $0 $40 anyone after  has the lowest value (like $0), we take it to replace the previous value ()
DP
so far the maximum profit
DP[i] = MAX(     DP[i-1] + (prices[i]-prices[i-1]) ,  (prices[i]-prices[i-1])     )
//NOTE:
local = Math.max(local+prices[i+1] - prices[i],prices[i+1] - prices[i]);
// Time:O(n) over array, Space:O(1) local global variables
public int maxProfit(int[] prices)
{

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



     int global = 0;
     int local = 0;
     for (int i = 0 ; i <  prices.length -1; i++ )
     {
          //X int local = prices[i+1] - prices[i]  ([i+1]-[i],0)
          // NOTE: 
          local = Math.max(local+prices[i+1] - prices[i],prices[i+1] - prices[i]);
          //X global = Math.max(local+global, local); // if local is negative, it will be ruled out
         global = Math.max(global, local);
     }
}

[$10, $0, $50]
i = 0 local =-10, global = 0
i=1   local = 50, global =max(0+50,50) =50

[$0, $10, %40]
i = 0 local 10. global =10
i=1 local =30 global =max(30+10, 30) = 40

[%50,$30,$0]
i= 0 local -20 global 0
i=2 local -30 global max(0,-30) = 0

3. Similar ones
NOTE: maximum, continuous
Maximum Subarray
Best Time to Buy and Sell Stock II, III, IV

[Duplicate][Two Pointers] Remove Duplicates from Sorted Array II

1. Example
Allow one duplicate!
s= [1,1,1,2,2,3]
You should return length = 5
new s = [1,1,2,2,3]

2. Implementation
duplicate => hash
sorted array => duplicate next to each other
keep checking and replace the second(third here since it allow a duplicate) duplicate
with the next non-duplicate character
Q1: how to know duplicate happen?
A1: keep a index to point out where duplicate happen
Q1: how to know this is third duplicate and is not allowed?
A1: keep a index to point out where duplicate happen plus one flag to indicate this is first duplicate
. So when duplicate happen and firstDuplicate flag is true, we tend to replace this duplicate (record its index) with the next non-duplicate
Q1: Can we use the method by counting how many duplicate which is beyond two duplicate happen?
A1: we can do that by keep two pointers
NOTE:
when detect first duplicate happen, we see it as a non-duplicate and increment lastIndex value // 
NOTE: duplicate if ( nums.length < 2) { return nums.length; }



// Time:O(n), Space:O(1)

public int removeDuplicates(int[] nums)
{


    // validate the input
    // NOTE: duplicate
    if ( nums.length < 2)
    {
        return nums.length;
    }


 


    int lastIndex = 0;
    int iterIndex = 1;
    boolean firstDuplicate = fasle;
    while (   iterIndex < nums.length )
    {
          if (  nums[lastIndex] == nums[iterIndex]  ) 
          {
               if (!firstDuplicate)
               { 
                   lastIndex++;
                   firstDuplicate = true;
               } 
          }
          else 
          {
               lastIndex++;
               nums[lastIndex] = nums[iterIdnex];
               firstDuplciate = false;
          }
          iterIndex++;
    }

    return lastIdnex+1;
0 1 2 3 4 5
l i
1,1,1,2,2,3

i1  n[0]==n[1]
    fl= t 
    l++=> 1
    i++ => 2
i2  n[1]==n[2]
    i++= > 3
i3  n[1] != n[3]
    l++ => 2
    n[2] = n[3]
    i++ => 4
    fl = f
i4  n[2] = n[4]
    f1 = t 
    l++ =>3
    i++ =>5
i5  n[3] != n[5]
    l++ => 4
    n[4] = n[5]
    i++ => 6
    STOP
}
 int last = 1;
 int iter =2;
 while ( iter < nums.length )
 {
      if (nums[iter] == nums[last] && nums[iter]== nums[last-1])
          iter++
      else
      {
          last++;
          num[last] = num[iter];
          iter+=
      }
 }

 return last++;
3. Similar Ones
Remove Duplicate from Sorted Array

[Path][DP] Unique Paths II

1. Example

[
[0 ,0 ,0]
[0 ,1, 0]
[0 ,0, 0]
]
return the total number of unique paths is 2



2. Implementation
res[j] = res[j] + res[j-1];
res[j] = 0 if grid is 1
[1,1,1]
[1,X,1]
[1,1, 2]
DP
1. prev info
2. iterate
3. init value


// Time:(m*n) for for loop, Space:O(n) array
public int uniquePAthsWithObstacles(int[][] obstacleGrid)
{


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




       int[] res = new int[obstacleGrid[0].length];
       res[0] = 1;
       //if (obstacleGrid[0][0] != 0) never happen
       for (int i = 0 ; i < obstacleGrid.length; i++)
       {
           for ( int j = 1 ; j < obstacleGrid[0].length;j++) 
           {
               res[j] = (obstacleGrid[i][j] == 0)?res[j]+res[j-1]:0;
           }
       }





       return res[obstacleGrid[0].length-1];
}
// Time:O(m*n) go over all cells, Space:O(n)
public int uniquePath(int[][] obstacleGrid)
{
      // validate the input
      if ( obstacleGrid == null || obstacleGrid.length == 0 || obstacle[0].length == 0)
      { 
           return 0;
      }
      
     
      return helper(obstacleGrid, 1,1);

}
private int helper(int[][] grid, int m, int n)
{



      if ( m == grid.length && n == grid[0].length)
      {
           return 1;
      }
      if (m > grid.length || n > grid[0].length)
      {
          return 0;
      }
      if ( grid[m][n] == 1 )
      {
          return 0;
      }



      helper(grid, m+1, n) + helper(grid, m, n+1);
}
   123

1  000
2  010
3  000

m = 3 and n = 3
(1,1)
     (2,1)        +              (1,2)
     (3,1)        + (2,2)X       (2,2)X           +  (1,3)
     (4,1)X+(3,2)                                    (2,3) + (1,4)X
            (4,2)X+(3,3)                             (3,3) + (2,4)X 
record when base case happen 
(1,1)(2,1)(3,1)(3,2)(3,3)
(1,1)(1,2)(1,3)(2,3)(3,3)
3. Similar Ones
Unique Paths

[Greedy] Best Time to Buy and Sell Stock II

1. Example

s is array of price at each day
s = [$10, $50, $60, $20, $5, $40]
Find the maximum profit?
You may complete as many as transactions as you like.
Not multiple transaction at the same time, which means you must sell stock before you buy again.

2. Implementation
Q1: maximum profit?
A1: accumulate every profit opportunity
Q1: can i buy at the lowest price and sell at the highest?
A1: only one transaction.
Q1: buy before sell ?
A1: we cannot find every large gap to do the transaction since they are probably not in chronological order. So check every transaction and if profitable, we do it.


// Time:O(n), Space:O(1)
public int maxProfit(int[] prices)
{

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



      int profit = 0;
      for (int i =1; i < prices.length ; i++)
      {
            ((prices[i] - prices[i-1]) > 0 )? profit += (prices[i] - prices[i-1]): continue;
      }



      return profit;
}

3. Similar Ones
Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock III
Best Time to Buy and Sell Stock IV