The val field of ListNode is of type int instead of type char.
SeleniteXin
@SeleniteXin
Posts made by SeleniteXin

RE: The test cases are not complete. Or, those O(n) time and O(1) space solutions won't work

RE: This is my java code, but it doesn't work. Can anybody help me?
Level order traversal works in time O(N), try to use binary search to reduce the complexity to O(logN)

Java 570ms Heap+BST and 430ms DivideandConquer Solution with Explanation
The main idea of the solutions is to keep an eye on the max height of buildings, and whenever the max height changes, we add it to a list.
For the Heap+BST approach, it's easier if we store both the starting point of a building
[Li, Hi]
and the ending point[Ri, Hi]
in a PriorityQueue. Therefore for N buildings, we will have 2N points in the PriorityQueue. Its order should be based on 1) xcoordinates and breaking ties with 2) height. At the same time, we need to keep a TreeMap which acts like a histogram of all current heights so that whenever we visit a ending point, we know what the updated max height is going to be. As many already pointed out,remove(object)
operation in BST is O(logN) whereas in PriorityQueue it's O(N), so we cannot use a PriorityQueue to keep track of the heights.I actually spent hours and hours in handling corner cases where multiple starting points and ending points appeared with the same xcoordinate, For example, if the input is:
[[1,2,1], [1,2,2], [1,2,3], [1,2,4], [2,3,2], [2,3,4]]
The result should be
[[1,4], [3,0]].
A trick to make the code simpler without worrying about those corner cases is to make sure that, in the PriorityQueue, when multiple points with the same xcoord occur, 1) always keep starting points in front of the ending points, 2) keep the starting points in descending order of its heights (so that you won't keep updating the max height at the same point) and 3) keep the ending points in ascending order of its heights (so that you won't update the max height to the next largest height after you removed the max height ending point).public class Solution { public List<int[]> getSkyline(int[][] buildings) { PriorityQueue<Point> points=new PriorityQueue<Point>(new Comparator<Point>(){ public int compare(Point a, Point b){ if(a.x!=b.x) return a.xb.x; return a.yb.y; } }); TreeMap<Integer, Integer> heights=new TreeMap<Integer, Integer>(); ArrayList<int[]> result=new ArrayList<>(); for(int[] building: buildings){ points.add(new Point(building[0], building[2])); points.add(new Point(building[1], building[2])); } heights.put(0, 1); int maxHeight=0; while(!points.isEmpty()){ Point point=points.poll(); if(point.y<0){ if(!heights.containsKey(point.y)) heights.put(point.y, 0); heights.put(point.y, heights.get(point.y)+1); } else{ heights.put(point.y, heights.get(point.y)1); if(heights.get(point.y)==0) heights.remove(point.y); } int currentMax=heights.lastEntry().getKey(); if(currentMax!=maxHeight){ result.add(new int[]{point.x, currentMax}); maxHeight=currentMax; } } return result; } private class Point{ int x; int y; public Point(int x, int y){ this.x=x; this.y=y; } } }
For the divideandconquer approach, we have to think about how to merge two lists of "key points" into a single list. It's pretty much like mergesort: we compare the first unvisited key points in both lists, and visit the point with a lower xcoordinate. Then we update the max height at that xcoordinate based on the height of the point. In order to do this, we need to keep two variables,
leftMax
andrightMax
which stores the current max heights from 2 lists.public class Solution { public List<int[]> getSkyline(int[][] buildings) { return getSkyline(buildings, 0, buildings.length1); } private ArrayList<int[]> getSkyline(int[][] buildings, int lo, int hi){ ArrayList<int[]> result=new ArrayList<>(); if(lo>hi) return result; if(lo==hi){ result.add(new int[]{buildings[lo][0], buildings[lo][2]}); result.add(new int[]{buildings[lo][1], 0}); return result; } int mid=(lo+hi)/2; ArrayList<int[]> left=getSkyline(buildings, lo, mid); ArrayList<int[]> right=getSkyline(buildings, mid+1, hi); int leftMax=0, rightMax=0, max=0; for(int i=0, j=0; i<left.size()j<right.size(); ){ int currentMax=0; if(i<left.size()&&j<right.size()&&left.get(i)[0]==right.get(j)[0]){ leftMax=left.get(i)[1]; rightMax=right.get(j)[1]; currentMax=Math.max(leftMax, rightMax); if(currentMax!=max){ result.add(new int[]{left.get(i)[0], currentMax}); max=currentMax; } i++; j++; } else if(j>=right.size()i<left.size()&&j<right.size()&&left.get(i)[0]<right.get(j)[0]){ leftMax=left.get(i)[1]; currentMax=Math.max(leftMax, rightMax); if(currentMax!=max){ result.add(new int[]{left.get(i)[0], currentMax}); max=currentMax; } i++; } else if(i>=left.size()i<left.size()&&j<right.size()&&left.get(i)[0]>right.get(j)[0]){ rightMax=right.get(j)[1]; currentMax=Math.max(leftMax, rightMax); if(currentMax!=max){ result.add(new int[]{right.get(j)[0], currentMax}); max=currentMax; } j++; } } return result; } }

RE: Java O(N) and O(NlogN) Solution with explanation
No, it still got TLE for the case in which s==120331635.

RE: Java O(N) and O(NlogN) Solution with explanation
Are you talking about getting the min length from case 3)? Yes, it takes O(N) time each recursion, but there are only O(logN) recursions.

Java O(N) and O(NlogN) Solution with explanation
There are lots of explanations for the following O(N) approach and I think the code is selfexplanatory:
public class Solution { public int minSubArrayLen(int s, int[] nums) { int lo=0, hi=0, sum=0, minLen=nums.length; boolean hasMin=false; while(hi<nums.length){ while(sum<s&&hi<nums.length) sum+=nums[hi++]; while(sumnums[lo]>=s) sum=nums[lo++]; if(!hasMin&&sum>=s) hasMin=true; minLen=Math.min(minLen, hilo); sum=nums[lo++]; } return hasMin? minLen:0; } }
For the O(NlogN) approach, we have to use divideandconquer. Divide the array into 2 halves at the middle and exluding the middle element, the left subarray will have indices from
0
tomiddle1
, and the right subarray will have indices frommiddle+1
tonums.length1
.Now the mininum length can come from 3 places: 1) the left subarray 2) the right subarray and 3) the subarray which contains the
middle
element. For case 1) and 2), we can call recursively to get the min lengths. However, for 3), we need to apply the O(N) approach above (so the O(NlogN) approach is slower, uses more space and harder to code......) and make sure that we always include themiddle
element. The complexity is T(N)=2T(N/2)+O(N) so T(N)=O(NlogN). My O(NlogN) approach will lead to TLE for the largest test case, but I tested it myself using some small test cases. Let me know if you find any errors and thanks in advance.public class Solution { public int minSubArrayLen(int s, int[] nums) { int minLen=minSubArrayLen(s, nums, 0, nums.length1); return minLen==Integer.MAX_VALUE? 0:minLen; } private int minSubArrayLen(int s, int[] nums, int lo, int hi){ if(hi<lohi==lo&&nums[hi]<s) return Integer.MAX_VALUE; if(hi==lo&&nums[hi]>=s) return 1; int mid=(lo+hi)/2; int left=minSubArrayLen(s, nums, lo, mid1), right=minSubArrayLen(s, nums, mid+1, hi); int sum=nums[mid], start=mid, end=mid+1, minLen=Integer.MAX_VALUE; while(sum<s&&start>0) sum+=nums[start]; if(sum>=s) minLen=Math.min(minLen, endstart); while(start<=mid){ sum=nums[start++]; while(sum<s&&end<nums.length) sum+=nums[end++]; if(sum>=s) minLen=Math.min(minLen, endstart); } return Math.min(minLen, Math.min(left, right)); } }

RE: Why the "binary search" tag?
Let's say we first try minHP=Integer.MAX_VALUE, and use DP to check whether the knight can save the princess. If the answer is yes, then we try another minHP=Integer.MAX_VALUE/2, and if again the knight can save the princess, the last value we tried (Integer.MAX_VALUE) must be larger than needed.

RE: Modified question: find the mimimum difference instead of the maximum difference?
Yes if you believe radix sort is linear. I couldn't think of an algorithm similar to what's presented in the solution (i.e. bucket sort), but maybe someone can come up with one.

Relatively short Iterative Mergesort Java Solution
/* A small trick used in the following code is that, in order to sort the following sublist of length 4, e.g. Start > 5 > 6 > 2 > 8 >Tail (assume list is already sorted under length 2) I break the sublist into 3 parts: 1) Start > Tail 2) 5 > 6 > Null 3) 2 > 8 > Null And then try to insert nodes from sublists 2) and 3) into 1). */ public class Solution { public ListNode sortList(ListNode head) { ListNode dummy=new ListNode(0); dummy.next=head; int length=0; for(ListNode current=head; current!=null; current=current.next) length++; for(int len=2;len/2<=length; len*=2){ ListNode start=dummy, mid=dummy, end=dummy; while(start.next!=null){ for(int i=0;i<len/2;i++){ mid= mid.next==null? mid:mid.next; if(end.next==null) continue; end= end.next.next==null? end.next:end.next.next; } ListNode left=start.next, right=mid.next, next=end.next; start.next=next; mid.next=null; end.next=null; while(left!=nullright!=null){ if(right==nullleft!=null&&right!=null&&left.val<right.val){ ListNode temp=left.next; left.next=start.next; start.next=left; left=temp; } else if(left==nullleft!=null&&right!=null&&left.val>=right.val){ ListNode temp=right.next; right.next=start.next; start.next=right; right=temp; } start=start.next; } mid=start; end=start; } } return dummy.next; } }

RE: If there is only one node with value 1, return 1 or 0?
Oops you are absolutely right, thanks a bunch!