O(nlogn) Java solution with binary search


  • 0
    Z
    class Solution {
        public List<Integer> fallingSquares(int[][] positions) {
            List<Integer> res=new ArrayList<>();
            // sq is a list sorted by right boundary
            List<int[]> sq=new ArrayList<>();
            
            int max=0;
            for (int[] pos:positions){
                int localMax=pos[1];
                
                // find the starting position to compare through binary search
                // skip all those positions that don't overlap with the curr position
                int lo=0, hi=sq.size()-1;
                while (lo <= hi){
                    int mi=lo+(hi-lo)/2;
                    if (sq.get(mi)[0]<=pos[0]){
                        lo=mi+1;
                    }else{
                        hi=mi-1;
                    }
                }
                
                // find the localMax comparing to those overlapped positions
                for (int i=lo;i<sq.size();i++){
                    if (pos[0]+pos[1]<=sq.get(i)[0]-sq.get(i)[1]) continue;
                    localMax=Math.max(localMax, sq.get(i)[2]+pos[1]);
                }
                
                // find the position to insert the new position
                int iPos=0;
                for (iPos=lo;iPos<sq.size();iPos++)
                    if (sq.get(iPos)[0] >= pos[0]+pos[1]) break;
                sq.add(iPos, new int[]{pos[0]+pos[1], pos[1], localMax});
                
                max=Math.max(max, localMax);
                res.add(max);
            }
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.