function subarraySum(nums, k) {
  const seen = new Map([[0, 1]]);          // the empty prefix, so subarrays starting at index 0 count
  let prefix = 0;
  let count = 0;
  for (const n of nums) {
    prefix += n;
    count += seen.get(prefix - k) ?? 0;
    seen.set(prefix, (seen.get(prefix) ?? 0) + 1);
  }
  return count;
}

subarraySum([1, 1, 1], 2);      // 2
subarraySum([1, -1, 0], 0);     // 3  (negatives and zeros are fine)

static int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> seen = new HashMap<>();
    seen.put(0, 1);                                  // the empty prefix
    int prefix = 0;
    int count = 0;
    for (int n : nums) {
        prefix += n;
        count += seen.getOrDefault(prefix - k, 0);
        seen.merge(prefix, 1, Integer::sum);
    }
    return count;
}
// subarraySum(new int[]{1, 1, 1}, 2)  -> 2
// subarraySum(new int[]{1, -1, 0}, 0) -> 3

static int[] buildPrefix(int[] nums) {
    int[] prefix = new int[nums.length + 1];
    for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
    return prefix;
}

static int rangeSum(int[] prefix, int from, int toInclusive) {
    return prefix[toInclusive + 1] - prefix[from];
}

function dailyTemperatures(temps) {
  const answer = new Array(temps.length).fill(0);
  const stack = [];                                    // indices whose answer is still unknown
  for (let i = 0; i < temps.length; i++) {
    while (stack.length > 0 && temps[i] > temps[stack[stack.length - 1]]) {
      const j = stack.pop();
      answer[j] = i - j;
    }
    stack.push(i);
  }
  return answer;
}

dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]); // [1, 1, 4, 2, 1, 1, 0, 0]

static int[] dailyTemperatures(int[] temps) {
    int[] answer = new int[temps.length];
    Deque<Integer> stack = new ArrayDeque<>();       // indices whose answer is still unknown
    for (int i = 0; i < temps.length; i++) {
        while (!stack.isEmpty() && temps[i] > temps[stack.peek()]) {
            int j = stack.pop();
            answer[j] = i - j;
        }
        stack.push(i);
    }
    return answer;
}
// dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73}) -> [1, 1, 4, 2, 1, 1, 0, 0]

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.components = n;
  }

  find(x) {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];    // path halving
      x = this.parent[x];
    }
    return x;
  }

  union(a, b) {
    let ra = this.find(a);
    let rb = this.find(b);
    if (ra === rb) return false;                       // already connected: this edge closes a cycle
    if (this.rank[ra] < this.rank[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    if (this.rank[ra] === this.rank[rb]) this.rank[ra]++;
    this.components--;
    return true;
  }
}

function findCircleNum(isConnected) {
  const n = isConnected.length;
  const uf = new UnionFind(n);
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i][j] === 1) uf.union(i, j);
    }
  }
  return uf.components;
}

findCircleNum([[1, 1, 0], [1, 1, 0], [0, 0, 1]]); // 2

class UnionFind {
    private final int[] parent;
    private final int[] rank;
    int components;

    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        components = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];           // path halving
            x = parent[x];
        }
        return x;
    }

    boolean union(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) return false;                  // already connected: this edge closes a cycle
        if (rank[ra] < rank[rb]) {
            int tmp = ra;
            ra = rb;
            rb = tmp;
        }
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
        components--;
        return true;
    }
}

static int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    UnionFind uf = new UnionFind(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1) uf.union(i, j);
        }
    }
    return uf.components;
}
// findCircleNum(new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}) -> 2

function rob(nums) {
  let take = 0;                            // best total if we rob the current house
  let skip = 0;                            // best total if we skip the current house
  for (const n of nums) {
    [take, skip] = [skip + n, Math.max(take, skip)];
  }
  return Math.max(take, skip);
}

rob([1, 2, 3, 1]);       // 4
rob([2, 7, 9, 3, 1]);    // 12

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

coinChange([1, 2, 5], 11); // 3
coinChange([2], 3);        // -1

function longestCommonSubsequence(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      dp[i][j] = a[i - 1] === b[j - 1]
        ? dp[i - 1][j - 1] + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[a.length][b.length];
}

longestCommonSubsequence("abcde", "ace"); // 3

static int rob(int[] nums) {
    int take = 0;                                    // best total if we rob the current house
    int skip = 0;                                    // best total if we skip it
    for (int n : nums) {
        int newTake = skip + n;
        skip = Math.max(take, skip);
        take = newTake;
    }
    return Math.max(take, skip);
}
// rob(new int[]{1, 2, 3, 1})    -> 4
// rob(new int[]{2, 7, 9, 3, 1}) -> 12

static int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);                     // "infinity" that cannot overflow
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}
// coinChange(new int[]{1, 2, 5}, 11) -> 3
// coinChange(new int[]{2}, 3)        -> -1

static int longestCommonSubsequence(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++) {
            dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1)
                    ? dp[i - 1][j - 1] + 1
                    : Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[a.length()][b.length()];
}
// longestCommonSubsequence("abcde", "ace") -> 3

class Trie {
  constructor() {
    this.root = { children: new Map(), end: false };
  }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, { children: new Map(), end: false });
      node = node.children.get(ch);
    }
    node.end = true;
  }

  #walk(text) {
    let node = this.root;
    for (const ch of text) {
      node = node.children.get(ch);
      if (!node) return null;
    }
    return node;
  }

  search(word) {
    return this.#walk(word)?.end === true;
  }

  startsWith(prefix) {
    return this.#walk(prefix) !== null;
  }
}

const trie = new Trie();
trie.insert("apple");
trie.search("app");      // false
trie.startsWith("app");  // true

class Trie {
    private static class Node {
        Node[] children = new Node[26];
        boolean end;
    }

    private final Node root = new Node();

    void insert(String word) {
        Node node = root;
        for (char ch : word.toCharArray()) {
            int i = ch - 'a';
            if (node.children[i] == null) node.children[i] = new Node();
            node = node.children[i];
        }
        node.end = true;
    }

    boolean search(String word) {
        Node node = walk(word);
        return node != null && node.end;
    }

    boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }

    private Node walk(String text) {
        Node node = root;
        for (char ch : text.toCharArray()) {
            node = node.children[ch - 'a'];
            if (node == null) return null;
        }
        return node;
    }
}
// Trie trie = new Trie();
// trie.insert("apple");
// trie.search("app")     -> false
// trie.startsWith("app") -> true

function dijkstra(n, edges, source) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) graph[u].push([v, w]);

  const dist = new Array(n).fill(Infinity);
  dist[source] = 0;
  const heap = new Heap((a, b) => a[0] - b[0]);        // [distance, node]
  heap.push([0, source]);
  while (heap.size > 0) {
    const [d, u] = heap.pop();
    if (d > dist[u]) continue;                         // stale entry, a shorter path was already found
    for (const [v, w] of graph[u]) {
      if (d + w < dist[v]) {
        dist[v] = d + w;
        heap.push([dist[v], v]);
      }
    }
  }
  return dist;
}

dijkstra(4, [[0, 1, 1], [0, 2, 4], [1, 2, 2], [2, 3, 1]], 0); // [0, 1, 3, 4]

static int[] dijkstra(int n, int[][] edges, int source) {
    List<List<int[]>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] e : edges) graph.get(e[0]).add(new int[]{e[1], e[2]});

    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));   // {distance, node}
    heap.add(new int[]{0, source});
    while (!heap.isEmpty()) {
        int[] top = heap.poll();
        int d = top[0];
        int u = top[1];
        if (d > dist[u]) continue;                   // stale entry
        for (int[] edge : graph.get(u)) {
            int v = edge[0];
            int w = edge[1];
            if (d + w < dist[v]) {
                dist[v] = d + w;
                heap.add(new int[]{dist[v], v});
            }
        }
    }
    return dist;
}
// dijkstra(4, new int[][]{{0, 1, 1}, {0, 2, 4}, {1, 2, 2}, {2, 3, 1}}, 0) -> [0, 1, 3, 4]

function canJump(nums) {
  let farthest = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > farthest) return false;                    // cannot reach index i
    farthest = Math.max(farthest, i + nums[i]);
  }
  return true;
}

canJump([2, 3, 1, 1, 4]); // true
canJump([3, 2, 1, 0, 4]); // false

static boolean canJump(int[] nums) {
    int farthest = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) return false;
        farthest = Math.max(farthest, i + nums[i]);
    }
    return true;
}
// canJump(new int[]{2, 3, 1, 1, 4}) -> true
// canJump(new int[]{3, 2, 1, 0, 4}) -> false

function singleNumber(nums) {
  return nums.reduce((acc, n) => acc ^ n, 0);          // pairs cancel: a ^ a = 0, a ^ 0 = a
}

const isPowerOfTwo = (n) => n > 0 && (n & (n - 1)) === 0;

function countBits(n) {
  let count = 0;
  while (n !== 0) {
    n &= n - 1;                                        // clears the lowest set bit
    count++;
  }
  return count;
}

singleNumber([4, 1, 2, 1, 2]); // 4
isPowerOfTwo(16);              // true
countBits(11);                 // 3  (1011)

static int singleNumber(int[] nums) {
    int acc = 0;
    for (int n : nums) acc ^= n;                     // pairs cancel
    return acc;
}

static boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

static int countBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;                                  // clears the lowest set bit
        count++;
    }
    return count;
}
// singleNumber(new int[]{4, 1, 2, 1, 2}) -> 4
// isPowerOfTwo(16)                       -> true
// countBits(11)                          -> 3

[10, 9, 1].sort();               // [1, 10, 9]   surprise
[10, 9, 1].sort((a, b) => a - b); // [1, 9, 10]

const bad = new Array(3).fill([]);
bad[0].push(1);                  // [[1], [1], [1]]
const good = Array.from({ length: 3 }, () => []);

const map = new Map();
map.set([1, 2], "a");
map.get([1, 2]);                 // undefined
map.set("1,2", "a");             // use a string key like `${r},${c}` instead

-1 % 3;                          // -1, not 2
((-1 % 3) + 3) % 3;              // 2

// Arrays
int[] a = {5, 3, 1};
Arrays.sort(a);                                      // ascending, in place
int[] copy = Arrays.copyOf(a, a.length);
int[] range = Arrays.copyOfRange(a, 1, 3);
Arrays.fill(a, -1);
String s = Arrays.toString(a);                       // "[-1, -1, -1]"
String deep = Arrays.deepToString(new int[][]{{1}, {2}});

// Sorting objects
Integer[] boxed = {5, 3, 1};
Arrays.sort(boxed, Collections.reverseOrder());
int[][] pairs = {{2, 1}, {1, 9}};
Arrays.sort(pairs, Comparator.comparingInt(p -> p[0]));

// Strings
String text = "hello";
char[] chars = text.toCharArray();
Arrays.sort(chars);
String sorted = new String(chars);                   // "ehllo"
StringBuilder sb = new StringBuilder(text).reverse();

// Streams, for concise conversions
int total = Arrays.stream(a).sum();
int max = Arrays.stream(a).max().getAsInt();
List<Integer> list = Arrays.stream(a).boxed().toList();
int[] back = list.stream().mapToInt(Integer::intValue).toArray();

record Point(int r, int c) {}
// Set<Point> visited = new HashSet<>();
// visited.add(new Point(2, 3));
// visited.contains(new Point(2, 3)) -> true

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        // call your method with the example from the prompt, then with an edge case
        System.out.println(Arrays.toString(twoSumSorted(new int[]{1, 2, 3, 4, 6}, 6)));
        System.out.println(twoSumSorted(new int[]{}, 3).length);
    }

    static int[] twoSumSorted(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            if (sum == target) return new int[]{lo, hi};
            if (sum < target) lo++;
            else hi--;
        }
        return new int[]{-1, -1};
    }
}

javac Solution.java && java Solution

java Solution.java