import java.util.*;

/** 25 array problems for interviews. Each section has a brute-force version where one is worth showing, and the optimal one. */
public class ArrayPrograms {

    // BEGIN a01
    static int largest(int[] a) {
        int max = a[0];
        for (int x : a) if (x > max) max = x;
        return max;
    }
    // END a01

    // BEGIN a02
    static int secondLargestBrute(int[] a) {                 // O(n log n): sort, then walk back to the first different value
        int[] c = a.clone();
        Arrays.sort(c);
        for (int i = c.length - 2; i >= 0; i--) if (c[i] != c[c.length - 1]) return c[i];
        throw new NoSuchElementException("all elements equal");
    }

    static int secondLargest(int[] a) {                      // O(n): one pass, two variables
        int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE;
        for (int x : a) {
            if (x > first) { second = first; first = x; }
            else if (x > second && x != first) second = x;
        }
        if (second == Integer.MIN_VALUE) throw new NoSuchElementException("all elements equal");
        return second;
    }
    // END a02

    // BEGIN a03
    static void reverse(int[] a) {
        for (int i = 0, j = a.length - 1; i < j; i++, j--) {
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }
    // END a03

    // BEGIN a04
    static int[] rotateLeftBrute(int[] a, int k) {           // O(n) time, O(n) extra space
        int n = a.length;
        int[] out = new int[n];
        for (int i = 0; i < n; i++) out[i] = a[(i + k) % n];
        return out;
    }

    static void rotateLeft(int[] a, int k) {                 // O(n) time, O(1) space: three reversals
        int n = a.length;
        k %= n;
        reverseRange(a, 0, k - 1);
        reverseRange(a, k, n - 1);
        reverseRange(a, 0, n - 1);
    }

    static void reverseRange(int[] a, int i, int j) {
        while (i < j) { int t = a[i]; a[i++] = a[j]; a[j--] = t; }
    }
    // END a04

    // BEGIN a05
    static List<Integer> duplicatesBrute(int[] a) {          // O(n^2)
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < a.length; i++)
            for (int j = i + 1; j < a.length; j++)
                if (a[i] == a[j] && !out.contains(a[i])) out.add(a[i]);
        return out;
    }

    static List<Integer> duplicates(int[] a) {               // O(n) time, O(n) space
        Set<Integer> seen = new HashSet<>(), dup = new LinkedHashSet<>();
        for (int x : a) if (!seen.add(x)) dup.add(x);
        return new ArrayList<>(dup);
    }
    // END a05

    // BEGIN a06
    static int missingBrute(int[] a, int n) {                // O(n^2): look for every value
        for (int v = 1; v <= n; v++) {
            boolean found = false;
            for (int x : a) if (x == v) { found = true; break; }
            if (!found) return v;
        }
        return -1;
    }

    static int missing(int[] a, int n) {                     // O(n), O(1): expected sum minus actual sum
        long expected = (long) n * (n + 1) / 2;
        long actual = 0;
        for (int x : a) actual += x;
        return (int) (expected - actual);
    }
    // END a06

    // BEGIN a07
    static int[] twoSumBrute(int[] a, int target) {          // O(n^2)
        for (int i = 0; i < a.length; i++)
            for (int j = i + 1; j < a.length; j++)
                if (a[i] + a[j] == target) return new int[]{i, j};
        return new int[0];
    }

    static int[] twoSum(int[] a, int target) {               // O(n): remember what we have seen
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < a.length; i++) {
            Integer j = index.get(target - a[i]);
            if (j != null) return new int[]{j, i};
            index.put(a[i], i);
        }
        return new int[0];
    }
    // END a07

    // BEGIN a08
    static int maxSubarrayBrute(int[] a) {                   // O(n^2)
        int best = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            int sum = 0;
            for (int j = i; j < a.length; j++) { sum += a[j]; best = Math.max(best, sum); }
        }
        return best;
    }

    static int kadane(int[] a) {                             // O(n): best sum of a subarray ending here
        int endingHere = a[0], best = a[0];
        for (int i = 1; i < a.length; i++) {
            endingHere = Math.max(a[i], endingHere + a[i]);  // extend the run, or restart at a[i]
            best = Math.max(best, endingHere);
        }
        return best;
    }
    // END a08

    // BEGIN a09
    static int removeDuplicatesSorted(int[] a) {             // returns the new length, array edited in place
        if (a.length == 0) return 0;
        int write = 1;
        for (int read = 1; read < a.length; read++) {
            if (a[read] != a[write - 1]) a[write++] = a[read];
        }
        return write;
    }
    // END a09

    // BEGIN a10
    static void moveZeroes(int[] a) {
        int write = 0;
        for (int read = 0; read < a.length; read++) {
            if (a[read] != 0) { int t = a[write]; a[write++] = a[read]; a[read] = t; }
        }
    }
    // END a10

    // BEGIN a11
    static int[] mergeSorted(int[] a, int[] b) {
        int[] out = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length) out[k++] = a[i] <= b[j] ? a[i++] : b[j++];
        while (i < a.length) out[k++] = a[i++];
        while (j < b.length) out[k++] = b[j++];
        return out;
    }
    // END a11

    // BEGIN a12
    static boolean isSorted(int[] a) {
        for (int i = 1; i < a.length; i++) if (a[i - 1] > a[i]) return false;
        return true;
    }
    // END a12

    // BEGIN a13
    static Map<Integer, Integer> frequency(int[] a) {
        Map<Integer, Integer> freq = new LinkedHashMap<>();
        for (int x : a) freq.merge(x, 1, Integer::sum);
        return freq;
    }
    // END a13

    // BEGIN a14
    static List<Integer> leaders(int[] a) {                  // an element larger than everything to its right
        LinkedList<Integer> out = new LinkedList<>();
        int max = Integer.MIN_VALUE;
        for (int i = a.length - 1; i >= 0; i--) {
            if (a[i] > max) { max = a[i]; out.addFirst(a[i]); }
        }
        return out;
    }
    // END a14

    // BEGIN a15
    static int equilibriumBrute(int[] a) {                   // O(n^2): recompute both sums
        for (int i = 0; i < a.length; i++) {
            int left = 0, right = 0;
            for (int j = 0; j < i; j++) left += a[j];
            for (int j = i + 1; j < a.length; j++) right += a[j];
            if (left == right) return i;
        }
        return -1;
    }

    static int equilibrium(int[] a) {                        // O(n): carry the left sum, derive the right sum
        int total = 0;
        for (int x : a) total += x;
        int left = 0;
        for (int i = 0; i < a.length; i++) {
            if (left == total - left - a[i]) return i;
            left += a[i];
        }
        return -1;
    }
    // END a15

    // BEGIN a16
    static int[] subarrayWithSum(int[] a, int target) {      // positive numbers only: sliding window, O(n)
        int left = 0, sum = 0;
        for (int right = 0; right < a.length; right++) {
            sum += a[right];
            while (sum > target && left <= right) sum -= a[left++];
            if (sum == target) return new int[]{left, right};
        }
        return new int[0];
    }
    // END a16

    // BEGIN a17
    static int majorityBrute(int[] a) {                      // O(n^2)
        for (int x : a) {
            int count = 0;
            for (int y : a) if (y == x) count++;
            if (count > a.length / 2) return x;
        }
        return -1;
    }

    static int majority(int[] a) {                           // Boyer-Moore voting, O(n), O(1)
        int candidate = 0, votes = 0;
        for (int x : a) {
            if (votes == 0) candidate = x;
            votes += (x == candidate) ? 1 : -1;
        }
        int count = 0;
        for (int x : a) if (x == candidate) count++;         // verify: a majority may not exist
        return count > a.length / 2 ? candidate : -1;
    }
    // END a17

    // BEGIN a18
    static List<Integer> intersection(int[] a, int[] b) {
        Set<Integer> set = new HashSet<>();
        for (int x : a) set.add(x);
        Set<Integer> out = new TreeSet<>();
        for (int y : b) if (set.contains(y)) out.add(y);
        return new ArrayList<>(out);
    }
    // END a18

    // BEGIN a19
    static int[] productExceptSelf(int[] a) {                // no division, O(n)
        int n = a.length;
        int[] out = new int[n];
        out[0] = 1;
        for (int i = 1; i < n; i++) out[i] = out[i - 1] * a[i - 1];   // product of everything left of i
        int right = 1;
        for (int i = n - 1; i >= 0; i--) { out[i] *= right; right *= a[i]; }
        return out;
    }
    // END a19

    // BEGIN a20
    static void sortColors(int[] a) {                        // Dutch national flag: one pass over 0s, 1s and 2s
        int low = 0, mid = 0, high = a.length - 1;
        while (mid <= high) {
            if (a[mid] == 0) { int t = a[low]; a[low++] = a[mid]; a[mid++] = t; }
            else if (a[mid] == 1) mid++;
            else { int t = a[high]; a[high--] = a[mid]; a[mid] = t; }
        }
    }
    // END a20

    // BEGIN a21
    static int maxProfitBrute(int[] p) {                     // O(n^2)
        int best = 0;
        for (int i = 0; i < p.length; i++)
            for (int j = i + 1; j < p.length; j++) best = Math.max(best, p[j] - p[i]);
        return best;
    }

    static int maxProfit(int[] p) {                          // O(n): track the cheapest price so far
        int min = Integer.MAX_VALUE, best = 0;
        for (int price : p) {
            min = Math.min(min, price);
            best = Math.max(best, price - min);
        }
        return best;
    }
    // END a21

    // BEGIN a22
    static int longestConsecutive(int[] a) {                 // O(n): only start counting at the beginning of a run
        Set<Integer> set = new HashSet<>();
        for (int x : a) set.add(x);
        int best = 0;
        for (int x : set) {
            if (!set.contains(x - 1)) {
                int len = 1;
                while (set.contains(x + len)) len++;
                best = Math.max(best, len);
            }
        }
        return best;
    }
    // END a22

    // BEGIN a23
    static int singleNumber(int[] a) {                       // every other value appears twice: x ^ x == 0
        int x = 0;
        for (int v : a) x ^= v;
        return x;
    }
    // END a23

    // BEGIN a24
    static int binarySearch(int[] a, int key) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;                    // not (lo + hi) / 2: that can overflow
            if (a[mid] == key) return mid;
            if (a[mid] < key) lo = mid + 1; else hi = mid - 1;
        }
        return -1;
    }
    // END a24

    // BEGIN a25
    static int trapBrute(int[] h) {                          // O(n^2): water above i = min(maxLeft, maxRight) - h[i]
        int total = 0;
        for (int i = 0; i < h.length; i++) {
            int l = 0, r = 0;
            for (int j = 0; j <= i; j++) l = Math.max(l, h[j]);
            for (int j = i; j < h.length; j++) r = Math.max(r, h[j]);
            total += Math.min(l, r) - h[i];
        }
        return total;
    }

    static int trap(int[] h) {                               // O(n), O(1): two pointers
        int lo = 0, hi = h.length - 1, lMax = 0, rMax = 0, total = 0;
        while (lo < hi) {
            if (h[lo] < h[hi]) { lMax = Math.max(lMax, h[lo]); total += lMax - h[lo++]; }
            else               { rMax = Math.max(rMax, h[hi]); total += rMax - h[hi--]; }
        }
        return total;
    }
    // END a25

    static String s(int[] a) { return Arrays.toString(a); }

    public static void main(String[] args) {
        int[] d = {7, 3, 9, 3, 5, 9, 1};
        System.out.println("01 largest            " + s(d) + " -> " + largest(d));
        System.out.println("02 second largest     " + s(d) + " -> brute " + secondLargestBrute(d) + ", one-pass " + secondLargest(d));
        int[] r = {1, 2, 3, 4, 5}; reverse(r);
        System.out.println("03 reverse            [1, 2, 3, 4, 5] -> " + s(r));
        int[] rot = {1, 2, 3, 4, 5, 6, 7}; rotateLeft(rot, 3);
        System.out.println("04 rotate left by 3   [1, 2, 3, 4, 5, 6, 7] -> " + s(rot) + " (brute: " + s(rotateLeftBrute(new int[]{1, 2, 3, 4, 5, 6, 7}, 3)) + ")");
        System.out.println("05 duplicates         " + s(d) + " -> brute " + duplicatesBrute(d) + ", hash set " + duplicates(d));
        int[] m = {1, 2, 4, 5, 6};
        System.out.println("06 missing 1..6       " + s(m) + " -> brute " + missingBrute(m, 6) + ", sum formula " + missing(m, 6));
        int[] ts = {2, 7, 11, 15};
        System.out.println("07 two sum (9)        " + s(ts) + " -> brute " + s(twoSumBrute(ts, 9)) + ", hash map " + s(twoSum(ts, 9)));
        int[] k = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("08 max subarray       " + s(k) + " -> brute " + maxSubarrayBrute(k) + ", Kadane " + kadane(k));
        int[] rd = {1, 1, 2, 2, 2, 3, 4, 4}; int len = removeDuplicatesSorted(rd);
        System.out.println("09 dedupe sorted      [1, 1, 2, 2, 2, 3, 4, 4] -> length " + len + " " + s(Arrays.copyOf(rd, len)));
        int[] mz = {0, 1, 0, 3, 12}; moveZeroes(mz);
        System.out.println("10 move zeroes        [0, 1, 0, 3, 12] -> " + s(mz));
        System.out.println("11 merge sorted       [1, 4, 7] + [2, 3, 9, 10] -> " + s(mergeSorted(new int[]{1, 4, 7}, new int[]{2, 3, 9, 10})));
        System.out.println("12 is sorted          [1, 2, 2, 5] -> " + isSorted(new int[]{1, 2, 2, 5}) + ", [3, 1, 2] -> " + isSorted(new int[]{3, 1, 2}));
        System.out.println("13 frequency          " + s(d) + " -> " + frequency(d));
        int[] ld = {16, 17, 4, 3, 5, 2};
        System.out.println("14 leaders            " + s(ld) + " -> " + leaders(ld));
        int[] eq = {-7, 1, 5, 2, -4, 3, 0};
        System.out.println("15 equilibrium index  " + s(eq) + " -> brute " + equilibriumBrute(eq) + ", one pass " + equilibrium(eq));
        int[] sw = {1, 4, 20, 3, 10, 5};
        System.out.println("16 subarray sum 33    " + s(sw) + " -> indexes " + s(subarrayWithSum(sw, 33)));
        int[] mj = {2, 2, 1, 1, 1, 2, 2};
        System.out.println("17 majority element   " + s(mj) + " -> brute " + majorityBrute(mj) + ", Boyer-Moore " + majority(mj) + "; no majority in [1, 2, 3] -> " + majority(new int[]{1, 2, 3}));
        System.out.println("18 intersection       [4, 9, 5, 9] and [9, 4, 9, 8, 4] -> " + intersection(new int[]{4, 9, 5, 9}, new int[]{9, 4, 9, 8, 4}));
        System.out.println("19 product except self [1, 2, 3, 4] -> " + s(productExceptSelf(new int[]{1, 2, 3, 4})));
        int[] sc = {2, 0, 2, 1, 1, 0}; sortColors(sc);
        System.out.println("20 sort 0s 1s 2s      [2, 0, 2, 1, 1, 0] -> " + s(sc));
        int[] pr = {7, 1, 5, 3, 6, 4};
        System.out.println("21 stock profit       " + s(pr) + " -> brute " + maxProfitBrute(pr) + ", one pass " + maxProfit(pr));
        System.out.println("22 longest run        [100, 4, 200, 1, 3, 2] -> " + longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));
        System.out.println("23 single number      [4, 1, 2, 1, 2] -> " + singleNumber(new int[]{4, 1, 2, 1, 2}));
        int[] bs = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        System.out.println("24 binary search      find 23 -> index " + binarySearch(bs, 23) + ", find 7 -> " + binarySearch(bs, 7));
        int[] rain = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println("25 trapping rain      " + s(rain) + " -> brute " + trapBrute(rain) + ", two pointers " + trap(rain));
    }
}