careercup / CtCI-6th-Edition

Cracking the Coding Interview 6th Ed. Solutions
11.33k stars 4.41k forks source link

1.8 solved with O(n) instead of O(n^2) #206

Closed coditori closed 4 years ago

coditori commented 4 years ago

For a MxN matrix it will be:

    private static int[][] setZeros(int[][] arr)
        boolean[] checked = new boolean[arr.length]; // prevents the row to be doubled checked
        int max = Math.max(arr.length, arr[0].length);
        int min = Math.min(arr.length, arr[0].length);

        for (int i = 0; i < arr.length * arr[0].length; i++) {
            int a = i / max;
            var b = i % min;
            if (arr[a][b] == 0 & !checked[a]) {
                arr[a] = new int[arr[0].length];
                checked[a] = true;
                i += arr[0].length - 1 - a; // jump to the next row
            }
        }
        return arr;
    }