import java.util.*;

class Solution {
    /**
     * Brute-force pairwise scan. Quadratic — useful only as a correctness baseline.
     * @param nums input array (non-null per problem constraints)
     * @return true iff any value repeats
     */
    public boolean containsDuplicate(final int[] nums) {
        if (nums == null || nums.length < 2) return false;
        final int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j]) return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.containsDuplicate(new int[]{1,2,3,1}));      // true
        System.out.println(s.containsDuplicate(new int[]{1,2,3,4}));      // false
        System.out.println(s.containsDuplicate(new int[]{}));             // false (edge)
        System.out.println(s.containsDuplicate(new int[]{7}));            // false (edge)
    }
}

import java.util.*;

class Solution {
    /**
     * Single-pass HashSet probe — the textbook ship-it answer.
     * Pre-sizing the set avoids rehash storms when n is known.
     */
    public boolean containsDuplicate(final int[] nums) {
        if (nums == null || nums.length < 2) return false;
        // Pre-size: load factor 0.75 → capacity = ceil(n / 0.75)
        final Set<Integer> seen = new HashSet<>((int) (nums.length / 0.75f) + 1);
        for (final int x : nums) {
            if (!seen.add(x)) return true;     // .add returns false on duplicate
        }
        return false;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.containsDuplicate(new int[]{1,2,3,1}));               // true
        System.out.println(s.containsDuplicate(new int[]{1,2,3,4}));               // false
        System.out.println(s.containsDuplicate(new int[]{1,1,1,3,3,4,3,2,4,2}));   // true
    }
}

import java.util.*;

class Solution {
    /**
     * Sort-then-scan. O(n log n) but cache-friendly and zero auxiliary heap.
     * Mutates the input — caller must accept this or pass a copy.
     */
    public boolean containsDuplicate(final int[] nums) {
        if (nums == null || nums.length < 2) return false;
        Arrays.sort(nums);   // in-place dual-pivot quicksort on primitives
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.containsDuplicate(new int[]{1,2,3,1}));   // true
        System.out.println(s.containsDuplicate(new int[]{1,2,3,4}));   // false
    }
}

import java.util.Arrays;

class Solution {
    public boolean isAnagram(final String s, final String t) {
        if (s == null || t == null || s.length() != t.length()) return false;
        final char[] a = s.toCharArray();
        final char[] b = t.toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);
        return Arrays.equals(a, b);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isAnagram("anagram", "nagaram"));   // true
        System.out.println(sol.isAnagram("rat", "car"));           // false
        System.out.println(sol.isAnagram("a", "ab"));              // false
    }
}

class Solution {
    public boolean isAnagram(final String s, final String t) {
        if (s == null || t == null || s.length() != t.length()) return false;
        final int[] counts = new int[26];   // lowercase ASCII alphabet
        for (int i = 0, n = s.length(); i < n; i++) {
            counts[s.charAt(i) - 'a']++;
            counts[t.charAt(i) - 'a']--;
        }
        for (final int c : counts) if (c != 0) return false;
        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isAnagram("anagram", "nagaram"));   // true
        System.out.println(sol.isAnagram("rat", "car"));           // false
    }
}

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isAnagram(final String s, final String t) {
        if (s == null || t == null || s.length() != t.length()) return false;
        final Map<Character, Integer> counts = new HashMap<>(Math.min(s.length(), 128));
        for (final char c : s.toCharArray()) counts.merge(c, 1, Integer::sum);
        for (final char c : t.toCharArray()) {
            final Integer v = counts.get(c);
            if (v == null || v == 0) return false;
            counts.put(c, v - 1);
        }
        return true;
    }
    /* Unicode-safe variant: iterate s.codePoints().forEach(...) and use Map<Integer,Integer>. */

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isAnagram("anagram", "nagaram"));   // true
        System.out.println(sol.isAnagram("rat", "car"));           // false
    }
}

class Solution {
    public int[] twoSum(final int[] nums, final int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) return new int[]{i, j};
            }
        }
        throw new IllegalArgumentException("No two-sum solution");
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(java.util.Arrays.toString(s.twoSum(new int[]{2,7,11,15}, 9)));   // [0, 1]
        System.out.println(java.util.Arrays.toString(s.twoSum(new int[]{3,2,4}, 6)));       // [1, 2]
    }
}

import java.util.HashMap;
import java.util.Map;

class Solution {
    /**
     * Single-pass: for each x, look up target - x in the map.
     * Insert AFTER the lookup so we never pair an element with itself.
     */
    public int[] twoSum(final int[] nums, final int target) {
        final Map<Integer, Integer> seen = new HashMap<>((int) (nums.length / 0.75f) + 1);
        for (int i = 0; i < nums.length; i++) {
            final int need = target - nums[i];
            final Integer j = seen.get(need);
            if (j != null) return new int[]{j, i};
            seen.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two-sum solution");
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(java.util.Arrays.toString(s.twoSum(new int[]{2,7,11,15}, 9)));   // [0, 1]
        System.out.println(java.util.Arrays.toString(s.twoSum(new int[]{3,3}, 6)));         // [0, 1]
    }
}

import java.util.Arrays;

class Solution {
    /**
     * Sort + two pointers. We keep original indices alongside values to
     * satisfy the index-return contract. O(n log n) time.
     */
    public int[] twoSum(final int[] nums, final int target) {
        final int n = nums.length;
        final int[][] pairs = new int[n][2];
        for (int i = 0; i < n; i++) { pairs[i][0] = nums[i]; pairs[i][1] = i; }
        Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));
        int l = 0, r = n - 1;
        while (l < r) {
            final long sum = (long) pairs[l][0] + pairs[r][0];   // long to avoid overflow
            if (sum == target) return new int[]{pairs[l][1], pairs[r][1]};
            if (sum < target) l++; else r--;
        }
        throw new IllegalArgumentException("No two-sum solution");
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(java.util.Arrays.toString(s.twoSum(new int[]{2,7,11,15}, 9)));   // some valid pair
    }
}

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(final String[] strs) {
        final List<List<String>> groups = new ArrayList<>();
        for (final String s : strs) {
            boolean placed = false;
            for (final List<String> g : groups) {
                if (isAnagram(s, g.get(0))) { g.add(s); placed = true; break; }
            }
            if (!placed) { final List<String> ng = new ArrayList<>(); ng.add(s); groups.add(ng); }
        }
        return groups;
    }

    private boolean isAnagram(final String a, final String b) {
        if (a.length() != b.length()) return false;
        final char[] ca = a.toCharArray(); final char[] cb = b.toCharArray();
        Arrays.sort(ca); Arrays.sort(cb);
        return Arrays.equals(ca, cb);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.groupAnagrams(new String[]{"eat","tea","tan","ate","nat","bat"}));
    }
}

import java.util.*;

class Solution {
    /**
     * Canonical form by sort. Cleanest reading; O(n·k log k) total work.
     */
    public List<List<String>> groupAnagrams(final String[] strs) {
        final Map<String, List<String>> groups = new HashMap<>();
        for (final String s : strs) {
            final char[] chars = s.toCharArray();
            Arrays.sort(chars);
            final String key = new String(chars);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.groupAnagrams(new String[]{"eat","tea","tan","ate","nat","bat"}));
    }
}

import java.util.*;

class Solution {
    /**
     * Frequency-vector canonical form: O(n·k) total. Beats the sort-key
     * approach when k log k > k (always for k ≥ 4 with cache-friendly arrays).
     */
    public List<List<String>> groupAnagrams(final String[] strs) {
        final Map<String, List<String>> groups = new HashMap<>();
        for (final String s : strs) {
            final int[] counts = new int[26];
            for (int i = 0; i < s.length(); i++) counts[s.charAt(i) - 'a']++;
            // Build a delimited signature; '#' avoids 'a11' colliding with 'a1+a1'.
            final StringBuilder sb = new StringBuilder(60);
            for (final int c : counts) { sb.append('#').append(c); }
            groups.computeIfAbsent(sb.toString(), k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.groupAnagrams(new String[]{"eat","tea","tan","ate","nat","bat"}));
    }
}

import java.util.*;

class Solution {
    public int[] topKFrequent(final int[] nums, final int k) {
        final Map<Integer,Integer> freq = new HashMap<>();
        for (final int x : nums) freq.merge(x, 1, Integer::sum);
        final List<Map.Entry<Integer,Integer>> entries = new ArrayList<>(freq.entrySet());
        entries.sort((a,b) -> b.getValue() - a.getValue());
        final int[] out = new int[k];
        for (int i = 0; i < k; i++) out[i] = entries.get(i).getKey();
        return out;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution().topKFrequent(new int[]{1,1,1,2,2,3}, 2)));
    }
}

import java.util.*;

class Solution {
    public int[] topKFrequent(final int[] nums, final int k) {
        final Map<Integer,Integer> freq = new HashMap<>();
        for (final int x : nums) freq.merge(x, 1, Integer::sum);
        // Min-heap so that the smallest count is at the top — that's who gets evicted.
        final PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> a[1] - b[1]);
        for (final Map.Entry<Integer,Integer> e : freq.entrySet()) {
            heap.offer(new int[]{e.getKey(), e.getValue()});
            if (heap.size() > k) heap.poll();
        }
        final int[] out = new int[k];
        for (int i = k - 1; i >= 0; i--) out[i] = heap.poll()[0];
        return out;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution().topKFrequent(new int[]{1,1,1,2,2,3}, 2)));
    }
}

import java.util.*;

class Solution {
    /**
     * Bucket sort by frequency: O(n) optimal. Frequencies are bounded by n,
     * so we sidestep the heap's log factor entirely.
     */
    public int[] topKFrequent(final int[] nums, final int k) {
        final int n = nums.length;
        final Map<Integer,Integer> freq = new HashMap<>();
        for (final int x : nums) freq.merge(x, 1, Integer::sum);

        final List<List<Integer>> buckets = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) buckets.add(new ArrayList<>());
        for (final Map.Entry<Integer,Integer> e : freq.entrySet()) {
            buckets.get(e.getValue()).add(e.getKey());
        }

        final int[] out = new int[k];
        int idx = 0;
        for (int i = n; i >= 1 && idx < k; i--) {
            for (final int v : buckets.get(i)) {
                out[idx++] = v;
                if (idx == k) break;
            }
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution().topKFrequent(new int[]{1,1,1,2,2,3}, 2)));
    }
}

import java.util.*;

class Codec {
    /** BROKEN encode — used only as a discussion baseline. Do not ship. */
    public String encode(final List<String> strs) {
        return String.join("#", strs);   // collapses if any payload contains '#'
    }
    public List<String> decode(final String s) {
        return Arrays.asList(s.split("#", -1));   // round-trips ONLY for delimiter-free inputs
    }

    public static void main(String[] args) {
        Codec c = new Codec();
        List<String> in = Arrays.asList("a","#","b");
        System.out.println(c.decode(c.encode(in)));   // [a, , , b]  ← BROKEN
    }
}

import java.util.*;

class Codec {
    /**
     * Length-prefix framing: '<len>#<payload>' per string, concatenated.
     * Robust against any payload character because we never split — we
     * read exactly len chars after the '#'.
     */
    public String encode(final List<String> strs) {
        final StringBuilder sb = new StringBuilder();
        for (final String s : strs) sb.append(s.length()).append('#').append(s);
        return sb.toString();
    }

    public List<String> decode(final String s) {
        final List<String> out = new ArrayList<>();
        int i = 0;
        final int n = s.length();
        while (i < n) {
            final int hash = s.indexOf('#', i);
            final int len = Integer.parseInt(s, i, hash, 10);   // JDK 9+
            out.add(s.substring(hash + 1, hash + 1 + len));
            i = hash + 1 + len;
        }
        return out;
    }

    public static void main(String[] args) {
        Codec c = new Codec();
        List<String> in = Arrays.asList("lint","code","love","you","","#3#");
        System.out.println(c.decode(c.encode(in)));   // round-trips perfectly
    }
}

import java.util.*;

class Codec {
    private static final char DELIM = '|';
    private static final char ESC = '\\';

    public String encode(final List<String> strs) {
        final StringBuilder sb = new StringBuilder();
        for (final String s : strs) {
            for (int i = 0; i < s.length(); i++) {
                final char c = s.charAt(i);
                if (c == DELIM || c == ESC) sb.append(ESC);
                sb.append(c);
            }
            sb.append(DELIM);
        }
        return sb.toString();
    }

    public List<String> decode(final String s) {
        final List<String> out = new ArrayList<>();
        final StringBuilder cur = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            final char c = s.charAt(i);
            if (c == ESC && i + 1 < s.length()) {
                cur.append(s.charAt(++i));
            } else if (c == DELIM) {
                out.add(cur.toString());
                cur.setLength(0);
            } else {
                cur.append(c);
            }
        }
        return out;
    }

    public static void main(String[] args) {
        Codec c = new Codec();
        System.out.println(c.decode(c.encode(Arrays.asList("a","|","\\","#3#",""))));
    }
}

class Solution {
    /** SHOWS WHY DIVISION IS WRONG: zeros break it; problem also forbids /. */
    public int[] productExceptSelfDivisionVariant(final int[] nums) {
        int total = 1, zeros = 0, zeroIdx = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) { zeros++; zeroIdx = i; }
            else total *= nums[i];
        }
        final int[] out = new int[nums.length];
        if (zeros >= 2) return out;             // all zero
        if (zeros == 1) { out[zeroIdx] = total; return out; }
        for (int i = 0; i < nums.length; i++) out[i] = total / nums[i];
        return out;
    }

    public static void main(String[] args) {
        // For instructional comparison only — do not ship.
    }
}

class Solution {
    /** Prefix and suffix product arrays — clearest possible reading. */
    public int[] productExceptSelf(final int[] nums) {
        final int n = nums.length;
        final int[] left = new int[n];
        final int[] right = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) left[i] = left[i-1] * nums[i-1];
        right[n-1] = 1;
        for (int i = n-2; i >= 0; i--) right[i] = right[i+1] * nums[i+1];
        final int[] out = new int[n];
        for (int i = 0; i < n; i++) out[i] = left[i] * right[i];
        return out;
    }

    public static void main(String[] args) {
        System.out.println(java.util.Arrays.toString(new Solution().productExceptSelf(new int[]{1,2,3,4})));
    }
}

class Solution {
    /**
     * O(1) extra space (output excluded). Two passes:
     *   pass 1: out[i] = product of nums[0..i-1]   (prefix)
     *   pass 2: walk right-to-left; multiply in running 'right' (suffix)
     */
    public int[] productExceptSelf(final int[] nums) {
        final int n = nums.length;
        final int[] out = new int[n];
        out[0] = 1;
        for (int i = 1; i < n; i++) out[i] = out[i-1] * nums[i-1];
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            out[i] *= right;
            right *= nums[i];
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(java.util.Arrays.toString(new Solution().productExceptSelf(new int[]{1,2,3,4})));
        System.out.println(java.util.Arrays.toString(new Solution().productExceptSelf(new int[]{-1,1,0,-3,3})));
    }
}

class Solution {
    public boolean isValidSudoku(final char[][] board) {
        for (int r = 0; r < 9; r++) {
            final boolean[] seen = new boolean[10];
            for (int c = 0; c < 9; c++) {
                final char ch = board[r][c];
                if (ch == '.') continue;
                final int d = ch - '0';
                if (seen[d]) return false;
                seen[d] = true;
            }
        }
        for (int c = 0; c < 9; c++) {
            final boolean[] seen = new boolean[10];
            for (int r = 0; r < 9; r++) {
                final char ch = board[r][c];
                if (ch == '.') continue;
                final int d = ch - '0';
                if (seen[d]) return false;
                seen[d] = true;
            }
        }
        for (int br = 0; br < 9; br += 3) for (int bc = 0; bc < 9; bc += 3) {
            final boolean[] seen = new boolean[10];
            for (int r = br; r < br + 3; r++) for (int c = bc; c < bc + 3; c++) {
                final char ch = board[r][c];
                if (ch == '.') continue;
                final int d = ch - '0';
                if (seen[d]) return false;
                seen[d] = true;
            }
        }
        return true;
    }
}

import java.util.*;

class Solution {
    public boolean isValidSudoku(final char[][] board) {
        final Set<String> seen = new HashSet<>(243);   // 3 keys × 81 cells, sized
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                final char ch = board[r][c];
                if (ch == '.') continue;
                final int b = (r / 3) * 3 + (c / 3);
                if (!seen.add("R" + r + ch) ||
                    !seen.add("C" + c + ch) ||
                    !seen.add("B" + b + ch)) return false;
            }
        }
        return true;
    }
}

class Solution {
    /**
     * Bitmask Sudoku validator. 27 ints, no allocations during the pass.
     * Each bit position 1..9 represents whether that digit has appeared.
     */
    public boolean isValidSudoku(final char[][] board) {
        final int[] rows = new int[9];
        final int[] cols = new int[9];
        final int[] boxes = new int[9];
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                final char ch = board[r][c];
                if (ch == '.') continue;
                final int mask = 1 << (ch - '0');
                final int b = (r / 3) * 3 + (c / 3);
                if ((rows[r] & mask) != 0 || (cols[c] & mask) != 0 || (boxes[b] & mask) != 0) return false;
                rows[r] |= mask; cols[c] |= mask; boxes[b] |= mask;
            }
        }
        return true;
    }
}

import java.util.*;

class Solution {
    public int longestConsecutive(final int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        Arrays.sort(nums);
        int best = 1, run = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) continue;
            run = (nums[i] == nums[i-1] + 1) ? run + 1 : 1;
            best = Math.max(best, run);
        }
        return best;
    }
}

import java.util.*;

class Solution {
    /**
     * Hash-set with start-of-run detection. The key insight: only initiate
     * the forward walk when x-1 is NOT in the set, ensuring each integer
     * is touched at most twice across the whole algorithm.
     */
    public int longestConsecutive(final int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        final Set<Integer> S = new HashSet<>((int) (nums.length / 0.75f) + 1);
        for (final int x : nums) S.add(x);
        int best = 0;
        for (final int x : S) {
            if (S.contains(x - 1)) continue;        // not a run start
            int cur = x;
            while (S.contains(cur + 1)) cur++;
            best = Math.max(best, cur - x + 1);
        }
        return best;
    }
}

import java.util.*;

class Solution {
    private final Map<Integer,Integer> parent = new HashMap<>();
    private final Map<Integer,Integer> size = new HashMap<>();

    private int find(int x) {
        while (parent.get(x) != x) { parent.put(x, parent.get(parent.get(x))); x = parent.get(x); }
        return x;
    }
    private void union(int a, int b) {
        final int ra = find(a), rb = find(b);
        if (ra == rb) return;
        final int sa = size.get(ra), sb = size.get(rb);
        if (sa < sb) { parent.put(ra, rb); size.put(rb, sa + sb); }
        else         { parent.put(rb, ra); size.put(ra, sa + sb); }
    }

    public int longestConsecutive(final int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        for (final int x : nums) { parent.putIfAbsent(x, x); size.putIfAbsent(x, 1); }
        for (final int x : nums) {
            if (parent.containsKey(x - 1)) union(x, x - 1);
            if (parent.containsKey(x + 1)) union(x, x + 1);
        }
        int best = 0;
        for (final int x : parent.keySet()) if (find(x) == x) best = Math.max(best, size.get(x));
        return best;
    }
}

class Solution {
    public boolean isPalindrome(final String s) {
        final StringBuilder sb = new StringBuilder(s.length());
        for (int i = 0; i < s.length(); i++) {
            final char c = s.charAt(i);
            if (Character.isLetterOrDigit(c)) sb.append(Character.toLowerCase(c));
        }
        return sb.toString().equals(sb.reverse().toString());
    }
}

class Solution {
    public boolean isPalindrome(final String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            while (l < r && !isAlnum(s.charAt(l))) l++;
            while (l < r && !isAlnum(s.charAt(r))) r--;
            if (toLower(s.charAt(l)) != toLower(s.charAt(r))) return false;
            l++; r--;
        }
        return true;
    }
    private static boolean isAlnum(final char c) {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
    }
    private static char toLower(final char c) {
        return (c >= 'A' && c <= 'Z') ? (char)(c + 32) : c;
    }
}

class Solution {
    public boolean isPalindrome(final String s) {
        final char[] buf = new char[s.length()];
        int n = 0;
        for (int i = 0; i < s.length(); i++) {
            final char c = s.charAt(i);
            if ((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')) buf[n++] = c;
            else if (c >= 'A' && c <= 'Z') buf[n++] = (char)(c + 32);
        }
        int l = 0, r = n - 1;
        while (l < r) {
            if (buf[l] != buf[r]) return false;
            l++; r--;
        }
        return true;
    }
}

class Solution {
    public int[] twoSum(final int[] numbers, final int target) {
        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) return new int[]{i+1, j+1};
            }
        }
        throw new IllegalArgumentException();
    }
}

class Solution {
    /** Two pointers — the canonical sorted-array template. */
    public int[] twoSum(final int[] numbers, final int target) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            final int s = numbers[l] + numbers[r];
            if (s == target) return new int[]{l + 1, r + 1};
            if (s < target) l++; else r--;
        }
        throw new IllegalArgumentException("No two-sum solution");
    }

    public static void main(String[] args) {
        System.out.println(java.util.Arrays.toString(new Solution().twoSum(new int[]{2,7,11,15}, 9)));
    }
}

class Solution {
    public int[] twoSum(final int[] numbers, final int target) {
        for (int i = 0; i < numbers.length - 1; i++) {
            int lo = i + 1, hi = numbers.length - 1;
            final int need = target - numbers[i];
            while (lo <= hi) {
                final int mid = lo + (hi - lo) / 2;
                if (numbers[mid] == need) return new int[]{i + 1, mid + 1};
                if (numbers[mid] < need) lo = mid + 1; else hi = mid - 1;
            }
        }
        throw new IllegalArgumentException();
    }
}

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(final int[] nums) {
        final Set<List<Integer>> seen = new HashSet<>();
        final int n = nums.length;
        for (int i = 0; i < n - 2; i++) for (int j = i+1; j < n-1; j++) for (int k = j+1; k < n; k++) {
            if (nums[i] + nums[j] + nums[k] == 0) {
                final List<Integer> t = Arrays.asList(nums[i], nums[j], nums[k]);
                Collections.sort(t);
                seen.add(t);
            }
        }
        return new ArrayList<>(seen);
    }
}

import java.util.*;

class Solution {
    /**
     * Sort + two-pointer composition. O(n^2). Skip duplicates at every level
     * to satisfy the unique-triplets contract.
     */
    public List<List<Integer>> threeSum(final int[] nums) {
        Arrays.sort(nums);
        final List<List<Integer>> out = new ArrayList<>();
        final int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] > 0) break;                         // sorted, no triplet possible
            if (i > 0 && nums[i] == nums[i-1]) continue;    // skip duplicate anchor
            int l = i + 1, r = n - 1;
            while (l < r) {
                final int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    out.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    l++; r--;
                    while (l < r && nums[l] == nums[l-1]) l++;
                    while (l < r && nums[r] == nums[r+1]) r--;
                } else if (sum < 0) l++;
                else r--;
            }
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().threeSum(new int[]{-1,0,1,2,-1,-4}));
    }
}

import java.util.*;

class Solution {
    public List<List<Integer>> threeSum(final int[] nums) {
        Arrays.sort(nums);
        final List<List<Integer>> out = new ArrayList<>();
        final int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i-1]) continue;
            final Set<Integer> seen = new HashSet<>();
            for (int j = i + 1; j < n; j++) {
                final int need = -nums[i] - nums[j];
                if (seen.contains(need)) {
                    out.add(Arrays.asList(nums[i], need, nums[j]));
                    while (j + 1 < n && nums[j+1] == nums[j]) j++;
                }
                seen.add(nums[j]);
            }
        }
        return out;
    }
}

class Solution {
    public int maxArea(final int[] height) {
        int best = 0;
        for (int i = 0; i < height.length - 1; i++)
            for (int j = i + 1; j < height.length; j++)
                best = Math.max(best, (j - i) * Math.min(height[i], height[j]));
        return best;
    }
}

class Solution {
    /**
     * Two pointers; always shrink toward the shorter side. The monotonic
     * argument: keeping the shorter side guarantees the new area is <=
     * the old, so abandoning it is the only progress move.
     */
    public int maxArea(final int[] height) {
        int l = 0, r = height.length - 1, best = 0;
        while (l < r) {
            final int h = Math.min(height[l], height[r]);
            best = Math.max(best, (r - l) * h);
            if (height[l] < height[r]) l++; else r--;
        }
        return best;
    }
}

class Solution {
    public int maxArea(final int[] height) {
        int l = 0, r = height.length - 1, best = 0;
        while (l < r) {
            final int h = Math.min(height[l], height[r]);
            best = Math.max(best, (r - l) * h);
            if (height[l] < height[r]) {
                final int prev = height[l++];
                while (l < r && height[l] <= prev) l++;
            } else {
                final int prev = height[r--];
                while (l < r && height[r] <= prev) r--;
            }
        }
        return best;
    }
}

class Solution {
    public int trap(final int[] height) {
        int total = 0;
        for (int i = 0; i < height.length; i++) {
            int L = 0, R = 0;
            for (int j = 0; j <= i; j++) L = Math.max(L, height[j]);
            for (int j = i; j < height.length; j++) R = Math.max(R, height[j]);
            total += Math.max(0, Math.min(L, R) - height[i]);
        }
        return total;
    }
}

class Solution {
    public int trap(final int[] height) {
        final int n = height.length;
        if (n == 0) return 0;
        final int[] L = new int[n];
        final int[] R = new int[n];
        L[0] = height[0];
        for (int i = 1; i < n; i++) L[i] = Math.max(L[i-1], height[i]);
        R[n-1] = height[n-1];
        for (int i = n - 2; i >= 0; i--) R[i] = Math.max(R[i+1], height[i]);
        int total = 0;
        for (int i = 0; i < n; i++) total += Math.min(L[i], R[i]) - height[i];
        return total;
    }
}

class Solution {
    /**
     * Two-pointer rainwater. Always advance from the lower wall — its
     * opposing wall is guaranteed at least as tall, so the running max
     * on the lower side fully determines water above each step.
     */
    public int trap(final int[] height) {
        int l = 0, r = height.length - 1;
        int lmax = 0, rmax = 0, total = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                if (height[l] >= lmax) lmax = height[l];
                else total += lmax - height[l];
                l++;
            } else {
                if (height[r] >= rmax) rmax = height[r];
                else total += rmax - height[r];
                r--;
            }
        }
        return total;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));   // 6
    }
}

class Solution {
    public int maxProfit(final int[] prices) {
        int best = 0;
        for (int i = 0; i < prices.length - 1; i++)
            for (int j = i + 1; j < prices.length; j++)
                best = Math.max(best, prices[j] - prices[i]);
        return best;
    }
}

class Solution {
    public int maxProfit(final int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int best = 0;
        for (final int p : prices) {
            if (p < minPrice) minPrice = p;
            else if (p - minPrice > best) best = p - minPrice;
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().maxProfit(new int[]{7,1,5,3,6,4}));   // 5
    }
}

class Solution {
    public int maxProfit(final int[] prices) {
        int l = 0, best = 0;
        for (int r = 1; r < prices.length; r++) {
            if (prices[r] < prices[l]) l = r;
            else best = Math.max(best, prices[r] - prices[l]);
        }
        return best;
    }
}

import java.util.*;
class Solution {
    public int lengthOfLongestSubstring(final String s) {
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            final Set<Character> seen = new HashSet<>();
            for (int j = i; j < s.length(); j++) {
                if (!seen.add(s.charAt(j))) break;
                best = Math.max(best, j - i + 1);
            }
        }
        return best;
    }
}

import java.util.*;
class Solution {
    public int lengthOfLongestSubstring(final String s) {
        final Set<Character> seen = new HashSet<>();
        int l = 0, best = 0;
        for (int r = 0; r < s.length(); r++) {
            while (!seen.add(s.charAt(r))) {
                seen.remove(s.charAt(l++));
            }
            best = Math.max(best, r - l + 1);
        }
        return best;
    }
}

import java.util.*;
class Solution {
    /**
     * Last-seen index map — O(n) with single-step pointer jumps.
     * Faster than the set-based variant on adversarial inputs because
     * 'l' advances in O(1) rather than inching through the window.
     */
    public int lengthOfLongestSubstring(final String s) {
        final Map<Character, Integer> last = new HashMap<>();
        int l = 0, best = 0;
        for (int r = 0; r < s.length(); r++) {
            final char c = s.charAt(r);
            final Integer prev = last.get(c);
            if (prev != null && prev >= l) l = prev + 1;
            last.put(c, r);
            best = Math.max(best, r - l + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().lengthOfLongestSubstring("abcabcbb"));   // 3
        System.out.println(new Solution().lengthOfLongestSubstring("pwwkew"));     // 3
    }
}

class Solution {
    public int characterReplacement(final String s, final int k) {
        int best = 0;
        for (int l = 0; l < s.length(); l++) {
            final int[] c = new int[26];
            int max = 0;
            for (int r = l; r < s.length(); r++) {
                c[s.charAt(r) - 'A']++;
                max = Math.max(max, c[s.charAt(r) - 'A']);
                if ((r - l + 1) - max <= k) best = Math.max(best, r - l + 1);
            }
        }
        return best;
    }
}

class Solution {
    public int characterReplacement(final String s, final int k) {
        final int[] counts = new int[26];
        int l = 0, maxFreq = 0, best = 0;
        for (int r = 0; r < s.length(); r++) {
            counts[s.charAt(r) - 'A']++;
            if (counts[s.charAt(r) - 'A'] > maxFreq) maxFreq = counts[s.charAt(r) - 'A'];
            // Note: maxFreq is intentionally not refreshed when shrinking — see comment block.
            while ((r - l + 1) - maxFreq > k) {
                counts[s.charAt(l) - 'A']--;
                l++;
            }
            best = Math.max(best, r - l + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().characterReplacement("AABABBA", 1));   // 4
    }
}

class Solution {
    public int characterReplacement(final String s, final int k) {
        int best = 0;
        for (char T = 'A'; T <= 'Z'; T++) {
            int l = 0, cnt = 0;
            for (int r = 0; r < s.length(); r++) {
                if (s.charAt(r) == T) cnt++;
                while ((r - l + 1) - cnt > k) {
                    if (s.charAt(l) == T) cnt--;
                    l++;
                }
                best = Math.max(best, r - l + 1);
            }
        }
        return best;
    }
}

class Solution {
    public boolean checkInclusion(final String s1, final String s2) {
        if (s1.length() > s2.length()) return false;
        final int[] target = new int[26];
        for (final char c : s1.toCharArray()) target[c - 'a']++;
        for (int i = 0; i + s1.length() <= s2.length(); i++) {
            final int[] win = new int[26];
            for (int j = 0; j < s1.length(); j++) win[s2.charAt(i + j) - 'a']++;
            if (java.util.Arrays.equals(target, win)) return true;
        }
        return false;
    }
}

import java.util.Arrays;

class Solution {
    public boolean checkInclusion(final String s1, final String s2) {
        final int m = s1.length(), n = s2.length();
        if (m > n) return false;
        final int[] target = new int[26];
        final int[] win = new int[26];
        for (int i = 0; i < m; i++) {
            target[s1.charAt(i) - 'a']++;
            win[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(target, win)) return true;
        for (int r = m; r < n; r++) {
            win[s2.charAt(r) - 'a']++;
            win[s2.charAt(r - m) - 'a']--;
            if (Arrays.equals(target, win)) return true;
        }
        return false;
    }
}

class Solution {
    public boolean checkInclusion(final String s1, final String s2) {
        final int m = s1.length(), n = s2.length();
        if (m > n) return false;
        final int[] target = new int[26];
        final int[] win = new int[26];
        for (int i = 0; i < m; i++) {
            target[s1.charAt(i) - 'a']++;
            win[s2.charAt(i) - 'a']++;
        }
        int matches = 0;
        for (int i = 0; i < 26; i++) if (win[i] == target[i]) matches++;
        if (matches == 26) return true;
        for (int r = m; r < n; r++) {
            final int add = s2.charAt(r) - 'a';
            final int rem = s2.charAt(r - m) - 'a';
            // add char
            if (win[add] == target[add]) matches--;
            win[add]++;
            if (win[add] == target[add]) matches++;
            // remove char
            if (win[rem] == target[rem]) matches--;
            win[rem]--;
            if (win[rem] == target[rem]) matches++;
            if (matches == 26) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().checkInclusion("ab", "eidbaooo"));   // true
    }
}

import java.util.*;
class Solution {
    public String minWindow(final String s, final String t) {
        if (t.length() > s.length()) return "";
        final int[] need = new int[128];
        for (final char c : t.toCharArray()) need[c]++;
        int bestL = -1, bestLen = Integer.MAX_VALUE;
        for (int l = 0; l < s.length(); l++) {
            final int[] have = new int[128];
            for (int r = l; r < s.length(); r++) {
                have[s.charAt(r)]++;
                if (covers(have, need) && r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; break; }
            }
        }
        return bestL == -1 ? "" : s.substring(bestL, bestL + bestLen);
    }
    private boolean covers(final int[] have, final int[] need) {
        for (int i = 0; i < 128; i++) if (have[i] < need[i]) return false;
        return true;
    }
}

import java.util.*;

class Solution {
    /**
     * Sliding window with 'formed' counter tracking how many distinct chars
     * have hit their required count.
     */
    public String minWindow(final String s, final String t) {
        if (t.length() > s.length()) return "";
        final int[] need = new int[128];
        int required = 0;
        for (final char c : t.toCharArray()) { if (need[c]++ == 0) required++; }
        final int[] have = new int[128];
        int formed = 0, l = 0, bestL = 0, bestLen = Integer.MAX_VALUE;
        for (int r = 0; r < s.length(); r++) {
            final char cr = s.charAt(r);
            have[cr]++;
            if (have[cr] == need[cr]) formed++;
            while (formed == required) {
                if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestL = l; }
                final char cl = s.charAt(l);
                have[cl]--;
                if (have[cl] < need[cl]) formed--;
                l++;
            }
        }
        return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestL, bestL + bestLen);
    }

    public static void main(String[] args) {
        System.out.println(new Solution().minWindow("ADOBECODEBANC", "ABC"));   // BANC
    }
}

import java.util.*;

class Solution {
    public String minWindow(final String s, final String t) {
        if (t.length() > s.length()) return "";
        final int[] need = new int[128];
        int required = 0;
        for (final char c : t.toCharArray()) { if (need[c]++ == 0) required++; }
        // Build filtered: only positions whose char is in t
        final List<int[]> filtered = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) if (need[s.charAt(i)] > 0) filtered.add(new int[]{i, s.charAt(i)});
        final int[] have = new int[128];
        int formed = 0, l = 0, bestL = 0, bestR = -1, bestLen = Integer.MAX_VALUE;
        for (int r = 0; r < filtered.size(); r++) {
            final int cr = filtered.get(r)[1];
            have[cr]++;
            if (have[cr] == need[cr]) formed++;
            while (formed == required) {
                final int sIdx = filtered.get(l)[0], eIdx = filtered.get(r)[0];
                if (eIdx - sIdx + 1 < bestLen) { bestLen = eIdx - sIdx + 1; bestL = sIdx; bestR = eIdx; }
                final int cl = filtered.get(l)[1];
                have[cl]--;
                if (have[cl] < need[cl]) formed--;
                l++;
            }
        }
        return bestR == -1 ? "" : s.substring(bestL, bestR + 1);
    }
}

class Solution {
    public int[] maxSlidingWindow(final int[] nums, final int k) {
        final int n = nums.length;
        final int[] out = new int[n - k + 1];
        for (int i = 0; i + k <= n; i++) {
            int m = nums[i];
            for (int j = i + 1; j < i + k; j++) m = Math.max(m, nums[j]);
            out[i] = m;
        }
        return out;
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    /**
     * Monotonic decreasing deque of indices. Each index amortizes O(1):
     * pushed once, popped at most once.
     */
    public int[] maxSlidingWindow(final int[] nums, final int k) {
        final int n = nums.length;
        final int[] out = new int[n - k + 1];
        final Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
            dq.offerLast(i);
            if (i >= k - 1) out[i - k + 1] = nums[dq.peekFirst()];
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(java.util.Arrays.toString(
            new Solution().maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3)));   // [3,3,5,5,6,7]
    }
}

class Solution {
    public int[] maxSlidingWindow(final int[] nums, final int k) {
        final int n = nums.length;
        final int[] left = new int[n];
        final int[] right = new int[n];
        for (int i = 0; i < n; i++) left[i] = (i % k == 0) ? nums[i] : Math.max(left[i-1], nums[i]);
        for (int i = n - 1; i >= 0; i--) right[i] = (i == n - 1 || (i + 1) % k == 0) ? nums[i] : Math.max(right[i+1], nums[i]);
        final int[] out = new int[n - k + 1];
        for (int i = 0; i + k <= n; i++) out[i] = Math.max(right[i], left[i + k - 1]);
        return out;
    }
}

class Solution {
    public boolean isValid(String s) {
        int len = -1;
        while (s.length() != len) {
            len = s.length();
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
        }
        return s.isEmpty();
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public boolean isValid(final String s) {
        final Deque<Character> stack = new ArrayDeque<>(s.length() / 2 + 1);
        for (int i = 0; i < s.length(); i++) {
            final char c = s.charAt(i);
            switch (c) {
                case '(': case '[': case '{': stack.push(c); break;
                case ')': if (stack.isEmpty() || stack.pop() != '(') return false; break;
                case ']': if (stack.isEmpty() || stack.pop() != '[') return false; break;
                case '}': if (stack.isEmpty() || stack.pop() != '{') return false; break;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.isValid("()[]{}"));   // true
        System.out.println(sol.isValid("(]"));       // false
    }
}

import java.util.*;

class Solution {
    private static final Map<Character, Character> MATCH = Map.of(')', '(', ']', '[', '}', '{');

    public boolean isValid(final String s) {
        final Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            final char c = s.charAt(i);
            if (MATCH.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != MATCH.get(c)) return false;
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

import java.util.*;
class MinStack {
    private final Deque<Integer> s = new ArrayDeque<>();
    public void push(int x) { s.push(x); }
    public void pop()       { s.pop(); }
    public int top()        { return s.peek(); }
    public int getMin() {
        int m = Integer.MAX_VALUE;
        for (final int v : s) m = Math.min(m, v);
        return m;
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
    private final Deque<Integer> values = new ArrayDeque<>();
    private final Deque<Integer> mins = new ArrayDeque<>();

    public void push(final int x) {
        values.push(x);
        mins.push(mins.isEmpty() ? x : Math.min(mins.peek(), x));
    }
    public void pop()       { values.pop(); mins.pop(); }
    public int top()        { return values.peek(); }
    public int getMin()     { return mins.peek(); }

    public static void main(String[] args) {
        MinStack m = new MinStack();
        m.push(-2); m.push(0); m.push(-3);
        System.out.println(m.getMin());   // -3
        m.pop();
        System.out.println(m.top());      // 0
        System.out.println(m.getMin());   // -2
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
    private final Deque<Integer> values = new ArrayDeque<>();
    private final Deque<Integer> mins = new ArrayDeque<>();

    public void push(final int x) {
        values.push(x);
        if (mins.isEmpty() || x <= mins.peek()) mins.push(x);
    }
    public void pop() {
        if (values.pop().equals(mins.peek())) mins.pop();
    }
    public int top()    { return values.peek(); }
    public int getMin() { return mins.peek(); }
}

import java.util.*;
class Solution {
    private int idx;
    public int evalRPN(final String[] tokens) {
        idx = tokens.length - 1;
        return parse(tokens);
    }
    private int parse(final String[] tokens) {
        final String t = tokens[idx--];
        switch (t) {
            case "+": { int b = parse(tokens); int a = parse(tokens); return a + b; }
            case "-": { int b = parse(tokens); int a = parse(tokens); return a - b; }
            case "*": { int b = parse(tokens); int a = parse(tokens); return a * b; }
            case "/": { int b = parse(tokens); int a = parse(tokens); return a / b; }
            default: return Integer.parseInt(t);
        }
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int evalRPN(final String[] tokens) {
        final Deque<Integer> stack = new ArrayDeque<>(tokens.length / 2 + 1);
        for (final String t : tokens) {
            switch (t) {
                case "+": { int b = stack.pop(), a = stack.pop(); stack.push(a + b); break; }
                case "-": { int b = stack.pop(), a = stack.pop(); stack.push(a - b); break; }
                case "*": { int b = stack.pop(), a = stack.pop(); stack.push(a * b); break; }
                case "/": { int b = stack.pop(), a = stack.pop(); stack.push(a / b); break; }
                default: stack.push(Integer.parseInt(t));
            }
        }
        return stack.peek();
    }

    public static void main(String[] args) {
        System.out.println(new Solution().evalRPN(new String[]{"2","1","+","3","*"}));   // 9
    }
}

class Solution {
    public int evalRPN(final String[] tokens) {
        final int[] stack = new int[tokens.length / 2 + 1];   // scratch, not input mutation
        int top = -1;
        for (final String t : tokens) {
            switch (t) {
                case "+": { final int b = stack[top--], a = stack[top]; stack[top] = a + b; break; }
                case "-": { final int b = stack[top--], a = stack[top]; stack[top] = a - b; break; }
                case "*": { final int b = stack[top--], a = stack[top]; stack[top] = a * b; break; }
                case "/": { final int b = stack[top--], a = stack[top]; stack[top] = a / b; break; }
                default: stack[++top] = Integer.parseInt(t);
            }
        }
        return stack[0];
    }
}

class Solution {
    public int[] dailyTemperatures(final int[] t) {
        final int n = t.length;
        final int[] out = new int[n];
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (t[j] > t[i]) { out[i] = j - i; break; }
        return out;
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] dailyTemperatures(final int[] t) {
        final int n = t.length;
        final int[] out = new int[n];
        final Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && t[i] > t[stack.peek()]) {
                final int j = stack.pop();
                out[j] = i - j;
            }
            stack.push(i);
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(java.util.Arrays.toString(
            new Solution().dailyTemperatures(new int[]{73,74,75,71,69,72,76,73})));   // [1,1,4,2,1,1,0,0]
    }
}

class Solution {
    public int[] dailyTemperatures(final int[] t) {
        final int n = t.length;
        final int[] out = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int j = i + 1;
            while (j < n && t[j] <= t[i]) {
                if (out[j] == 0) { j = n; break; }
                j += out[j];
            }
            if (j < n) out[i] = j - i;
        }
        return out;
    }
}

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        // Conceptual baseline only — see optimal for the right approach.
        return 0;
    }
}

import java.util.*;

class Solution {
    public int carFleet(final int target, final int[] position, final int[] speed) {
        final int n = position.length;
        final double[][] cars = new double[n][2];
        for (int i = 0; i < n; i++) { cars[i][0] = position[i]; cars[i][1] = speed[i]; }
        // Sort by position descending — closest to target first
        Arrays.sort(cars, (a, b) -> Double.compare(b[0], a[0]));
        int fleets = 0;
        double leadTime = 0.0;
        for (final double[] c : cars) {
            final double arrival = (target - c[0]) / c[1];
            if (arrival > leadTime) {
                leadTime = arrival;
                fleets++;
            }
        }
        return fleets;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().carFleet(12, new int[]{10,8,0,5,3}, new int[]{2,4,1,1,3}));   // 3
    }
}

import java.util.*;

class Solution {
    public int carFleet(final int target, final int[] position, final int[] speed) {
        final int n = position.length;
        final Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> Integer.compare(position[b], position[a]));
        int fleets = 0;
        long leadDist = 0, leadSpeed = 1;     // virtual lead: arrival time = leadDist / leadSpeed
        for (final int i : idx) {
            final long dist = (long)(target - position[i]);
            final long sp = speed[i];
            // car's arrival = dist/sp; lead's arrival = leadDist/leadSpeed
            // car arrives strictly later iff dist * leadSpeed > leadDist * sp
            if (dist * leadSpeed > leadDist * sp) {
                leadDist = dist; leadSpeed = sp;
                fleets++;
            }
        }
        return fleets;
    }
}

class Solution {
    public int largestRectangleArea(final int[] h) {
        int best = 0;
        for (int i = 0; i < h.length; i++) {
            int l = i, r = i;
            while (l > 0 && h[l-1] >= h[i]) l--;
            while (r < h.length - 1 && h[r+1] >= h[i]) r++;
            best = Math.max(best, h[i] * (r - l + 1));
        }
        return best;
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    /**
     * Monotonic increasing stack of indices. The +1 sentinel iteration at
     * i == n flushes the remaining stack with height 0.
     */
    public int largestRectangleArea(final int[] heights) {
        final int n = heights.length;
        final Deque<Integer> stack = new ArrayDeque<>();
        int best = 0;
        for (int i = 0; i <= n; i++) {
            final int h = (i == n) ? 0 : heights[i];
            while (!stack.isEmpty() && heights[stack.peek()] > h) {
                final int idx = stack.pop();
                final int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                best = Math.max(best, heights[idx] * width);
            }
            stack.push(i);
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().largestRectangleArea(new int[]{2,1,5,6,2,3}));   // 10
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int largestRectangleArea(final int[] heights) {
        final int n = heights.length;
        final int[] left = new int[n], right = new int[n];
        final Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) stack.pop();
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) stack.pop();
            right[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        int best = 0;
        for (int i = 0; i < n; i++) best = Math.max(best, heights[i] * (right[i] - left[i] - 1));
        return best;
    }
}

class Solution {
    public int search(final int[] nums, final int target) {
        for (int i = 0; i < nums.length; i++) if (nums[i] == target) return i;
        return -1;
    }
}

class Solution {
    public int search(final int[] nums, final int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            final int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().search(new int[]{-1,0,3,5,9,12}, 9));   // 4
    }
}