// Week 3 – Solutions of the practice exercises
// Run: java Exercises03.java
import java.util.Arrays;

public class Exercises03 {

    // E1. Average
    static double average(int[] a) {
        long sum = 0;
        for (int v : a) sum += v;
        return (double) sum / a.length;
    }

    // E2. Does it contain x?
    static boolean contains(int[] a, int x) {
        for (int v : a) if (v == x) return true;
        return false;
    }

    // E3. Second largest element with a single pass
    static int secondLargest(int[] a) {
        int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE;
        for (int v : a) {
            if (v > first) {
                second = first;
                first = v;
            } else if (v > second && v != first) {
                second = v;
            }
        }
        return second;
    }

    // E4. Removing duplicates from a SORTED array in place; returns the new length
    static int removeDuplicates(int[] a) {
        if (a.length == 0) return 0;
        int w = 1; // the next distinct element is written here
        for (int r = 1; r < a.length; r++) {
            if (a[r] != a[w - 1]) a[w++] = a[r];
        }
        return w;
    }

    // E5. Merging two sorted arrays – O(n + m)
    static int[] merge(int[] a, int[] b) {
        int[] c = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length) {
            c[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
        }
        while (i < a.length) c[k++] = a[i++];
        while (j < b.length) c[k++] = b[j++];
        return c;
    }

    // E6. Row sums and column sums of a matrix
    static int[][] rowColSums(int[][] m) {
        int[] rows = new int[m.length], cols = new int[m[0].length];
        for (int i = 0; i < m.length; i++)
            for (int j = 0; j < m[0].length; j++) {
                rows[i] += m[i][j];
                cols[j] += m[i][j];
            }
        return new int[][] { rows, cols };
    }

    // E7. Spiral traversal
    static String spiral(int[][] m) {
        StringBuilder sb = new StringBuilder();
        int top = 0, bottom = m.length - 1, left = 0, right = m[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) sb.append(m[top][j]).append(' ');
            top++;
            for (int i = top; i <= bottom; i++) sb.append(m[i][right]).append(' ');
            right--;
            if (top <= bottom) {
                for (int j = right; j >= left; j--) sb.append(m[bottom][j]).append(' ');
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; i--) sb.append(m[i][left]).append(' ');
                left++;
            }
        }
        return sb.toString().trim();
    }

    public static void main(String[] args) {
        int[] a = { 4, 9, 2, 9, 7, 1 };
        System.out.println("E1. average = " + average(a));
        System.out.println("E2. contains(7) = " + contains(a, 7) + ", contains(5) = " + contains(a, 5));
        System.out.println("E3. secondLargest = " + secondLargest(a));
        int[] s = { 1, 1, 2, 3, 3, 3, 5 };
        int len = removeDuplicates(s);
        System.out.println("E4. removeDuplicates -> " + Arrays.toString(Arrays.copyOf(s, len)));
        System.out.println("E5. merge = " + Arrays.toString(merge(new int[] { 1, 4, 9 }, new int[] { 2, 3, 10, 11 })));
        int[][] m = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
        int[][] rc = rowColSums(m);
        System.out.println("E6. row sums = " + Arrays.toString(rc[0]) + ", column sums = " + Arrays.toString(rc[1]));
        System.out.println("E7. spiral: " + spiral(m));
    }
}