50 DSA-Questions: #10, #11

#10. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. (The container has rectangle shape)

public class Exercise10 {
    // private final Integer[] HEIGHT = {1,8,6,2,5,4,8,3,7};
    // private final Integer[] HEIGHT = {1,2,4,7,9};
    // private final Integer[] HEIGHT = {6, 2, 0, 20, 1};
    // private final Integer[] HEIGHT = {1, 1, 10, 9, 1, 1};
    // private final Integer[] HEIGHT = {14, 8, 5, 3, 3, 2, 1};
    private final Integer[] HEIGHT = {100, 1, 102};

    private int getArea(int i, int j) {
        return Math.abs(i - j) * Math.min(HEIGHT[i], HEIGHT[j]);
    }

    private void solveBruteForce() {
        int indexI = 0, indexJ = 0;
        int maxArea = 0;
        for (int i=0; i<HEIGHT.length - 1; i++) {
            for (int j=1; j<HEIGHT.length; j++) {
                int area = getArea(i, j);
                if (area > maxArea) {
                    maxArea = area;
                    indexI = i;
                    indexJ = j;
                }
            }
        }
        System.out.println("[Brut] maxArea = " + maxArea + ", i = " + indexI + ", j = " + indexJ);
        // O(n^2)
    }

    private void solveEasy() {
        // sort lines by y desc, x desc;
        // find first common element going from i=0 and from j=0 towards the rest of the arrays;
        // for that element find its best pair;

        List<Integer> unsortedArray = Arrays.asList(HEIGHT);
        List<Integer> sortedArray = Arrays.asList(HEIGHT.clone());
        sortedArray.sort((i1, i2) -> i2 - i1 != 0 ? i2 - i1 : unsortedArray.indexOf(i2) - unsortedArray.indexOf(i1));

        int indexElement = 0;
        Set<String> keys = new HashSet<>();
        for (int i=0; i<HEIGHT.length; i++) {
            String key1 = i + "," + unsortedArray.get(i);
            String key2 = unsortedArray.indexOf(sortedArray.get(i)) + "," + sortedArray.get(i);
            if (keys.contains(key1) || key1.equals(key2)) {
                indexElement = i;
                break;
            }
            if (keys.contains(key2)) {
                indexElement = unsortedArray.indexOf(sortedArray.get(i));
                break;
            }
            keys.add(key1);
            keys.add(key2);
        }

        int maxArea = 0;
        int secondIndex = 0;
        for (int i=0; i<HEIGHT.length; i++) {
            int area = getArea(indexElement, i);
            if (area > maxArea) {
                maxArea = area;
                secondIndex = i;
            }
        }

        System.out.println("[Easy] maxArea = " + maxArea + ", i = " + indexElement + ", j = " + secondIndex);
        // O(n log n) due to sorting
    }

    public static void main(String args[]) {
        new Exercise10().solveBruteForce();
        new Exercise10().solveEasy();
    }
}

#11. Set Matrix Zeroes

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's. You must do it in place (means no extra memory should be used -> space complexity O(1)).

public class Exercise11 {
    private final Integer[][] MATRIX = {{1,1,1},{1,0,1},{1,1,1}}; // 1 <= m, n <= 200
    // private final Integer[][] MATRIX = {{1,0,1,1},{1,1,1,1},{1,1,1,0}};
    // private final Integer[][] MATRIX = {{1,1,2,4},{3,1,9,3},{7,0,8,1}};

    private void showMatrix(long mask, String label) {
        System.out.println(label);
        for (int i=0; i< MATRIX.length; i++) {
            System.out.print("[ ");
            for (int j=0; j<MATRIX[i].length; j++) {
                int elem = getBitAt(mask, i, j) > 0 ? MATRIX[i][j] : 0;
                System.out.print(elem + " ");
            }
            System.out.println("]");
        }
        System.out.println();
    }

    private long clearBitAt(long mask, int i, int j) {
        int pos = i * MATRIX[0].length + j;
        int clearMask = ~ (1 << pos);
        return clearMask & mask;
    }

    private long getBitAt(long mask, int i, int j) {
        int pos = i * MATRIX[0].length + j;
        return mask & (1 << pos);
    }

    private long setZerosFor(long mask, int posI, int posJ) {
        for (int i=0; i<MATRIX.length; i++) {
            mask = clearBitAt(mask, i, posJ);
        }
        for (int j=0; j<MATRIX[0].length; j++) {
            mask = clearBitAt(mask, posI, j);
        }
        return mask;
    }

    private void solve() {
        // matrix has a initial mask (number), where each bit is 0 if element = 0, else 1
        long mask = (long) Math.pow(2, MATRIX.length * MATRIX[0].length) - 1;
        showMatrix(mask, "Initial:");

        for (int i=0; i<MATRIX.length; i++) {
            for (int j=0; j<MATRIX[0].length; j++) {
                if (MATRIX[i][j] == 0) {
                    mask = setZerosFor(mask, i , j);
                }
            }
        }
        showMatrix(mask, "After Zeros set:");

        // O(1) space complexity
    }

    public static void main(String args[]) {
        new Exercise11().solve();
    }
}