[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