Faster than 100% (1ms). O(mn) time, O(1) space... self explained.. NERF THIS!!!


  • 0
    B

    the 2D problem can be broken down into 2*1D problems.
    for each sub problem. use 2 pointers starting from the 2 ends to pair up cells whose values are '1'.

    My first version (faster than 80%)

    public class Solution {
        public int minTotalDistance(int[][] grid) {
            return vDistance(grid) + hDistance(grid);
        }
        
        private static int vDistance(int[][] grid) {
            int rows = grid.length;
            int cols = rows != 0 ? grid[0].length : 0;
            
            int count = 0;
            
            int startRow = 0;
            int endRow = rows - 1;
            int startCol = 0;
            int endCol = 0;
            while(startRow < endRow) {
                while(startCol < cols) {
                    if(grid[startRow][startCol] == 0) startCol++;
                    else break;
                }
                while(endCol < cols) {
                    if(grid[endRow][endCol] == 0) endCol++;
                    else break;
                }
                if(startCol < cols && endCol < cols && grid[startRow][startCol] == 1 && grid[endRow][endCol] == 1) {
                    count += (endRow - startRow);
                    startCol++;
                    endCol++;
                }
                if(startCol == cols) {
                    startRow++;
                    startCol = 0;
                }
                if(endCol == cols) {
                    endRow--;
                    endCol = 0;
                }
            }
            return count;
        }
        
        private static int hDistance(int[][] grid) {
            int rows = grid.length;
            int cols = rows != 0 ? grid[0].length : 0;
            
            int count = 0;
            
            int startCol = 0;
            int endCol = cols - 1;
            int startRow = 0;
            int endRow = 0;
            while(startCol < endCol) {
                while(startRow < rows) {
                    if(grid[startRow][startCol] == 0) startRow++;
                    else break;
                }
                while(endRow < rows) {
                    if(grid[endRow][endCol] == 0) endRow++;
                    else break;
                }
                if(startRow < rows && endRow < rows && grid[startRow][startCol] == 1 && grid[endRow][endCol] == 1) {
                    count += (endCol - startCol);
                    startRow++;
                    endRow++;
                }
                if(startRow == rows) {
                    startCol++;
                    startRow = 0;
                }
                if(endRow == rows) {
                    endCol--;
                    endRow = 0;
                }
            }
             return count;
        }
    }
    

    My second version (faster than 76%): a compact version that has no dup code.

    public class Solution {
        public int minTotalDistance(int[][] grid) {
          return distance(grid, true) + distance(grid, false);
        }
    
        private static int distance(int[][] grid, boolean vertical) {
          int rows = grid.length;
          int cols = rows != 0 ? grid[0].length : 0;
    
          int majorMax = vertical ? rows : cols;
          int minorMax = vertical ? cols : rows;
    
          int count = 0;
    
          int startMajor = 0;
          int endMajor = majorMax - 1;
          int startMinor = 0;
          int endMinor = 0;
          while(startMajor < endMajor) {
            while(startMinor < minorMax) {
              if(grid[vertical ? startMajor : startMinor][vertical ? startMinor : startMajor] == 0) startMinor++;
              else break;
            }
            while(endMinor < minorMax) {
              if(grid[vertical ? endMajor : endMinor][vertical ? endMinor : endMajor] == 0) endMinor++;
              else break;
            }
            if(startMinor < minorMax && endMinor < minorMax
                 && grid[vertical ? startMajor : startMinor][vertical ? startMinor : startMajor] == 1
                 && grid[vertical ? endMajor : endMinor][vertical ? endMinor : endMajor] == 1) {
              count += (endMajor - startMajor);
              startMinor++;
              endMinor++;
            }
            if(startMinor == minorMax) {
              startMajor++;
              startMinor = 0;
            }
            if(endMinor == minorMax) {
              endMajor--;
              endMinor = 0;
            }
          }
          return count;
        }
    }
    

    OK. NOW. If you understand the 2 above. You should be able to understand the ultimate version which is the fastest of all (beats 100% by 1/Sep/2016):

    public class Solution {
    
        public int minTotalDistance(int[][] grid) {
          return distance(grid, true) + distance(grid, false);
        }
    
        private static int distance(int[][] grid, boolean vertical) {
          int rows = grid.length;
          int cols = rows != 0 ? grid[0].length : 0;
    
          int majorMax = vertical ? rows : cols;
          int minorMax = vertical ? cols : rows;
    
          int count = 0;
    
          int startMajor = 0;
          int endMajor = majorMax - 1;
          int startMinor = 0;
          int endMinor = 0;
          while(startMajor < endMajor) {
            while(startMajor < endMajor && grid[vertical ? startMajor : startMinor][vertical ? startMinor : startMajor] == 0) {
              if(++startMinor == minorMax) {
                startMajor++; startMinor = 0;
              }
            }
            while(startMajor < endMajor && grid[vertical ? endMajor : endMinor][vertical ? endMinor : endMajor] == 0) {
              if(++endMinor == minorMax) {
                endMajor--; endMinor = 0;
              }
            }
            count += (endMajor - startMajor);
            if(++startMinor == minorMax) {
              startMajor++; startMinor = 0;
            }
            if(++endMinor == minorMax) {
              endMajor--; endMinor = 0;
            }
          }
          return count;
        }
    }
    

  • 0
    L

    Thanks for sharing! Could you please explain why pairing up cells actually gives the shortest distance?


  • 1
    B

    So important thing to know is:

    between 2 people, the total distance to travel is fixed no matter where you place the meeting point (assuming that is placed between the 2 people):

    A--x----B: total distance = 2 + 4 = 6
    A---x---B: total distance = 3 + 3 = 6
    A----x--B: total distance = 4 + 2 = 6

    travel distance = pos(B) - pos(A)
    whenever we find a pair like this, we will need to do

    count += pos(B) - pos(A)
    

    If you scale this up, the problem effectively becomes "finding pairs". Whenever you find a pair, increment the count.


  • 0
    L
    This post is deleted!

  • 0
    L

    @beijunyi said in Faster than 100% (1ms). O(mn) time, O(1) space... self explained.. NERF THIS!!!:

    So important thing to know is:

    between 2 people, the total distance to travel is fixed no matter where you place the meeting point (assuming that is placed between the 2 people):

    A--x----B: total distance = 2 + 4 = 6
    A---x---B: total distance = 3 + 3 = 6
    A----x--B: total distance = 4 + 2 = 6

    travel distance = pos(B) - pos(A)
    whenever we find a pair like this, we will need to do

    count += pos(B) - pos(A)
    

    If you scale this up, the problem effectively becomes "finding pairs". Whenever you find a pair, increment the count.

    Brilliant! Thanks.

    After taking care of the horizontal case, I just transpose the grid and do it again to simulate the vertical case. It gives clear code but takes more space.


Log in to reply
 

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