Java interview snippets: Google L4 / L5 preparation#

cd /Users/apoorvdubey/Study/prep_for_google
javac --release 8 -Xlint:all,-options -d /private/tmp/codex-java-interview-check JavaInterviewTemplates.java JavaInterviewTemplatesTest.java
java -cp /private/tmp/codex-java-interview-check JavaInterviewTemplatesTest

static void arraysAndLists() {
    int[] a = {3, 1, 2};
    int[] copy = a.clone();
    int[] slice = Arrays.copyOfRange(a, 0, 2); // [0, 2)
    Arrays.sort(copy);                          // mutates copy
    int[] filled = new int[5];
    Arrays.fill(filled, -1);
    int[][] matrix = new int[2][3];
    for (int[] row : matrix) Arrays.fill(row, -1);
    int[][] deepCopy = new int[matrix.length][];
    for (int i = 0; i < matrix.length; i++) deepCopy[i] = matrix[i].clone();
    boolean equal = Arrays.equals(a, copy);
    boolean deepEqual = Arrays.deepEquals(matrix, deepCopy);
    List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 2));
    list.add(4);
    list.remove(Integer.valueOf(1)); // remove value 1
    list.remove(0);                 // remove index 0
    Collections.sort(list);
    Collections.reverse(list);
    Integer[] boxed = list.toArray(new Integer[0]);
    int[] primitive = list.stream().mapToInt(Integer::intValue).toArray();
    // Arrays.asList(new int[]{1, 2}) is a List<int[]> containing ONE array.
    // Arrays.asList(1, 2) is fixed-size; wrap in ArrayList to add/remove.
    // a.length; list.size(); Arrays.toString(a); Arrays.deepToString(matrix).
}

static String stringTools(String s) {
    int n = s.length();
    if (n > 0) {
        char first = s.charAt(0);
        String rest = s.substring(1); // valid even when n == 1
        String prefix = s.substring(0, Math.min(3, n)); // end exclusive
    }
    char[] chars = s.toCharArray();
    Arrays.sort(chars);
    String sorted = new String(chars);
    String[] words = s.trim().isEmpty() ? new String[0] : s.trim().split("\\s+");
    String[] dotted = "a.b.".split("\\.", -1); // regex; preserve trailing empty
    boolean equal = Objects.equals(s, sorted); // null-safe equality
    int comparison = s.compareTo(sorted);     // lexicographic order
    StringBuilder out = new StringBuilder();
    for (char c : s.toCharArray()) out.append(c);
    if (out.length() > 0) out.deleteCharAt(out.length() - 1);
    return out.reverse().toString();
    // String is immutable. Repeated concatenation in a loop can be quadratic.
    // char is a UTF-16 code unit; use s.codePoints().toArray() if required.
    // Lowercase-English counting only: int[] count = new int[26]; count[c-'a']++.
}

static Map<Integer, Integer> frequencies(int[] a) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : a) freq.put(x, freq.getOrDefault(x, 0) + 1);
    // Equivalent increment: freq.merge(x, 1, Integer::sum);
    Set<Integer> seen = new HashSet<>();
    for (int x : a) {
        if (!seen.add(x)) { /* x was already present */ }
    }
    Map<String, List<Integer>> groups = new HashMap<>();
    groups.computeIfAbsent("key", k -> new ArrayList<>()).add(7);
    for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
        int value = entry.getKey(), count = entry.getValue();
    }
    // Decrement and remove zero counts (when x is present):
    // int next = freq.get(x) - 1;
    // if (next == 0) freq.remove(x); else freq.put(x, next);
    // Use iterator.remove() to remove during iteration.
    return freq;
}

static void dequeTools() {
    Queue<Integer> queue = new ArrayDeque<>();
    queue.offer(10);
    Integer head = queue.peek(); // null if empty
    Integer removed = queue.poll();
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(10);
    int top = stack.peek();     // unboxing null would throw if empty
    int popped = stack.pop();   // throws if empty
    Deque<Integer> deque = new ArrayDeque<>();
    deque.offerFirst(1);
    deque.offerLast(2);
    deque.peekFirst();
    deque.peekLast();
    deque.pollFirst();
    deque.pollLast();
    // ArrayDeque rejects null. Keep queue and stack conventions distinct.
}

static int kthLargestHeap(int[] a, int k) {
    if (k < 1 || k > a.length) throw new IllegalArgumentException("k");
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int x : a) {
        minHeap.offer(x);
        if (minHeap.size() > k) minHeap.poll();
    }
    return minHeap.peek(); // O(n log(k+1)) time, O(k) space
}
static void comparatorTools() {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    PriorityQueue<int[]> byCost = new PriorityQueue<>((a, b) -> {
        int cmp = Integer.compare(a[1], b[1]);
        return cmp != 0 ? cmp : Integer.compare(a[0], b[0]);
    });
    int[][] intervals = {{2, 4}, {1, 5}, {1, 3}};
    Arrays.sort(intervals, (a, b) -> {
        int cmp = Integer.compare(a[0], b[0]);
        return cmp != 0 ? cmp : Integer.compare(a[1], b[1]);
    });
    // Never use a[0] - b[0] as a comparator: overflow can break ordering.
    // Primitive int[] cannot take a comparator; int[][] can (rows are objects).
    // Heap iteration is NOT sorted. Repeated poll() retrieves sorted order.
    // Do not mutate a queued element's priority; reinsert a new entry instead.
}

static void orderedTools() {
    TreeMap<Integer, Integer> counts = new TreeMap<>();
    counts.merge(10, 1, Integer::sum);
    counts.merge(10, 1, Integer::sum); // frequency 2
    counts.merge(20, 1, Integer::sum);
    Integer floor = counts.floorKey(15);   // <= 15
    Integer ceiling = counts.ceilingKey(15); // >= 15
    Integer lower = counts.lowerKey(10);   // < 10; null here
    Integer higher = counts.higherKey(10); // > 10
        int smallest = counts.firstKey(); // requires nonempty map
        int largest = counts.lastKey();
        int x = 10;
        Integer count = counts.get(x); // never unbox get() directly; absent => null
        if (count != null) {
            if (count == 1) counts.remove(x);
            else counts.put(x, count - 1);
        }
    NavigableSet<Integer> set = new TreeSet<>();
    set.add(10); set.add(20);
    Integer candidate = set.ceiling(11);
    // TreeSet removes duplicates according to its comparator (compare == 0).
}

static long gcd(long a, long b) { // nonnegative inputs
    while (b != 0) { long remainder = a % b; a = b; b = remainder; }
    return a;
}
static long modPow(long base, long exponent, int mod) {
    // exponent >= 0, mod > 0; int modulus keeps products within long range.
    long result = 1 % mod;
    base = Math.floorMod(base, (long) mod);
    while (exponent > 0) {
        if ((exponent & 1L) != 0) result = result * base % mod;
        base = base * base % mod;
        exponent >>= 1;
    }
    return result;
}
static void numericTools() {
    int a = Integer.MAX_VALUE, b = 2;
    long product = (long) a * b; // cast BEFORE arithmetic
    long sum = (long) a + b;
    long absolute = Math.abs((long) Integer.MIN_VALUE);
    long n = 15, d = 4; // n >= 0, d > 0
    long ceilDiv = n / d + (n % d == 0 ? 0 : 1); // no n+d overflow
    int normalized = Math.floorMod(-3, 5);
    int mask = 12, bit = 2; // 0 <= bit < 32 for int
    boolean isSet = (mask & (1 << bit)) != 0;
    int set = mask | (1 << bit), clear = mask & ~(1 << bit);
    int toggle = mask ^ (1 << bit), lowest = mask & -mask;
    int withoutLowest = mask & (mask - 1);
    int count = Integer.bitCount(mask), logicalShift = mask >>> 1;
    boolean powerOfTwo = mask > 0 && (mask & (mask - 1)) == 0;
    long wideBit = 1L << 40;
    // Java masks shift distances: 1 << 32 equals 1 << 0.
}

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}
static class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
static class GraphNode {
    int val;
    List<GraphNode> neighbors = new ArrayList<>();
    GraphNode(int val) { this.val = val; }
}

static ListNode reverseList(ListNode head) { // mutates links; O(n), O(1)
    ListNode previous = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = previous;
        previous = head;
        head = next;
    }
    return previous;
}
static boolean hasCycle(ListNode head) { // O(n), O(1)
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}
static ListNode mergeLists(ListNode a, ListNode b) {
    // Sorted ascending, acyclic, disjoint lists; reuses and mutates nodes.
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a != null ? a : b;
    return dummy.next; // O(n+m), O(1) auxiliary space
}

static int lowerBound(int[] a, int target) {
    int left = 0, right = a.length; // search [left, right)
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left; // first >= target; n if none
}
static int upperBound(int[] a, int target) {
    int left = 0, right = a.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left; // first > target; n if none
}
// Sorted ascending input. O(log n), O(1).
// count(target) = upperBound(a,target) - lowerBound(a,target).
// Exact match: int i = lowerBound(a,t); boolean found = i < a.length && a[i] == t;

static int minEatingSpeed(int[] piles, long hours) {
    // Positive piles; one pile per hour, unused capacity cannot transfer.
    if (piles.length == 0) return 0;
    if (hours < piles.length) return -1;
    int left = 1, right = 0;
    for (int pile : piles) right = Math.max(right, pile);
    while (left < right) {
        int speed = left + (right - left) / 2;
        long needed = 0;
        for (int pile : piles) needed += ((long) pile + speed - 1) / speed;
        if (needed <= hours) right = speed; // feasible: seek smaller
        else left = speed + 1;
    }
    return left; // O(n log maxPile), O(1)
}
// Maximize feasible x: if (feasible(mid)) left = mid; else right = mid - 1;
// MUST use mid = left + (right - left + 1) / 2 when assigning left = mid,
// otherwise left == mid forever when right == left + 1.

static long[] prefixSums(int[] a) {
    long[] prefix = new long[a.length + 1];
    for (int i = 0; i < a.length; i++) prefix[i + 1] = prefix[i] + a[i];
    return prefix; // sum of [left,right) = prefix[right] - prefix[left]
}
static long subarraySumCount(int[] a, long target) {
    // Supports negative values; count can exceed int range.
    Map<Long, Long> frequencies = new HashMap<>();
    frequencies.put(0L, 1L);
    long prefix = 0, answer = 0;
    for (int x : a) {
        prefix += x;
        answer += frequencies.getOrDefault(prefix - target, 0L);
        frequencies.put(prefix, frequencies.getOrDefault(prefix, 0L) + 1);
    }
    return answer; // expected O(n) time, O(n) space
}

static int[] twoSumSorted(int[] a, long target) {
    int left = 0, right = a.length - 1;
    while (left < right) {
        long sum = (long) a[left] + a[right];
        if (sum == target) return new int[]{left, right};
        if (sum < target) left++;
        else right--;
    }
    return new int[]{-1, -1}; // O(n), O(1); returns zero-based indices
}

static int longestAtMostKDistinct(String s, int k) {
    if (k <= 0) return 0;
    Map<Character, Integer> freq = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        freq.put(c, freq.getOrDefault(c, 0) + 1);
        while (freq.size() > k) {
            char old = s.charAt(left++);
            int remaining = freq.get(old) - 1;
            if (remaining == 0) freq.remove(old);
            else freq.put(old, remaining);
        }
        best = Math.max(best, right - left + 1);
    }
    return best; // expected O(n); O(min(alphabet,k+1)) space; UTF-16 units
}

static long maxWindowSum(int[] a, int k) {
    if (k < 1 || k > a.length) throw new IllegalArgumentException("k");
    long window = 0, best = Long.MIN_VALUE;
    for (int right = 0; right < a.length; right++) {
        window += a[right];
        if (right >= k) window -= a[right - k];
        if (right >= k - 1) best = Math.max(best, window);
    }
    return best; // O(n), O(1); works with all-negative arrays
}

static int[] nextGreaterIndex(int[] a) {
    int[] answer = new int[a.length];
    Arrays.fill(answer, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < a.length; i++) {
        while (!stack.isEmpty() && a[stack.peek()] < a[i]) {
            answer[stack.pop()] = i;
        }
        stack.push(i);
    }
    return answer; // O(n), O(n); strictly greater, not greater-or-equal
}

static int[] slidingMaximum(int[] a, int k) {
    if (k < 1 || k > a.length) throw new IllegalArgumentException("k");
    int[] answer = new int[a.length - k + 1];
    Deque<Integer> deque = new ArrayDeque<>(); // indices, descending values
    for (int i = 0; i < a.length; i++) {
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) deque.pollFirst();
        while (!deque.isEmpty() && a[deque.peekLast()] <= a[i]) deque.pollLast();
        deque.offerLast(i);
        if (i >= k - 1) answer[i - k + 1] = a[deque.peekFirst()];
    }
    return answer; // O(n), O(k) auxiliary space, excluding output
}

static int[][] mergeIntervals(int[][] intervals) {
    // Closed intervals [start,end], start <= end; touching intervals merge.
    int[][] sorted = new int[intervals.length][];
    for (int i = 0; i < intervals.length; i++) sorted[i] = intervals[i].clone();
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
    List<int[]> result = new ArrayList<>();
    for (int[] current : sorted) {
        if (result.isEmpty() || result.get(result.size() - 1)[1] < current[0]) {
            result.add(current);
        } else {
            int[] last = result.get(result.size() - 1);
            last[1] = Math.max(last[1], current[1]);
        }
    }
    return result.toArray(new int[0][]); // O(n log n), O(n); preserves input
}

static int meetingRooms(int[][] intervals) {
    // Half-open [start,end), start < end. End at t frees the room for a start at t
    // (peek() <= start). Touching meetings share a room; they do not need two.
    int[][] sorted = intervals.clone(); // sorting outer array only; rows unchanged
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
    PriorityQueue<Integer> ends = new PriorityQueue<>();
    int best = 0;
    for (int[] interval : sorted) {
        while (!ends.isEmpty() && ends.peek() <= interval[0]) ends.poll();
        ends.offer(interval[1]);
        best = Math.max(best, ends.size());
    }
    return best; // O(n log n), O(n)
}

static List<Integer> inorder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
        while (current != null) { stack.push(current); current = current.left; }
        current = stack.pop();
        result.add(current.val);
        current = current.right;
    }
    return result; // O(n), O(h) auxiliary space
}
static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size(); // snapshot before adding children
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result; // O(n), O(maximum width) auxiliary space
}

static int heightOrUnbalanced(TreeNode root) {
    if (root == null) return 0;
    int left = heightOrUnbalanced(root.left);
    if (left == -1) return -1;
    int right = heightOrUnbalanced(root.right);
    if (right == -1 || Math.abs(left - right) > 1) return -1;
    return 1 + Math.max(left, right); // -1 means unbalanced
}
static TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    // General binary tree; BOTH node references must exist in the tree.
    if (root == null || root == p || root == q) return root;
    TreeNode left = lca(root.left, p, q), right = lca(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}
// Each O(n) time, O(h) call stack. Skewed trees can overflow Java's stack.

static boolean validBST(TreeNode root) {
    return validBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
static boolean validBST(TreeNode node, long low, long high) {
    if (node == null) return true;
    if (node.val <= low || node.val >= high) return false;
    return validBST(node.left, low, node.val) && validBST(node.right, node.val, high);
}
// Strict BST: duplicates disallowed. O(n), O(h). Long bounds admit all int values.

static List<List<Integer>> graph(int n, int[][] edges, boolean directed) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        if (!directed) graph.get(edge[1]).add(edge[0]);
    }
    return graph; // vertex IDs 0..n-1
}
static int[] bfsDistances(List<List<Integer>> graph, int source) {
    int[] distance = new int[graph.size()];
    Arrays.fill(distance, -1);
    Queue<Integer> queue = new ArrayDeque<>();
    distance[source] = 0;
    queue.offer(source);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : graph.get(u)) {
            if (distance[v] != -1) continue;
            distance[v] = distance[u] + 1; // mark when enqueuing
            queue.offer(v);
        }
    }
    return distance; // unweighted shortest paths; -1 means unreachable
}
static int connectedComponents(List<List<Integer>> graph) {
    // UNDIRECTED graph. This is not an SCC algorithm for directed graphs.
    boolean[] visited = new boolean[graph.size()];
    int components = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    for (int start = 0; start < graph.size(); start++) {
        if (visited[start]) continue;
        components++;
        visited[start] = true;
        stack.push(start);
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v : graph.get(u)) {
                if (!visited[v]) { visited[v] = true; stack.push(v); }
            }
        }
    }
    return components;
}
// Each traversal O(V+E) time, O(V) auxiliary space (excluding adjacency).

static int[][] distanceToZero(int[][] grid) {
    // Rectangular binary grid; all cells traversable. No zero => all -1.
    int rows = grid.length, cols = rows == 0 ? 0 : grid[0].length;
    int[][] dist = new int[rows][cols];
    Queue<int[]> queue = new ArrayDeque<>();
    for (int r = 0; r < rows; r++) {
        Arrays.fill(dist[r], -1);
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 0) { dist[r][c] = 0; queue.offer(new int[]{r, c}); }
        }
    }
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        for (int[] d : directions) {
            int r = cell[0] + d[0], c = cell[1] + d[1];
            if (r < 0 || r >= rows || c < 0 || c >= cols || dist[r][c] != -1) continue;
            dist[r][c] = dist[cell[0]][cell[1]] + 1;
            queue.offer(new int[]{r, c});
        }
    }
    return dist; // O(rows*cols) time and space; input unchanged
}

static int[] topologicalSort(List<List<Integer>> graph) {
    int n = graph.size();
    int[] indegree = new int[n], order = new int[n];
    for (List<Integer> neighbors : graph) for (int v : neighbors) indegree[v]++;
    Queue<Integer> queue = new ArrayDeque<>();
    for (int u = 0; u < n; u++) if (indegree[u] == 0) queue.offer(u);
    int count = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order[count++] = u;
        for (int v : graph.get(u)) if (--indegree[v] == 0) queue.offer(v);
    }
    return count == n ? order : new int[0];
    // Nonempty graph + empty result => cycle. Empty graph has valid empty order.
    // Edge u->v means u must precede v. O(V+E), O(V) auxiliary space.
}

static class Edge {
    final int to, weight;
    Edge(int to, int weight) { this.to = to; this.weight = weight; }
}
static long[] dijkstra(List<List<Edge>> graph, int source) {
    // All weights >= 0; finite distances fit in long and are < Long.MAX_VALUE.
    long[] dist = new long[graph.size()];
    Arrays.fill(dist, Long.MAX_VALUE);
    PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    dist[source] = 0;
    heap.offer(new long[]{0, source}); // {distance, node}
    while (!heap.isEmpty()) {
        long[] current = heap.poll();
        long distance = current[0];
        int u = (int) current[1];
        if (distance != dist[u]) continue;
        for (Edge edge : graph.get(u)) {
            long candidate = distance + edge.weight;
            if (candidate < dist[edge.to]) {
                dist[edge.to] = candidate;
                heap.offer(new long[]{candidate, edge.to});
            }
        }
    }
    return dist; // Long.MAX_VALUE means unreachable.
    // Lazy heap: O(V + E log(E+1)) time, O(V+E) auxiliary space.
}

static class UnionFind {
    final int[] parent, size;
    int components;
    UnionFind(int n) {
        parent = new int[n]; size = new int[n]; components = n;
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }
    int find(int x) {
        while (x != parent[x]) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) { int temp = ra; ra = rb; rb = temp; }
        parent[rb] = ra;
        size[ra] += size[rb];
        components--;
        return true;
    }
}
// Amortized O(alpha(n)) per operation, O(n) storage, O(n) initialization.
// union returning false detects a redundant edge in an undirected graph.

static class Trie {
    static class Node { Node[] next = new Node[26]; boolean word; }
    final Node root = new Node();
    void insert(String s) { // lowercase a-z only; supports empty word
        Node node = root;
        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i) - 'a';
            if (node.next[index] == null) node.next[index] = new Node();
            node = node.next[index];
        }
        node.word = true;
    }
    Node walk(String s) {
        Node node = root;
        for (int i = 0; i < s.length(); i++) {
            node = node.next[s.charAt(i) - 'a'];
            if (node == null) return null;
        }
        return node;
    }
    boolean search(String s) { Node node = walk(s); return node != null && node.word; }
    boolean startsWith(String prefix) { return walk(prefix) != null; }
}
// O(length) per operation; space proportional to total inserted characters
// with 26 child slots per node. Use a map for a sparse/larger alphabet.

static List<List<Integer>> subsets(int[] a) { // assumes distinct input values
    List<List<Integer>> result = new ArrayList<>();
    subsets(a, 0, new ArrayList<>(), result);
    return result;
}
static void subsets(int[] a, int start, List<Integer> path, List<List<Integer>> result) {
    result.add(new ArrayList<>(path)); // copy, never add the mutable path itself
    for (int i = start; i < a.length; i++) {
        path.add(a[i]);
        subsets(a, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}
static List<List<Integer>> uniquePermutations(int[] input) {
    int[] a = input.clone(); Arrays.sort(a);
    List<List<Integer>> result = new ArrayList<>();
    permute(a, new boolean[a.length], new ArrayList<>(), result);
    return result;
}
static void permute(int[] a, boolean[] used, List<Integer> path, List<List<Integer>> result) {
    if (path.size() == a.length) { result.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < a.length; i++) {
        if (used[i] || (i > 0 && a[i] == a[i - 1] && !used[i - 1])) continue;
        used[i] = true; path.add(a[i]);
        permute(a, used, path, result);
        path.remove(path.size() - 1); used[i] = false;
    }
}
// Subsets O(n*2^n); permutations O(n*n!) worst case, including output copies.
// O(n) auxiliary space excluding returned output. Empty input yields [[]].

static int coinChange(int[] coins, int amount) {
    // Positive coin values, unlimited reuse, 0 <= amount < Integer.MAX_VALUE;
    // amount must be small enough to allocate the DP array.
    int impossible = amount + 1;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, impossible); dp[0] = 0;
    for (int value = 1; value <= amount; value++) {
        for (int coin : coins) {
            if (coin <= value && dp[value - coin] != impossible)
                dp[value] = Math.min(dp[value], dp[value - coin] + 1);
        }
    }
    return dp[amount] == impossible ? -1 : dp[amount];
    // dp[value] = minimum coins for exactly value. O(amount*coins), O(amount).
    // 0/1 knapsack compresses capacity DESCENDING to prevent item reuse.
}

static int lcs(String a, String b) {
    int[][] dp = new int[a.length() + 1][b.length() + 1];
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = 1 + dp[i - 1][j - 1];
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[a.length()][b.length()]; // O(m*n) time and space
    // dp[i][j] refers to prefixes of lengths i and j, not character indices.
}

static long minPathSum(int[][] grid) {
    // Nonempty rectangular grid, move only right/down; negative costs allowed.
    return minPathSum(grid, 0, 0, new Long[grid.length][grid[0].length]);
}
static long minPathSum(int[][] g, int r, int c, Long[][] memo) {
    if (memo[r][c] != null) return memo[r][c];
    if (r == g.length - 1 && c == g[0].length - 1) return memo[r][c] = (long) g[r][c];
    long best = Long.MAX_VALUE;
    if (r + 1 < g.length) best = Math.min(best, minPathSum(g, r + 1, c, memo));
    if (c + 1 < g[0].length) best = Math.min(best, minPathSum(g, r, c + 1, memo));
    return memo[r][c] = g[r][c] + best;
}
// O(rows*cols) time/memo storage; O(rows+cols) recursion depth.
// null means uncomputed: -1 is unsafe as a sentinel when valid results include -1.

static int lisLength(int[] a) {
    int[] tails = new int[a.length];
    int size = 0;
    for (int x : a) {
        int left = 0, right = size;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] < x) left = mid + 1;
            else right = mid;
        }
        tails[left] = x;
        if (left == size) size++;
    }
    return size; // strictly increasing; O(n log n), O(n)
    // tails[i] is the smallest known tail for length i+1; NOT the actual LIS.
}

static void mergeSort(int[] a) { mergeSort(a, new int[a.length], 0, a.length); }
static void mergeSort(int[] a, int[] temp, int left, int right) {
    if (right - left <= 1) return;
    int mid = left + (right - left) / 2;
    mergeSort(a, temp, left, mid); mergeSort(a, temp, mid, right);
    int i = left, j = mid, write = left;
    while (i < mid && j < right) temp[write++] = a[i] <= a[j] ? a[i++] : a[j++];
    while (i < mid) temp[write++] = a[i++];
    while (j < right) temp[write++] = a[j++];
    for (int k = left; k < right; k++) a[k] = temp[k];
}
// [left,right); stable; mutates input. O(n log n), O(n) auxiliary space.

static int kthSmallest(int[] a, int k) {
    // 1-based k; MUTATES input. Three-way partition handles duplicate pivots.
    if (k < 1 || k > a.length) throw new IllegalArgumentException("k");
    Random random = new Random();
    int target = k - 1, left = 0, right = a.length - 1;
    while (left <= right) {
        int pivot = a[left + random.nextInt(right - left + 1)];
        int less = left, scan = left, greater = right;
        while (scan <= greater) {
            if (a[scan] < pivot) swap(a, less++, scan++);
            else if (a[scan] > pivot) swap(a, scan, greater--);
            else scan++;
        }
        if (target < less) right = less - 1;
        else if (target > greater) left = greater + 1;
        else return pivot;
    }
    throw new AssertionError("unreachable");
}
static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }
// Expected O(n), worst O(n^2), O(1) auxiliary space.

static class Fenwick {
    final long[] tree;
    Fenwick(int n) { tree = new long[n + 1]; }
    void add(int index, long delta) { // external zero-based index
        if (index < 0 || index >= tree.length - 1) throw new IndexOutOfBoundsException();
        for (int i = index + 1; i < tree.length; i += i & -i) tree[i] += delta;
    }
    long prefix(int end) { // sum of [0,end)
        if (end < 0 || end >= tree.length) throw new IndexOutOfBoundsException();
        long sum = 0;
        for (int i = end; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
    long range(int left, int right) { return prefix(right) - prefix(left); }
}
// O(log n) per add/query, O(n) storage. Valid range: 0 <= left <= right <= n.

static class LruCache {
    final int capacity;
    final LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
    LruCache(int capacity) {
        if (capacity < 0) throw new IllegalArgumentException("capacity");
        this.capacity = capacity;
    }
    Integer get(int key) { return map.get(key); } // null if absent; refreshes recency
    void put(int key, int value) {
        map.put(key, value);
        if (map.size() > capacity) {
            Iterator<Integer> iterator = map.keySet().iterator();
            iterator.next(); iterator.remove(); // least recently accessed
        }
    }
}
// Expected O(1) get/put, O(capacity) storage; not thread-safe.
// If asked to implement internals, explain/map out hash map + doubly linked list.

static final class Cell {
    final int row, col;
    Cell(int row, int col) { this.row = row; this.col = col; }
    @Override public boolean equals(Object other) {
        if (this == other) return true;
        if (!(other instanceof Cell)) return false;
        Cell cell = (Cell) other;
        return row == cell.row && col == cell.col;
    }
    @Override public int hashCode() { return 31 * row + col; }
}
// Set<Cell> cells = new HashSet<>(); cells.add(new Cell(1,2));
// cells.contains(new Cell(1,2)) is true. int[] keys instead use identity equality.
// Hash collisions are allowed; equal objects MUST have equal hash codes.

static long maxSubarray(int[] a) {
    if (a.length == 0) throw new IllegalArgumentException("nonempty array required");
    long endingHere = a[0], best = a[0];
    for (int i = 1; i < a.length; i++) {
        endingHere = Math.max((long) a[i], endingHere + a[i]);
        best = Math.max(best, endingHere);
    }
    return best; // nonempty subarray; O(n), O(1); handles all-negative input
}

static long knapsack(int[] weights, int[] values, int capacity) {
    // Same-length arrays; weights > 0; capacity >= 0; choosing no items allowed.
    long[] dp = new long[capacity + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int room = capacity; room >= weights[i]; room--) {
            dp[room] = Math.max(dp[room], dp[room - weights[i]] + values[i]);
        }
    }
    return dp[capacity]; // O(items*capacity), O(capacity)
    // Descending room prevents reusing this item; ascending would allow reuse.
}

static class ManualLruCache {
    static class Node {
        final int key;
        int value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }
    final int capacity;
    final Map<Integer, Node> map = new HashMap<>();
    final Node head = new Node(0, 0), tail = new Node(0, 0);
    ManualLruCache(int capacity) {
        if (capacity < 0) throw new IllegalArgumentException("capacity");
        this.capacity = capacity;
        head.next = tail; tail.prev = head;
    }
    void unlink(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    void addMostRecent(Node node) { // insert immediately after head sentinel
        node.prev = head; node.next = head.next;
        head.next.prev = node; head.next = node;
    }
    Integer get(int key) {
        Node node = map.get(key);
        if (node == null) return null;
        unlink(node); addMostRecent(node);
        return node.value;
    }
    void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) { node.value = value; unlink(node); }
        else { node = new Node(key, value); map.put(key, node); }
        addMostRecent(node);
        if (map.size() > capacity) {
            Node victim = tail.prev;
            unlink(victim); map.remove(victim.key);
        }
    }
}
// Expected O(1) per get/put, O(capacity) space; zero capacity works.
// Invariant: every map node appears once between head and tail; most recent first.

static boolean isBipartite(List<List<Integer>> graph) {
    // Undirected graph; handles disconnected components and self-loops.
    int[] color = new int[graph.size()]; // 0 unvisited, +1/-1 colors
    Queue<Integer> queue = new ArrayDeque<>();
    for (int start = 0; start < graph.size(); start++) {
        if (color[start] != 0) continue;
        color[start] = 1; queue.offer(start);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : graph.get(u)) {
                if (color[v] == color[u]) return false;
                if (color[v] == 0) { color[v] = -color[u]; queue.offer(v); }
            }
        }
    }
    return true; // O(V+E) time, O(V) auxiliary space
}

static ListNode removeNthFromEnd(ListNode head, int n) {
    // Acyclic list; 1 <= n <= length. Mutates links. Reject invalid n.
    if (n < 1) throw new IllegalArgumentException("n must be positive");
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i < n; i++) {
        if (fast.next == null) throw new IllegalArgumentException("n exceeds length");
        fast = fast.next;
    }
    while (fast.next != null) { fast = fast.next; slow = slow.next; }
    slow.next = slow.next.next;
    return dummy.next; // O(L), O(1)
}
static ListNode middleNode(ListNode head) {
    // Acyclic list; null input returns null; does not mutate links.
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow; // second middle on even length; O(L), O(1)
}
static ListNode reverseKGroup(ListNode head, int k) {
    // Acyclic list; k >= 1. Mutates links; incomplete final group is unchanged.
    if (k < 1) throw new IllegalArgumentException("k must be positive");
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode groupPrev = dummy;
    while (true) {
        ListNode kth = groupPrev;
        for (int i = 0; i < k && kth != null; i++) kth = kth.next;
        if (kth == null) break;
        ListNode groupNext = kth.next;
        ListNode prev = groupNext, cur = groupPrev.next;
        while (cur != groupNext) {
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        ListNode newEnd = groupPrev.next;
        groupPrev.next = kth;
        groupPrev = newEnd;
    }
    return dummy.next; // O(L), O(1)
}

static String minWindow(String s, String t) {
    // Smallest substring of s covering every character of t (counts matter).
    // ASCII. Empty t or |s| < |t| => "".
    if (t.isEmpty() || s.length() < t.length()) return "";
    int[] need = new int[128], window = new int[128];
    int required = 0;
    for (int i = 0; i < t.length(); i++) if (need[t.charAt(i)]++ == 0) required++;
    int formed = 0, left = 0, bestLen = Integer.MAX_VALUE, bestL = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (++window[c] == need[c] && need[c] > 0) formed++;
        while (formed == required) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestL = left;
            }
            char old = s.charAt(left++);
            window[old]--; // keep counts accurate even for characters absent from t
            if (need[old] > 0 && window[old] < need[old]) formed--;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
    // O(|s|+|t|), O(1) extra for ASCII. Track satisfied unique chars, not raw totals.
}

static long[][] prefix2D(int[][] a) {
    // Rectangular input; arithmetic and intermediate sums must fit in long.
    int rows = a.length, cols = rows == 0 ? 0 : a[0].length;
    long[][] p = new long[rows + 1][cols + 1];
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            p[i + 1][j + 1] = a[i][j] + p[i][j + 1] + p[i + 1][j] - p[i][j];
        }
    }
    return p; // Build time/space O((rows+1)*(cols+1)); rectangle queries are O(1).
    // Inclusive rectangle: p[r2+1][c2+1]-p[r1][c2+1]-p[r2+1][c1]+p[r1][c1].
}
static void rangeAdd(long[] diff, int left, int right, long val) {
    // Inclusive [left,right]; diff.length == n+1; 0 <= left <= right < n.
    // Start with a zeroed diff array; all update arithmetic must fit in long.
    if (left < 0 || left > right || right >= diff.length - 1)
        throw new IllegalArgumentException("invalid range");
    diff[left] += val;
    diff[right + 1] -= val; // sentinel is always allocated; O(1) update
}
static long[] materialize(long[] diff, int n) {
    // Produces accumulated increments to an initially zero array, not an existing base.
    if (n < 0 || n != diff.length - 1) throw new IllegalArgumentException("invalid n");
    long[] a = new long[n];
    long cur = 0;
    for (int i = 0; i < n; i++) { cur += diff[i]; a[i] = cur; }
    return a; // O(n) time/output space, O(1) auxiliary space beyond output
}

static int[] zeroOneBfs(List<List<int[]>> graph, int source) {
    // Vertex IDs 0..n-1; valid source; entries {to, weight}, weight in {0,1}.
    // O(V+E) time; a specialized alternative to Dijkstra, which also works here.
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    Deque<Integer> deque = new ArrayDeque<>();
    dist[source] = 0;
    deque.offer(source);
    while (!deque.isEmpty()) {
        int u = deque.pollFirst();
        for (int[] edge : graph.get(u)) {
            int v = edge[0], w = edge[1], nd = dist[u] + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                if (w == 0) deque.offerFirst(v);
                else deque.offerLast(v);
            }
        }
    }
    return dist; // Integer.MAX_VALUE means unreachable; O(V+E) space upper bound
}

static int numIslands(char[][] grid) {
    // Rectangular '0'/'1' grid, 4-neighbor; mutates '1' -> '0'.
    // Iterative to avoid StackOverflowError on snakes; copy input to preserve it.
    if (grid.length == 0) return 0;
    int rows = grid.length, cols = grid[0].length, count = 0;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    Deque<int[]> stack = new ArrayDeque<>();
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] != '1') continue;
            count++;
            grid[r][c] = '0';
            stack.push(new int[]{r, c});
            while (!stack.isEmpty()) {
                int[] cell = stack.pop();
                for (int[] d : dirs) {
                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
                    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] != '1') continue;
                    grid[nr][nc] = '0'; // mark when pushing
                    stack.push(new int[]{nr, nc});
                }
            }
        }
    }
    return count; // O(rows*cols) time and worst-case stack space
}