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)).

class Solution {
    void setZeroes(int[][] matrix) {
        boolean row0has0 = false;
        for (int j=0; j<matrix[0].length; j++) {
            if (matrix[0][j] == 0) {
                row0has0 = true;
                break;
            }
        }
        boolean col0has0 = false;
        for (int i=0; i<matrix.length; i++) {
            if (matrix[i][0] == 0) {
                col0has0 = true;
                break;
            }
        }
        
        // set matrix[0][j] = 0 when col j has a zero
        // set matrix[i][0] = 0 when row i has a zero
        for (int i=0; i<matrix.length; i++) {
            for (int j=0; j<matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        // set zeroes in matrix by checking which row/col is set to zero
        for (int i=1; i<matrix.length; i++) {
            if (matrix[i][0] == 0) {
                setZerosRow(matrix, i);
            }
        }
        for (int j=1; j<matrix[0].length; j++) {
            if (matrix[0][j] == 0) {
                setZerosCol(matrix, j);
            }
        }
        // finally set row/col 0 to zero if previously checked
        if (row0has0) {
            for (int j=0; j<matrix[0].length; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0has0) {
            for (int i=0; i<matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
    }
    private void setZerosCol(int[][] matrix, int posJ) {
        for (int i=1; i<matrix.length; i++) {
            matrix[i][posJ] = 0;
        }
    }
    private void setZerosRow(int[][] matrix, int posI) {
        for (int j=1; j<matrix[0].length; j++) {
            matrix[posI][j] = 0;
        }
    }
}