[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

[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

[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

[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

[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

[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

[Matrix] Set Matrix Zeroes

1. Example
Given a mxn matrix, if an element is 0, set its entire row and column to 0.
Do it in-place?
[
[1,11,  1,1]
[2,  3,  4,0]
[5,  6, 19,8]
]
=>
[
[1,11 ,1 ,0]
[0,  0 ,0 ,0]
[5,  6, 19,0]
]

[
[1,11,  1,0]
[2,  3,  4,0]
[5,  6, 19,8]
]
=>
[
[0,0 , 0,0]
[2,  3,  4,0]
[5,  6, 19,0]
]
=>
[
[0,0 , 0,0]
[0,  0,  0,0]
[0,  0, 0,0]
]
=> WRONG, cannot set matrix zero in serial order
2.  Implementation
do a statistics to collect which row or index has zero and set the zeroes in a batch according to statistics table
Q1: how to form a such table ?
A1: keep two boolean array for row and column like row[m] and col[n]
Q1: how to form a such table without Extra space?
A1: use the the first row and the first column as row[m] = matrix[i][0]
and col[n] = matrix[0][i]
Q1: What about first column or first row has zero by itself?
A1: use two boolean flag to record

// Time :O(mxn) over the matrix, Space:O(1) two flag
public void setZeroes (int[][] matrix)
{
      // validate the input
      if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
      {
         return;
      }

      


      boolean fstRowWithZero = false;
      boolean fstColWithZero = fasle;
      for (int i = 0 ; i < matrix. length;i++)
      {
           if (matrix[i][0] == 0)
           {
                fstColWithZero = true;
                // NOTE:
                break;
           }
      }
      for (int j = 0 ; j < matrix[0].length;j++)
      {
           if (matrix[0][j] == 0)
           {
                fstRowWithZero = true;
                // NOTE:
                break;
           }
      }



      // NOTE: start from second row and column
      //for ( int i = 0 ; i < matrix.length;i++)
      for ( int i = 1 ; i < matrix.length;i++)
      {
          //for (int j = 0 ; j < matrix[0].length ; j++)
          for (int j = 1 ; j < matrix[0].length ; j++)
          {
                if (matrix[i][j] == 0 )
                {
                     matrix[i][0] = 0;
                     matrix[0][j] = 0;
                }
          }
      }




      for (int i = 0 ; i < matrix.length;i++)
      { 
         for ( int j = 0 ; j < matrix[0].length ;j++)
         {
              if (   matrix[i][0] == 0 || matrix[i][j] == 0   )
              {
                   matrix[i][j] = 0;
              }
         }
      }
      if (fstRowWithZero == true)
      {
         for (int j = 0 ; j< matrix[0].length;j++)
         {
              matrix[0][j] = 0;
         }
      }
      if (fstColWithZero == true)
      { 
         for (int i = 0 ; i < matrix.length;i++)
         {
              matrix[i][0] = 0;
         }
      }

}

3. Similar Ones
Rotate Image
Search a 2D matrix
Spiral Matrix
Spiral Matrix II

[Sum] 3Sum

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



2. Implementation
Thought1:
Q1: like two Sum
A1: sort the array first
Fix one and the rest use twoSum()
Q1: fix one which one
A1: from the end of the array
Q1: Duplicate solution avoid
A1: same element not being used twice, num[i] in fix one, and the other two in twoSum
Q1: how to combine twoSum and fixed one element to become three sum
A1: list get and add and addAll
FOLLOW UP: solution element in order as original array?

List item = new ArrayList();
 item.add(num[l]);
 item.add(num[r]); 
 // NOTE: no need to check repeated solution since already avoid when iterating res.add(item); // NOTE: more than one solution so iterating l++; r--;
 // avoid Duplicate solution
 while (l < r && num[l] == num[l-1] ) { l++; } 
 while( l< r && num[r] == num[r+1] ) { r--; }

public List> threeSum (int[] num)
{

        List> res = new ArrayList>();


       // valid the input
       if (num == null || num.length <3 data-blogger-escaped--1="" data-blogger-escaped-arrays.sort="" data-blogger-escaped-for="" data-blogger-escaped-i="" data-blogger-escaped-int="" data-blogger-escaped-note:="" data-blogger-escaped-num="" data-blogger-escaped-res="" data-blogger-escaped-return="" data-blogger-escaped-sort="">1 ; i--)
       {
           // NOTE: avoid repeated solution
           if ( i == num.length || num[i] != num[i+1] )
           {  
             List> curRes = twoSum(num, i-1, 0 - num[i]);
             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 end, int target)
{
        List> res = new ArrayList>();


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

      
       
       int l =0 ;
       int r = end;
       while (l< r)
       {
             if (  num[l] + num[r] == target )
             {
                   List item = new ArrayList();
                   item.add(num[l]);
                   item.add(num[r]);
                   // NOTE: no need to check repeated solution since already avoid when iterating 
                   res.add(item);
                   // NOTE: more than one solution so iterating
                   l++;
                   r--;

                   // avoid Duplicate 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++
             }

             // NOTE : avoid solution when equal to target

       }
       return res;


}

3. Similar Ones
Combination Sum II
Two Sum
4Sum
3Sum closest

[Sum]Two Sum [Facebook]

1. Example
a = [2,7,11,15] , target =9
2+7=9
Return index1 =1, index2 =2;



2. Implementation
Q1: return an index
A1: need to secure original array to find the index
Q1: how many solution set?
A1: Exactly one solution
Thought1: pairs O(n^2)
Thought2: sort O(n log(n))
// NOTE: snippet
if (res[0] == nums[i] || res[1] == nums[i])
{
if (index1 == -1)
{
index1 = i+1;
}
else
{
index2 = i+1;
}
}

// Time:O(n log(n)), Space:O(n) new array
public int[] twoSum (int[] nums, int target)
{
     int[] res = new int[2];
     // valid the input
     if (nums == null || num.length <2)
     {
         return res;
     }
      




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





     int index1 = -1; 
     int index2 = -1;
     for (int i = 0 ; i < nums.length ; i++)
     {
          if (res[0] == nums[i] || res[1] == nums[i])
          {
               if (index1 == -1)
               {
                   index1 = i+1;
               }
               else 
               {
                   index2 = i+1;
               }
          }
     }
     res[0] = index1;
     res[1] = index2;
     return res;

}

3.  Similar Ones
3Sum
4Sum
3Sum closest

[Duplicate] Contains Duplicate II

1. Example

a =[1,2,3,4,5,1,5]

int k = 5 the difference between idx5 - idx 0 = 5 => return true 5<=k
a = [1,2,3,4,5,6,1,5]
int k = 5 the difference between idx6 - idx 0 = 6 => return false 6> k

2. Implementation

check out current duplicate index with previous index
// NOTE: find the max gap and it is still less than k
// NOTE: at most so equal is allowed
// NOTE: snippet

if ( min > Math.abs(map.get(nums[i]) - i ) ) 
 { 
 min = Math.abs(map.get(nums[i]) - i ); 
 }

// Time :O(n), SpacE:O(n) map
public boolean containsNearbyDuplicate(int[] nums, int k)
{
      // valid the input
      if (nums == null || nume.length == 0)
      {
           return false;
      }
    


      HashMap res = new HashMap();
      // NOTE: find the max value and it still less than k
      int min = Integer.MAX_VALUE;
      for (int i = 0 ; i < nums.length;i++)
      { 
         if (   map.containsKey( nums[i] )    )
         { 
               if (   min > Math.abs(map.get(nums[i]) - i )   )  
               {
                    // return true;
                    min = Math.abs(map.get(nums[i]) - i );
               }
         }
         else 
         {
               mqp.put(nums[i], i);
         }
      }


 
      // NOTE: at most so equal is allowed
      if (min <= k)
      {
         return true;
      }
      else
      {
         return false;
      }
}

3. Similar Ones

(E) contains Duplicate

(M) Contrains Duplicate |||

[Duplicate][Divide and Conquer][Bit Manipulation]Majority Element

1. Example
The majority element is the element that appears more than  ⌊ n/2 ⌋  times
a= [1,1,1,3]   n=4 , 4/2 = 2
=> majority element 1 occur thrice

2. Implementation

Thought1: count element's occurences and loop to fins out whose occurences is larger than n/2
1-0 duplicate => hashSet or hashMap
1-1 a hashmap

Thought2: n/2 that means (n/2) / (n) = 1/2 with half probability to pick up the majority element
NOTE: count =0 reset last element
if curr = last element, count++
else count--

// NOTE: snippet

if (count == 0 ) { 

lastElem = nums[i]; 

count++; 

} else if ( lastElem == nums[i] ) { 

count++; 

} else {

 count--; 

}


<>

Time:O(2*n), Space:O(n) hashmap
public int majorityElement (int[] nums)
{
     // valid the input
     if ( nums == null || nums.length == 0)
     {
         return -1;
     }
  

     HashMap  map = new HashMap();
     for (int i = 0 ; i < nums.length;i++)
     {
          if (   map.containsKey(nums[i])  )
          {
                 map.put(nums[i], map.get(nums[i] + 1 );
          }
          else 
          {
                 map.put(nums[i], 1);
          }
     }
     


     //for (Entry e: map)
     for (Entry e: map.EntrySet() )
     {
          if (e.getValue() > (nums.length >>1) )
          {
              return e.getKey();
          }
     }

}

     for (int key: map.keySet())
     {
         if (map.get(key) > (nums.length >>1) )
         {
             return key;
         }
     }

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


     int count = 0;
     int lastElem = nums[0];
     for (int i=1 ;i < nums.length;i++)
     {
        
         //if (lastElem == nums[i])
         //{ 
         //     count++;
         //}
         //else 
         //{
         //     count = 0;
         //     lastElem = num[i];
         //}

         if (count == 0 ) 
         {
              lastElem = nums[i];
              count++;
         }
         else if ( lastElem == nums[i] )
         {
              count++;
         }
         else 
         {
              count--;
         }
     }




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

3. Similar Ones
(M) Majority Element

[Merge][Two Poitners] Merge Sorted Array[Facebook]

1. Example
a = [1,2,3,4]
b= [7,8,9,10]
c= merge a and b = [1,2,3,4,7,8,9,10]



2. Implementation
Q1:void => in-place
A1:assume one array size is large enough to accommdate the others.
Q1:hard to insert element into existing array ?
A1:start merging from the last element, backward iterating
num1[m-1]
num2[n-1]
num1[m+n-1]
Q1: one is larger than the other
A1: while to prepend the rest
// NOTE: the reason giving m and n is m is available size and in fact num1's size is larger than m
// NOTE :snippet
int indexNum1 = m-1;

 int indexNum2 = n-1;

 int indexTotal = m+n-1;

while( indexNum2 >=0 )

// Time:O(m+n), Space:O(1)
public void (int[] num1, int m, int[] num2, int n)
{
     // valid the input
     //if (num1== null || m == 0)
     //{
     //     return num2;
     //}
     //if (num2==null || n == 0 ) 
     //{
          //return num1;
     //     return;// void
     //}
     if ( num1 == null || num2 == null )
     {
          return;
     }





     // NOTE: the reason giving m and n is m is available size and in fact num1's size is larger than m
     int indexNum1 = m-1;
     int indexNum2 = n-1;
     int indexTotal = m+n-1;
     //while ( m >=0 && n>=0)
     while (indexNum1 >= 0 && indexNum2 >= 0)
     {
         if (num1[indexNum1] > num2[indexNum2] )
         {
              num1[indexTotal--] = num1[indexNum1--];
         }
         else 
         {
              num1[indexTotal--] = num2[indexNum2--];
         }
     }





     while( indexNum2 >=0 )
     {
         num1[indexTotal--] = num2[indexNum2--];
     }
     while (indexNum1 >= 0)
     {
         num1[indexTotal--] = num1[indexNum1--];
     }
}

3. Similar Ones
(E) Merge two sorted lists

[Triangle] Pascal's Triangle II

1. Example
k =3
return [1,3,3,1]

[
[1],
[1,1],
[1,2,1],
[1,3,3,1]   <= k=3
]

2. Implementation
only O(k) extra space since if use Pascal's Triangle I's method, space:O(n)
cannot have a new List<Integer> for every row, so keep overwriting the existing one
List<Integer> would only keep current list element so for k =3 only keep 4 elements


// NOTE: first row refers to k = 0

// NOTE: forward iterating would race

// NOTE: 3(idx=2) = 1(idx=2) + 2(idx=1)

// NOTE: 3(idx=2) = 2(idx=1) + 1(idx=2)
// NOTE: snippet
for (i = pre.size() -1 ; i > 0; i--) { 

   pre.set( i ,pre.get(i) + pre.get(i-1) ); 

 } 

pre.add(1);

// time :O(n^2), Space:O(k)
public List generate(int k)
{
     List pre = new ArrayList();
     // validate the input
     // NOTE: first row refers to k = 0
     if ( k < 0 )
     { 
         return pre;
     }
      


     pre.add(1);



      
     for(int i = 1 ; i <= k;k++)
     {


         // NOTE: forward iterating would race 
         //for (int i = 0 ; i < pre.size() ; i ++ )
         // NOTE: 3(idx=2) = 1(idx=2) + 2(idx=1) 
         for (i = pre.size() -1 ; i > 0; i--)
         {
             pre.set( i  ,pre.get(i) + pre.get(i-1)  ); 
         }
         pre.add(1);



     }
    
     return pre;
}

// NOTE: 3(idx=2) =   2(idx=1) + 1(idx=2) 
for ( i = pre.size()-2; i >=0 ;i--)
{
    pre.set(i+1,  pre.get(i) + pre.get(i+1)   );
}

3. Similar Ones:
Pascal's Triangle I