[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

[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)