50 DSA-Questions: #12, #13

#12. Spiral Matrix
Given an m x n matrix, return all elements of the matrix in spiral order.

class Solution {
    private enum DIRECTION {LEFT_TO_RIGHT, TOP_TO_BOTTOM, RIGHT_TO_LEFT, BOTTOM_TO_TOP};
    private void run(int[][] matrix, int i, int j, DIRECTION direction, int cycle, List<Integer> result) {
        switch (direction) {
            case LEFT_TO_RIGHT:
                if (j >= matrix[0].length-cycle) {
                    return;
                }
                for (int jj=j; jj<matrix[0].length-cycle; jj++) {
                    result.add(matrix[i][jj]);
                }
                run(matrix, i+1, matrix[0].length - cycle - 1, DIRECTION.TOP_TO_BOTTOM, cycle, result);
                break;
            case TOP_TO_BOTTOM:
                if (i >= matrix.length-cycle) {
                    return;
                }
                for (int ii=i; ii<matrix.length-cycle; ii++) {
                    result.add(matrix[ii][j]);
                }
                run(matrix, matrix.length - cycle - 1, j-1, DIRECTION.RIGHT_TO_LEFT, cycle, result);
                break;
            case RIGHT_TO_LEFT:
                boolean added = false;
                for (int jj=j; jj>=cycle; jj--) {
                    result.add(matrix[i][jj]);
                    added = true;
                }
                if (added) {
                    run(matrix, i-1, cycle, DIRECTION.BOTTOM_TO_TOP, cycle, result);
                }
                break;
            case BOTTOM_TO_TOP:
                added = false;
                for (int ii=i; ii>cycle; ii--) {
                    added = true;
                    result.add(matrix[ii][j]);
                }
                if (added) {
                    run(matrix, cycle + 1, j+1, DIRECTION.LEFT_TO_RIGHT, cycle + 1, result);
                }
                break;
        }
    }
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        run(matrix, 0, 0, DIRECTION.LEFT_TO_RIGHT, 0, result);
        return result;
    }
}

#13. Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

public class Exercise13 {
    private final int MARKER = 1000000; // marks that Mij has been updated
    // private final int[][] MATRIX = {{1,2,3},{4,5,6},{7,8,9}}; // n x n, -1000 <= matrix[i][j] <= 1000
    // private final Integer[][] MATRIX = {{1,2,3,4, 5},{6,7,8,9,0},{9,8,7,6,5}, {4,3,2,1,0}, {9,1,2,3,4}};
    // private final Integer[][] MATRIX = {{1,2,-3,-4},{0,7,8,-9},{9,8,-7,6}, {4,0,2,-1}};
    private final Integer[][] MATRIX = {{1000,2},{-1000,7}};
    private int MAX_VALUE = 1001;

    private int getCorrespondingElement90Cw(int i, int j) {
        return MATRIX[MATRIX.length-1-j][i];
    }

    private int getCorrespondingElement90Ccw(int i, int j) {
        return MATRIX[j][MATRIX.length-1-i];
    }

    private int getCorrespondingElement180(int i, int j) {
        return MATRIX[MATRIX.length-1-i][MATRIX.length-1-j];
    }

    private void solveOnlyDisplay() {
        for (int i=0; i<MATRIX.length; i++) {
            for (int j = 0; j < MATRIX[0].length; j++) {
                System.out.print(getCorrespondingElement90Cw(i,j) + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    private void addToOriginalMatrix(int valueToAdd) {
        for (int i=0; i<MATRIX.length; i++) {
            for (int j=0; j<MATRIX[0].length; j++) {
                MATRIX[i][j] = MATRIX[i][j] + valueToAdd;
            }
        }
    }

    private int getMatrixMin() {
        int minElem = MAX_VALUE;
        for (int i=0; i<MATRIX.length; i++) {
            for (int j=0; j<MATRIX[0].length; j++) {
                if (MATRIX[i][j] < minElem) {
                    minElem = MATRIX[i][j];
                }
            }
        }
        return minElem;
    }

    private void display() {
        for (int i=0; i<MATRIX.length; i++) {
            for (int j = 0; j < MATRIX[0].length; j++) {
                System.out.print(MATRIX[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    private void solveWithSaving() {
        assert(MATRIX.length == MATRIX[0].length);
        int minValue = getMatrixMin();
        if (minValue < 0) {
            addToOriginalMatrix(- minValue); // make all values positive
            MAX_VALUE -= minValue; // update max possible 
        }

        // in place saving 90 degrees clockwise matrix rotation

        // extra loading matrix: Mij = MARKER + Mij * MAX_VALUE + Mij_rotated
        for (int i=0; i<MATRIX.length; i++) {
            for (int j=0; j<MATRIX[0].length; j++) {
                int rotatedMij = getCorrespondingElement90Cw(i,j);
                if (rotatedMij >= MARKER) {
                    int originalRotatedElement = (rotatedMij - MARKER) / MAX_VALUE;
                    MATRIX[i][j] = MARKER + MATRIX[i][j] * MAX_VALUE + originalRotatedElement;
                } else {
                    MATRIX[i][j] = MARKER + MATRIX[i][j] * MAX_VALUE + rotatedMij;
                }
            }
        }

        // cleanup to get only Mij_rotated
        for (int i=0; i<MATRIX.length; i++) {
            for (int j = 0; j < MATRIX[0].length; j++) {
                MATRIX[i][j] = (MATRIX[i][j] - MARKER) % MAX_VALUE;
            }
        }

        if (minValue < 0) {
            addToOriginalMatrix(minValue); // restore original values in matrix
        }

        display();
    }

    public static void main(String args[]) {
        new Exercise13().solveOnlyDisplay();
        new Exercise13().solveWithSaving();
    }
}

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;
        }
    }
}

50 DSA-Questions: Arrays #8, #9

#8. Search in Rotated Sorted Array

Given the array nums after the possible rotation and an integer target, return the index of the target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity.

public class Exercise8 {
    private final int TARGET = 0;
    private final int[] ARRAY = {4,5,6,7,0,1,2}; // index = 4
    // private final int[] ARRAY = {10,12,0,4,5,7}; // index = 2
    // private final int[] ARRAY = {0,7,8,9,10}; // index = 0
    // private final int[] ARRAY = {3,4,6,7,8,9,0}; // index = 6
    // private final int[] ARRAY = {7, -6, -3, -2, -1, 0, 5}; // index = 5

    private void find(int leftIndex, int rightIndex) {
        if (leftIndex == rightIndex || leftIndex + 1 == rightIndex) { // one or two elements left
            int index = ARRAY[leftIndex] == TARGET ? leftIndex : (ARRAY[rightIndex] == TARGET ? rightIndex : -1);
            System.out.println("Index = " + ((index > -1) ? index : "N/A"));
            return;
        }

        int mid = leftIndex + (rightIndex - leftIndex) / 2;

        if (ARRAY[leftIndex] <= ARRAY[mid] && ARRAY[leftIndex] <= TARGET && ARRAY[mid] >= TARGET) { // search in left array
            find(leftIndex, mid);
            return;
        }

        if (ARRAY[mid+1] <= ARRAY[rightIndex] && ARRAY[mid+1] <= TARGET && ARRAY[rightIndex] >= TARGET) { // search in right array
            find(mid+1, rightIndex);
            return;
        }

        if (ARRAY[leftIndex] > ARRAY[mid] && TARGET <= ARRAY[mid]) {
            find(leftIndex, mid); // search in left array
            return;
        }

        find(mid+1, rightIndex); // search in right array
    }

    private void solve() {
        find(0, ARRAY.length - 1);
    }

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

#9. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

public class Exercise9 {
    // private final Integer[] NUMS = {-1,0,1,2,-1,-4}; // triplets [[-1,-1,2],[-1,0,1]]
    private final Integer[] NUMS = {1, 2, -3, 2, -4, 1, 3, 1, -2}; // triplets [[1,2,-3],[2,2,-4],[1,1,-2],[1,-4,3]]
    private final int TARGET_SUM = 0;

    private List<Pair<Integer, Integer>> twoSum(int targetSum, int indexThird) {
        List<Integer> list = Arrays.asList(NUMS);
        List<Pair<Integer, Integer>> result = new ArrayList<>();

        for (int i=0; i<list.size(); i++) {
            if (i == indexThird) {
                continue; // duplicate
            }

            final int element = list.get(i); // to the left
            int key = targetSum - element; // to the right
            if (list.indexOf(element) == list.lastIndexOf(key) || indexThird == list.lastIndexOf(key)) {
                continue; // duplicate
            }

            if (list.contains(key)) {
                result.add(new Pair<>(element, key));
            }
        }
        return result;
    }

    private void solve() {
        Set<String> result = new HashSet<>();
        for (int i=0; i<NUMS.length; i++) {
            int thirdElement = TARGET_SUM - NUMS[i];
            final int element = NUMS[i];
            List<Pair<Integer, Integer>> twoSums = twoSum(thirdElement, i);
            if (!twoSums.isEmpty()) {
                twoSums.forEach(twoSum -> {
                    String label = "[" +
                            getMinValue(element, twoSum.getKey(), twoSum.getValue()) + ","  +
                            getMidValue(element, twoSum.getKey(), twoSum.getValue()) + ","  +
                            getMaxValue(element, twoSum.getKey(), twoSum.getValue()) + "]";
                    result.add(label);
                });
            }
        }
        System.out.println(result);
    }

    private int getMidValue(int a, int b, int c) {
        return Math.max(Math.min(a,b), Math.min(Math.max(a,b),c));
    }

    private int getMaxValue(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }

    private int getMinValue(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }

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

50 DSA-Questions: Arrays #5, #6, #7

#5. Maximum Subarray
Given an integer array nums, find the subarray with the largest sum, and return its sum.

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        // for each element: what is the largest sum that can be obtained so far?
        // by either addition or keeping the current element
        // modify num semnification to largestSum
        int max = nums[0];
        for (int i=1; i<nums.length; i++) {
            nums[i] = Math.max(nums[i], nums[i-1]+nums[i]); // replace with * for largest product
            if (max < nums[i]) {
                max = nums[i];
            }
        }
        
        return max;
    }
}

#6. La fel ca #5, dar se cere produsul.

#7. Find the Minimum in Rotated Sorted Array

Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time.

public class Exercise7 {
    private final int[] ARRAY = {3,4,5,1,2}; // min = 1
    // private final int[] ARRAY = {10,12,0,4,5,7}; // min = 0
    // private final int[] ARRAY = {5,7,8,9,10}; // min = 5
    // private final int[] ARRAY = {3,4,6,7,8,9,2}; // min = 2

    private void find(int leftIndex, int rightIndex) {
        if (leftIndex == rightIndex || leftIndex + 1 == rightIndex) { // one or two elements left
            System.out.println("Min = " + Math.min(ARRAY[leftIndex], ARRAY[rightIndex]));
            return;
        }

        int mid = leftIndex + (rightIndex - leftIndex) / 2;
        if (ARRAY[leftIndex] <= ARRAY[mid] && ARRAY[mid] <= ARRAY[rightIndex]) { // sorted array
            System.out.println("Min = " + ARRAY[leftIndex]);
            return;
        }

        if (ARRAY[leftIndex] > ARRAY[mid]) { // search in left array
            find(leftIndex, mid);
            return;
        }

        find(mid+1, rightIndex); // search in right array
    }

    private void solve() {
        find(0, ARRAY.length - 1);
    }

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

50 DSA-Questions: Arrays #3, #4

#3. Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int element : nums) {
            if (map.containsKey(element)) {
                return true;
            }
            map.put(element, 0);
        }
        return false;
    }
}

#4. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[I]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] leftToRight = new int[nums.length];
        leftToRight[0] = 1;
        leftToRight[1] = nums[0];
        for (int i=2; i<nums.length; i++) {
            leftToRight[i] = leftToRight[i-1] * nums[i-1];
        }
        int[] rightToLeft = new int[nums.length];
        rightToLeft[nums.length-1] = 1;
        rightToLeft[nums.length-2] = nums[nums.length-1];
        for (int i=nums.length-3; i>=0; i--) {
            rightToLeft[i] = rightToLeft[i+1] * nums[i+1];
        }
        int[] result = new int[nums.length];
        for (int i=0; i<nums.length; i++) {
            result[i] = leftToRight[i] * rightToLeft[i];
        }
        
        return result;
        // O(n)
    }
}

// SAU, mai rapid:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        // left to right
        result[0] = 1;
        for (int i=1; i<nums.length; i++) {
            result[i] = result[i-1] * nums[i-1];
        }
        // right to left
        int prevFactor = 1;
        for (int i=nums.length-2; i>=0; i--) {
            int value = prevFactor * nums[i+1];
            result[i] *= value;
            prevFactor = value;
        }
        
        return result;
        // O(n)
    }
}