Step 1: Core Java classes for DSA

• Arrays & Collections:

  Arrays.sort(nums);
  Arrays.fill(arr, val);
  Collections.sort(list);

  Built-ins for sorting arrays/lists and pre-filling arrays with a default value.

  Params: nums = array to sort; arr = target array; val = fill value; list = list sorted in-place.
• String ops:

  s.toCharArray();
  s.charAt(i);
  s.substring(l, r);
  s.split(" ");

  Common string conversions and indexing helpers for char access, slicing, and tokenizing.

  Params: s = source string; i = index; l/r = substring bounds (r exclusive); delimiter = split token.
• HashMap / HashSet:

  map.getOrDefault(k, 0);
  map.put(k, v);
  set.contains(x);
  set.add(x);

  O(1) average-time lookups and inserts for counting, presence checks, and caching.

  Params: k = key; v = value; x = candidate element; defaults applied when key missing.
• Deque / Queue:

  Deque<Integer> dq = new ArrayDeque<>();
  dq.offer(x);
  dq.poll();
  dq.peekFirst();
  dq.peekLast();

  Double-ended queue for BFS, sliding windows, and monotonic queue patterns.

  Params: dq = deque instance; x = element; peekFirst/Last inspect ends; poll removes from head.
• PriorityQueue:

  PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
  pq.offer(item);
  pq.poll();
  pq.peek();

  Min-heap by default; customize comparator for max-heap or tuple ordering.

  Params: pq = heap; a/b = tuple elements compared; item = element pushed (e.g., int[], custom obj).
• TreeMap / TreeSet:

  floorKey(...);
  ceilingKey(...);
  firstEntry();
  lastEntry();

  Ordered maps/sets for range queries, predecessor/successor lookup, and sweeping.

  Params: key inputs to floor/ceiling; entries store key/value pairs when using TreeMap.
• Lists & arrays:

  new ArrayList<>();
  list.toArray(new Integer[0]);
  int[] copy = Arrays.copyOf(arr, n);

  Create dynamic lists, convert to arrays, or clone slices for immutable operations.

  Params: list = ArrayList; arr = source array; n = copy length; result copy is 0-padded if n larger.

Step 2: Templates & patterns

• Two pointers:

  int l = 0, r = nums.length - 1;
  while (l < r) {
    int sum = nums[l] + nums[r];
    ...
  }

  Walk inward from both ends to find pairs/conditions in sorted arrays or strings.

  Params: l/r = indices at ends; sum = example aggregation (two-sum style); condition = your target check.
• Sliding window:

  for (int r = 0; r < n; r++) {
    expand;
    while (condition) shrink;
    update best;
  }

  Grow/shrink a window to maintain constraints (length, counts) in O(n).

  Params: r = expand pointer; condition = validity guard to shrink; best = tracked answer/metric.
• BFS (graph/tree):

  Queue<int[]> q = new ArrayDeque<>();
  q.offer(start);
  while (!q.isEmpty()) {
    int[] cur = q.poll();
    for (int[] nb : neighbors) if (visit) q.offer(nb);
  }

  Layer-by-layer traversal for shortest path on unweighted graphs or tree levels.

  Params: q = queue; start = seed node/state; neighbors = adjacency for cur; visit = seen/valid check.
• DFS recursion:

  void dfs(int u) {
    if (seen[u]) return;
    seen[u] = true;
    for (int v : g.get(u)) dfs(v);
  }

  Depth-first exploration for connected components, backtracking, and tree ops.

  Params: u = current node; seen = visited array/set; g = adjacency list; v = neighbor.
• Binary search:

  int l = 0, r = n - 1;
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (ok(m)) r = m - 1;
    else l = m + 1;
  }

  Find boundaries or feasibility thresholds in O(log n) on sorted/monotone domains.

  Params: l/r = bounds; m = mid index; ok(m) = monotone predicate driving search direction.
• Priority queue (Dijkstra min-heap):

  pq.offer(new int[]{0, src});
  while (!pq.isEmpty()) {
    int[] cur = pq.poll();
    if (dist > best[cur[1]]) continue;
    ...
  }

  Greedy extraction of the next closest/cheapest node for shortest paths or k-selection.

  Params: pq = min-heap; cur = tuple [dist, node]; dist = tentative cost; best = best-known distances array.
• Prefix sums:

  int[] pre = new int[n + 1];
  for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];

  O(1) range sums after O(n) preprocess; useful for subarray queries and diffs.

  Params: pre[i] = sum of nums[0..i-1]; nums = input array; n = length.
• DP array:

  int[] dp = new int[n];
  Arrays.fill(dp, INF);
  dp[0] = base;

  Store optimal subproblem results; initialize with sentinels, set base case, iterate.

  Params: dp = state array; INF = sentinel large value; base = initial state assignment.

Final tips: Speed and debugging

• 🗓️ Practice 3–5 problems weekly across arrays, strings, graphs, and DP.
• 🧪 Add small local tests in main(); print intermediate state when stuck.
• 🔍 Prefer `var` for enhanced for-loops in Java 11+ to shorten syntax, but keep clarity in interviews.
• 📚 Revisit misses: tag problems by pattern and redo after 48 hours to lock in.