Leetcode 296 Best Meeting Point

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0), (0,4), and (2,2):

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

Solution 1: best meeting point of one-dimension is at the middle point. for 2D is the same. find the mid-x and mid-y, it is the meeting place.

 public class Solution {  
   public int minTotalDistance(int[][] grid) {  
     int m=grid.length;  
     if (m==0) return 0;  
     int n=grid[0].length;  
     int[] row=new int[n];  
     int[] col=new int[m];  
     for (int i=0;i<m;i++) {  
       for (int j=0; j<n;j++) {  
         if (grid[i][j]==1) {  
           col[i]++;  
           row[j]++;  
         }  
       }  
     }  
     int res=0;  
     int i=0, j=n-1;  
     while (i<j) {  
       int min=Math.min(row[i],row[j]);  
       res+=min*(j-i);  
       if ((row[i]-=min)==0) i++;  
       if ((row[j]-=min)==0) j--;  
     }  
     i=0; j=m-1;  
     while (i<j) {  
       int min=Math.min(col[i],col[j]);  
       res+=min*(j-i);  
       if ((col[i]-=min)==0) i++;  
       if ((col[j]-=min)==0) j--;  
     }  
     return res;  
   }  
 }  

Leetcode 253 Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

Solution 1: Use min PQ to store the meeting rooms end time. If new meeting start time greater or equal than least element, update it. If not open a new meeting room. Report the pq size at the end. O(nlogn) complexity.

 public class Solution {  
   class CompStart implements Comparator<Interval> {  
     @Override  
     public int compare(Interval a, Interval b) {  
       return a.start-b.start;  
     }  
   }  
   public int minMeetingRooms(Interval[] intervals) {  
     int n=intervals.length;  
     Arrays.sort(intervals, new CompStart());  
     PriorityQueue<Integer> pq=new PriorityQueue<>();  
     for (int i=0; i<n; i++) {  
       if (i>0 && intervals[i].start>=pq.peek()) pq.poll();  
       pq.add(intervals[i].end);  
     }  
     return pq.size();  
   }  
 }  

Solution 2: two sorted array of start time and end time. Two pointers to iterator start array and end array. Iterate the time line, the current time active meeting is num of start minus num of end. Since need sort, still O(nlogn) solution, but fast than solution 1.

 public class Solution {  
   public int minMeetingRooms(Interval[] intervals) {  
     int n=intervals.length;  
     int[] start=new int[n];  
     int[] end=new int[n];  
     for (int i=0; i<n; i++) {  
       start[i]=intervals[i].start;  
       end[i]=intervals[i].end;  
     }  
     Arrays.sort(start);  
     Arrays.sort(end);  
     int i=0, j=0, res=0;  
     while (i<n) {  
       if (start[i]<end[j]) i++;  
       else if (start[i]>end[j]) j++;  
       else {  
         i++;  
         j++;  
       }  
       res=Math.max(res,i-j);  
     }  
     return res;  
   }  
 }  

Leetcode 252 Meeting Rooms

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

Solution 1: Sort the interval, make sure there is no overlap.

 public class Solution {  
   class InterComp implements Comparator<Interval> {  
     @Override  
     public int compare(Interval a, Interval b) {  
       return a.start-b.start;  
     }  
   }  
   public boolean canAttendMeetings(Interval[] intervals) {  
     int n=intervals.length;  
     Arrays.sort(intervals,new InterComp());  
     for (int i=1; i<n; i++) {  
       if (intervals[i].start<intervals[i-1].end) return false;  
     }  
     return true;  
   }  
 }  

Leetcode 215 Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

Solution 1: Sort the array and return nums[k-1], it is O(nlogn) time and O(1) space.

Solution 2: QuickSort partition. O(n) best and O(n^2) worst. Can be shuffle to grantee the performance

 public class Solution {  
   public int findKthLargest(int[] nums, int k) {  
     k--;  
     int lo=0, hi=nums.length-1;  
     while (lo<=hi) {  
       int[] p=partition(nums,lo,hi);  
       if (k>p[1]) lo=p[1]+1;  
       else if (k<p[0]) hi=p[0]-1;  
       else return nums[k];  
     }  
     return 0;  
   }  
   private int[] partition(int[] nums, int lo, int hi) {  
     int v=nums[lo];  
     int j=lo, i=lo+1, k=hi;  
     while (i<=k) {  
       if (nums[i]==v) i++;  
       else if (nums[i]<v) swap(nums,i,k--);  
       else swap(nums,i++,j++);  
     }  
     return new int[]{j,k};  
   }  
   private void swap(int[] nums, int i, int j) {  
     int temp=nums[i];  
     nums[i]=nums[j];  
     nums[j]=temp;  
   }  
 }  

Leetcode 210 Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Solution 1: build the graph, then DFS to judge if there is loop. If not topo sort.

 public class Solution {  
   public int[] findOrder(int numCourses, int[][] prerequisites) {  
     int V=numCourses;  
     List<Integer>[] adj=new List[V];  
     for (int v=0; v<V; v++) adj[v]=new LinkedList<>();  
     for (int i=0; i<prerequisites.length; i++) adj[prerequisites[i][1]].add(prerequisites[i][0]);  
     boolean[] marked=new boolean[V];  
     boolean[] onStack=new boolean[V];  
     boolean[] hasCycle=new boolean[1];  
     Deque<Integer> stack=new LinkedList<>();  
     for (int v=0; v<V; v++)  
       if (!marked[v]) dfs(v,adj,V,marked,onStack,hasCycle,stack);  
     if (hasCycle[0]) return new int[0];  
     int[] res=new int[V];  
     for (int i=0; i<V; i++) res[i]=stack.pop();  
     return res;  
   }  
   private void dfs(int v, List<Integer>[] adj, int V, boolean[] marked, boolean[] onStack, boolean[] hasCycle, Deque<Integer> stack) {  
     marked[v]=true;  
     onStack[v]=true;  
     for (int w:adj[v]) {  
       if (hasCycle[0]) return;  
       else if (!marked[w]) dfs(w,adj,V,marked,onStack,hasCycle,stack);  
       else if(onStack[w]) hasCycle[0]=true;  
     }  
     stack.push(v);  
     onStack[v]=false;  
   }  
 }  

Leetcode 179 Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Solution 1: use the comparator interface

 public class Solution {  
   class MSBcompare implements Comparator<String> {  
     @Override  
     public int compare(String a, String b){  
       return (a+b).compareTo(b+a);  
     }  
   }  
   public String largestNumber(int[] nums) {  
     int n=nums.length;  
     String[] s=new String[n];  
     for (int i=0; i<n; i++) s[i]=String.valueOf(nums[i]);  
     Arrays.sort(s,new MSBcompare());  
     StringBuilder sb=new StringBuilder();  
     for (int i=n-1; i>=0; i--) sb.append(s[i]);  
     int i=0;  
     while (sb.charAt(i)=='0' && i<n-1) i++;  
     return sb.substring(i);  
   }  
 }  

Leetcode 164 Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Solution 1: As request for O(n) time and O(n) space. Use bracket. The max gap must be greater than gap=(max-min)/(n-1). So we can create n bracket: [min,min+gap), [min+gap,min+2gap).... the result must be value between brackets instead of within bracket. So first step is allocate all numbers into the bracket, then iterate the bracket to find max inter-bracket value.

 public class Solution {  
   public int maximumGap(int[] nums) {  
     int n=nums.length;  
     if (n<2) return 0;  
     int max=Integer.MIN_VALUE, min=Integer.MAX_VALUE;  
     for (int x: nums) {  
       max=Math.max(max,x);  
       min=Math.min(min,x);  
     }  
     int gap=(max-min)/(n-1);  
     if (gap*(n-1)<max-min) gap++;  
     if (gap==0) return 0;  
     int[] minBracket=new int[n];  
     int[] maxBracket=new int[n];  
     Arrays.fill(minBracket, Integer.MAX_VALUE);  
     Arrays.fill(maxBracket, Integer.MIN_VALUE);  
     for (int x: nums) {  
       int i=(x-min)/gap;  
       maxBracket[i]=Math.max(maxBracket[i],x);  
       minBracket[i]=Math.min(minBracket[i],x);  
     }  
     int res=0;  
     int lo=maxBracket[0];//bracket[0] is not blank, at least min will be there  
     for (int i=1; i<n; i++) {  
       if (maxBracket[i]!=Integer.MIN_VALUE) {  
         res=Math.max(res,minBracket[i]-lo);  
         lo=maxBracket[i];  
       }  
     }  
     return res;  
   }  
 }  

Leetcode 148 Sort List

Sort a linked list in O(n log n) time using constant space complexity.
Solution 1: use quick sort partition and top down merge sort can get O(n log n) but need O(log n) space as in system stack. The only solution of O(1) space is bottom up merge sort.

 public class Solution {  
   public ListNode sortList(ListNode head) {  
     int n=0;  
     ListNode p=head;  
     while (p!=null) {n++; p=p.next;}  
     ListNode dummy=new ListNode(0);  
     dummy.next=head;  
     for (int size=1; size<n; size*=2) {  
       ListNode i=dummy;  
       while (true) {  
         ListNode j=i;  
         for (int k=0; k<size && j!=null; k++) j=j.next;  
         if (j==null || j.next==null) break;  
         ListNode t=j;  
         for (int k=0; k<size && t!=null; k++) t=t.next;  
         ListNode p1=i.next, p2=j.next;  
         j.next=null;  
         if (t!=null) {  
           ListNode temp=t.next;  
           t.next=null;  
           t=temp;  
         }  
         while (p1!=null || p2!=null) {  
           if (p1==null) {i.next=p2; i=i.next; p2=p2.next; }  
           else if (p2==null) {i.next=p1; i=i.next; p1=p1.next;}  
           else if (p1.val<p2.val) {i.next=p1; i=i.next; p1=p1.next;}  
           else {i.next=p2; i=i.next; p2=p2.next;}  
         }  
         if (t==null) break;  
         i.next=t;  
       }  
     }  
     return dummy.next;  
   }  
 }  

Leetcode 147 Insertion Sort List

Sort a linked list using insertion sort.
Solution 1: insertion sort, use dummy node.

 public class Solution {  
   public ListNode insertionSortList(ListNode head) {  
     ListNode dummy=new ListNode(0);  
     dummy.next=head;  
     ListNode i=dummy;  
     while (i.next!=null) {  
       if (i==dummy || i.next.val>=i.val) i=i.next;  
       else {  
         ListNode j=dummy;  
         while (j.next.val<i.next.val) j=j.next;  
         ListNode p=i.next;  
         i.next=p.next;  
         p.next=j.next;  
         j.next=p;  
       }  
     }  
     return dummy.next;  
   }  
 }  

Leetcode 75 Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

Solution 1: use quick sort 3 way partition, time complexity is O(n);

 public class Solution {  
   public void sortColors(int[] nums) {  
     int n=nums.length;  
     int i=0, j=-1, k=n-1;//quick sort 3-way partition  
     while (i<=k) {  
       if (nums[i]==1) i++;  
       else if (nums[i]==0) swap(nums,i++,++j);  
       else swap(nums,i,k--);  
     }  
   }  
   private void swap(int[] nums, int i, int j) {  
     int temp=nums[i];  
     nums[i]=nums[j];  
     nums[j]=temp;  
   }  
 }  

Leetcode 57 Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Solution 1: O(n) solution

 public class Solution {  
   public List<Interval> insert(List<Interval> intervals, Interval newInterval) {  
     int i=0, n=intervals.size();  
     List<Interval> res=new ArrayList<>();  
     while (i<n && intervals.get(i).end<newInterval.start) res.add(intervals.get(i++));  
     while (i<n && intervals.get(i).start<=newInterval.end) {  
       newInterval.start=Math.min(newInterval.start,intervals.get(i).start);  
       newInterval.end=Math.max(newInterval.end,intervals.get(i).end);  
       i++;  
     }  
     res.add(newInterval);  
     while (i<n) res.add(intervals.get(i++));  
     return res;  
   }  
 }  

Leetcode 56 Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution 1: Use compactor interface to sort with start. if next interval is not overlap then just add to result otherwise update the end value use max of current end and next end.

 public class Solution {  
   class IntervalCompare implements Comparator<Interval> {  
     public int compare(Interval a, Interval b) {  
       return a.start-b.start;  
     }  
   }  
   public List<Interval> merge(List<Interval> intervals) {  
     IntervalCompare iComp=new IntervalCompare();  
     Collections.sort(intervals,iComp);  
     List<Interval> res=new ArrayList<>();  
     for (Interval x: intervals) {  
       int n=res.size();  
       if (n==0 || res.get(n-1).end<x.start) res.add(x);  
       else if (res.get(n-1).end<x.end) res.get(n-1).end=x.end;  
     }  
     return res;  
   }  
 }  

Leetcode 31 Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Solution 1:  use 1269753 as example, start from last number, moving ahead and find last num in increasing order. 126|9753: it is 9 in this case. Then sort from 9 to end. It became: 126|3579. Next step is to find the number just greater than 6 which is 7, swap them to be final answer: 1273569.

 public class Solution {  
   public void nextPermutation(int[] nums) {  
     int n=nums.length;  
     if (n<=1) return;  
     int i=n-1;  
     while (i>0 && nums[i-1]>=nums[i]) i--;  
     Arrays.sort(nums,i,n);  
     if (i==0) return;  
     int j=i-1;  
     while (nums[i]<=nums[j]) i++;  
     int temp=nums[i];  
     nums[i]=nums[j];  
     nums[j]=temp;  
   }  
 }