{"title":"Java Crash Course for DSA","description":"","content":"This chapter is a focused crash course on the Java features used repeatedly in DSA and coding interview preparation. Instead of covering the entire language, we will concentrate only on the parts that matter for solving problems efficiently in interviews.\n\n---\n\n# Common Imports\n\nOn LeetCode, most imports are available automatically. But when writing Java locally or in some interview platforms, you need to know what to import. Here are the imports that cover 95% of DSA problems:\n\n\n```java\nimport java.util.*; // ArrayList, HashMap, HashSet, Queue, PriorityQueue, etc.\nimport java.util.Arrays; // Arrays.sort(), Arrays.fill(), Arrays.asList()\nimport java.util.Collections; // Collections.sort(), Collections.reverseOrder()\n```\n\n\nThe wildcard `java.util.*` covers almost everything you need. In a real interview, you can write this at the top and move on. Do not waste time importing individual classes.\n\n---\n\n# Variables, Types, and the Overflow Trap\n\nJava is a statically typed language, which means every variable must have a declared type. For DSA, a small set of primitive types covers most problems.\n\n\n| Type | Size | Range | DSA Use Case |\n|------|------|-------|--------------|\n| `int` | 4 bytes | -2.1B to 2.1B | Array indices, counters, most values |\n| `long` | 8 bytes | -9.2 x 10^18 to 9.2 x 10^18 | Prefix sums, large products, overflow-prone math |\n| `char` | 2 bytes | 0 to 65,535 | String characters, frequency arrays |\n| `boolean` | 1 byte (JVM-dependent) | `true` / `false` | Visited arrays, flags |\n| `double` | 8 bytes | ±1.7 x 10^308 | Rarely used, some geometry problems |\n\n\nEach primitive type has a corresponding **wrapper class** (`Integer`, `Long`, `Character`, `Boolean`, `Double`) that lets you use primitives in collections. We will cover this in detail in the autoboxing section.\n\nThe most dangerous pitfall with types is **integer overflow**. Consider the classic binary search:\n\n\n```java\n// BUG: if left + right > Integer.MAX_VALUE, this overflows\nint mid = (left + right) / 2;\n\n// CORRECT: safe from overflow\nint mid = left + (right - left) / 2;\n```\n\n\nThis is not a theoretical concern. When `left` and `right` are both above 1 billion, their sum exceeds `int` range and wraps to a negative number. The safe version avoids this by computing the difference first.\n\nWhen should you use `long` instead of `int`? Use `long` in these cases:\n\n1. **Prefix sums** of arrays with large values (sum of 10^5 elements each up to 10^9 gives 10^14)\n2. **Multiplication** of two large ints (e.g., `n * (n - 1)` where n is near 10^5)\n3. **Factorial or combination** calculations\n4. **Modulo problems** where intermediate sums can exceed int range before taking mod\n\n\n```java\n// Overflow: 100000 * 99999 > Integer.MAX_VALUE\nint wrong = n * (n - 1);\n\n// Safe: cast to long BEFORE multiplication\nlong correct = (long) n * (n - 1);\n\n// WRONG: casting AFTER multiplication is too late, overflow already happened\nlong stillWrong = (long)(n * (n - 1));\n```\n\n\nThe placement of the cast matters. `(long) n * (n - 1)` first promotes `n` to `long`, then performs `long` multiplication. But `(long)(n * (n - 1))` performs `int` multiplication first (which overflows), then casts the already-corrupted result to `long`.\n\n**The ternary operator** is a compact alternative to if-else for inline decisions:\n\n\n```java\nint result = (a > b) ? a : b; // Same as Math.max(a, b)\nString label = (count == 1) ? \"item\" : \"items\";\n```\n\n\n---\n\n# Operators and Control Flow\n\nMost operators in Java work as you would expect, but a few deserve special attention for DSA.\n\n**Modular arithmetic** with `%` appears in hashing, cyclic array problems, and math-heavy questions. Remember that Java's `%` can return negative values for negative operands: `-7 % 3` gives `-1`, not `2`. To get a positive result, use `((n % m) + m) % m`.\n\nMany problems ask you to return the result \"modulo 10^9 + 7\" to prevent overflow in the output. This is a standard pattern:\n\n\n```java\nprivate static final int MOD = 1_000_000_007;\n\n// Apply modulo during computation, not just at the end\nlong result = 0;\nfor (int i = 0; i < n; i++) {\n result = (result + values[i]) % MOD;\n}\nreturn (int) result;\n```\n\n\nNote the underscore in `1_000_000_007`. Java allows underscores in numeric literals for readability. This is the same as writing `1000000007`, easier to read and verify.\n\n**Bitwise operators** unlock an entire category of problems:\n\n\n```java\n// XOR trick: find the number that appears once (all others appear twice)\n// nums = [4, 1, 2, 1, 2]\nint single = 0;\nfor (int num : nums) {\n single ^= num; // XOR cancels out duplicates\n}\n// single = 4\n```\n\n\nKey bitwise operators:\n\n\n| Operator | Symbol | DSA Use |\n|----------|--------|---------|\n| AND | `&` | Masking, checking if bit is set: `(n & (1 << i)) != 0` |\n| OR | `\\|` | Setting bits: `n \\| (1 << i)` |\n| XOR | `^` | Finding unique elements, toggling bits |\n| NOT | `~` | Bit inversion |\n| Left shift | `<<` | Multiply by powers of 2: `1 << n` equals 2^n |\n| Right shift | `>>` | Divide by powers of 2 (preserves sign) |\n| Unsigned right shift | `>>>` | Divide by powers of 2 (fills with 0) |\n\n\nA common bit manipulation pattern is checking and setting individual bits, which shows up in problems using bitmasks to represent subsets:\n\n\n```java\n// Check if bit i is set\nboolean isSet = (mask & (1 << i)) != 0;\n\n// Set bit i\nmask = mask | (1 << i);\n\n// Clear bit i\nmask = mask & ~(1 << i);\n\n// Toggle bit i\nmask = mask ^ (1 << i);\n\n// Count number of set bits\nint count = Integer.bitCount(mask);\n```\n\n\n**Control flow** in Java offers three loop forms. Use each where it fits:\n\n\n```java\n// Index-based for: when you need the index\nfor (int i = 0; i < nums.length; i++) { ... }\n\n// Backward traversal (used in some DP and stack problems)\nfor (int i = n - 1; i >= 0; i--) { ... }\n\n// Enhanced for-each: when you only need values\nfor (int num : nums) { ... }\n\n// While: when the termination condition is not index-based\nwhile (left < right) { ... }\n```\n\n\nOne limitation to remember: the enhanced `for-each` loop does not give you the index, and you cannot modify the underlying collection while iterating. If you need the index or need to modify elements, use the standard `for` loop.\n\n**Short-circuit evaluation** with `&&` and `||` is important for safety. Java evaluates left to right and stops as soon as the result is determined:\n\n\n```java\n// Safe: the second condition is only checked if the first is true\nif (index < nums.length && nums[index] == target) { ... }\n\n// Without short-circuit, this would throw ArrayIndexOutOfBoundsException\n// when index >= nums.length\n```\n\n\n---\n\n# Methods and Pass-by-Value\n\nExtract logic into helper methods when it keeps your code clean. On LeetCode, your solution lives inside a class with `static` or instance methods.\n\n\n```java\n// Helper method for swapping elements in an array\nprivate void swap(int[] arr, int i, int j) {\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n}\n```\n\n\nJava is always **pass-by-value**. But for objects (including arrays), the \"value\" being passed is the reference. This means:\n\n- **Primitive parameters** are copies. Changing them inside a method does not affect the caller.\n- **Object/array parameters** pass a copy of the reference. You can modify the contents (like `arr[i] = 5`), but reassigning the reference itself (`arr = new int[10]`) does not affect the caller.\n\nThis is why the `swap` method above works: it modifies the array contents through the reference. But you cannot write a method that swaps two `int` variables.\n\nThis distinction matters in recursive and backtracking problems. When you pass a `List` to a recursive call and add elements to it, those additions are visible to the caller. That is why the backtracking pattern works, adding and removing from a shared list as you explore different branches:\n\n\n```java\nprivate void backtrack(List path, List> results) {\n if (isComplete(path)) {\n results.add(new ArrayList<>(path)); // MUST copy, not add reference\n return;\n }\n for (int choice : choices) {\n path.add(choice); // Modify shared list\n backtrack(path, results); // Recurse with modified list\n path.remove(path.size() - 1); // Undo modification\n }\n}\n```\n\n\nThe `new ArrayList<>(path)` when saving results creates a copy. If you wrote `results.add(path)` instead, every entry in `results` would be a reference to the same list, and they would all end up empty after backtracking unwinds. This is a common bug in backtracking solutions.\n\n**Variable scope:** Variables declared inside a loop body exist only within that iteration:\n\n\n```java\nfor (int i = 0; i < n; i++) {\n int temp = nums[i]; // temp is created and destroyed each iteration\n}\n// temp does not exist here\n```\n\n\nIf you need a value to persist across iterations (like a running sum or a previous element), declare it before the loop.\n\n---\n\n# Autoboxing and Unboxing\n\nJava collections like `ArrayList`, `HashMap`, and `HashSet` cannot store primitive types directly. They require wrapper objects: `Integer` instead of `int`, `Long` instead of `long`, `Character` instead of `char`, and so on.\n\nJava automatically converts between primitives and their wrappers. This is called **autoboxing** (primitive to wrapper) and **unboxing** (wrapper to primitive):\n\n\n```java\nList list = new ArrayList<>();\nlist.add(42); // Autoboxing: int 42 -> Integer.valueOf(42)\nint val = list.get(0); // Unboxing: Integer -> int\n```\n\n\nThis conversion is convenient, but it has these pitfalls:\n\n**Pitfall 1: **`==`** compares references for wrapper objects, not values.**\n\n\n```java\nInteger a = 200;\nInteger b = 200;\na == b // false! Compares references, not values\na.equals(b) // true\n\nInteger c = 100;\nInteger d = 100;\nc == d // true! Java caches Integer values from -128 to 127\n```\n\n\nJava caches `Integer` objects for values -128 to 127, so `==` happens to work for small numbers. For larger values, it fails. This is a tricky bug because it works in your tests with small inputs and breaks with larger ones. Always use `.equals()` or unbox to `int` before comparing.\n\n**Pitfall 2: Unboxing null throws NullPointerException.**\n\n\n```java\nMap map = new HashMap<>();\nint count = map.get(\"missing\"); // NullPointerException! get() returns null\nint count = map.getOrDefault(\"missing\", 0); // Safe: returns 0\n```\n\n\n**Pitfall 3: Performance in tight loops.**\n\nEach autoboxing operation creates an object on the heap. In a tight inner loop processing millions of elements, this can cause noticeable slowdowns. When performance matters, use primitive arrays (`int[]`) instead of `ArrayList`.\n\n---\n\n# Arrays\n\nArrays are the most fundamental data structure in Java and the starting point for almost every DSA problem.\n\n\n```java\n// Declaration and initialization\nint[] nums = new int[5]; // [0, 0, 0, 0, 0] (defaults to 0)\nint[] nums = {1, 2, 3, 4, 5}; // Literal initialization\nboolean[] visited = new boolean[n]; // defaults to false\nString[] words = new String[n]; // defaults to null\n```\n\n\nDefault values matter and they differ by type:\n\n\n| Array Type | Default Value | DSA Significance |\n|-----------|---------------|------------------|\n| `int[]` | `0` | Distance arrays, DP tables start at 0 |\n| `long[]` | `0L` | Same, for large value computations |\n| `boolean[]` | `false` | Visited arrays start as unvisited |\n| `char[]` | `'\\0'` | Null character |\n| `Object[]` (including `String[]`, `Integer[]`) | `null` | Must initialize before use |\n\n\n**The **`.length`** property** (no parentheses) gives the array size. This is different from `String.length()` (with parentheses) and `List.size()`.\n\n\n```java\nint[] arr = {1, 2, 3};\narr.length // 3 (property, no parentheses)\n\nString s = \"hello\";\ns.length() // 5 (method, with parentheses)\n\nList list = new ArrayList<>();\nlist.size() // 0 (method, with parentheses)\n```\n\n\n**2D arrays** appear in every matrix problem (BFS on grid, dynamic programming tables, etc.):\n\n\n```java\nint[][] matrix = new int[rows][cols];\n\n// Access: matrix[row][col]\n// Row count: matrix.length\n// Column count: matrix[0].length\n```\n\n\nFor DP problems, you often need a table with one extra row and column for the base case:\n\n\n```java\n// DP table with n+1 rows to handle 0-indexed base case\nint[] dp = new int[n + 1];\nint[][] dp = new int[m + 1][n + 1];\n```\n\n\nVisiting the four orthogonal neighbors is a common pattern in matrix problems:\n\n\n```java\nint[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n\nfor (int[] dir : directions) {\n int newRow = row + dir[0];\n int newCol = col + dir[1];\n if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {\n // Process neighbor\n }\n}\n```\n\n\nFor 8-directional movement (including diagonals), add the four diagonal pairs to the `directions` array: `{-1,-1}, {-1,1}, {1,-1}, {1,1}`.\n\n\n```mermaid\nflowchart TD\n subgraph Matrix[\"matrix[3][3]\"]\n direction TB\n R0[\"[0,0] [0,1] [0,2]\"]\n R1[\"[1,0] [1,1] [1,2]\"]\n R2[\"[2,0] [2,1] [2,2]\"]\n end\n\n UP[\"Up
[-1, 0]\"]\n DOWN[\"Down
[+1, 0]\"]\n LEFT[\"Left
[0, -1]\"]\n RIGHT[\"Right
[0, +1]\"]\n\n UP --> R1\n DOWN --> R1\n LEFT --> R1\n RIGHT --> R1\n\n style R0 fill:#00ceff,stroke:#000,color:#000\n style R1 fill:#ffa94d,stroke:#000,color:#000\n style R2 fill:#00ceff,stroke:#000,color:#000\n style UP fill:#69db7c,stroke:#000,color:#000\n style DOWN fill:#69db7c,stroke:#000,color:#000\n style LEFT fill:#69db7c,stroke:#000,color:#000\n style RIGHT fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe `Arrays` utility class provides these operations:\n\n\n```java\nimport java.util.Arrays;\n\nArrays.sort(nums); // Sort in ascending order\nArrays.fill(dist, Integer.MAX_VALUE); // Fill with a value\nint[] copy = Arrays.copyOf(nums, nums.length); // Copy entire array\nint[] partial = Arrays.copyOfRange(nums, 1, 4); // Copy index 1 to 3\nSystem.out.println(Arrays.toString(nums)); // Debug: \"[1, 2, 3]\"\nSystem.out.println(Arrays.deepToString(matrix)); // Debug 2D: \"[[1, 2], [3, 4]]\"\n```\n\n\n`Arrays.asList()` converts elements to a `List`, but has an important gotcha:\n\n\n```java\n// Works: creates a list from individual elements\nList words = Arrays.asList(\"hello\", \"world\");\n\n// Gotcha: returns a FIXED-SIZE list backed by the array\n// You CANNOT add() or remove() from it\nList fixed = Arrays.asList(\"a\", \"b\");\nfixed.add(\"c\"); // throws UnsupportedOperationException!\n\n// Fix: wrap in a new ArrayList for a mutable list\nList mutable = new ArrayList<>(Arrays.asList(\"a\", \"b\"));\nmutable.add(\"c\"); // works fine\n\n// Gotcha: does NOT work with primitive arrays\nint[] nums = {1, 2, 3};\nList wrong = Arrays.asList(nums); // List of size 1 (the array itself),\n // NOT a List of size 3\n// For primitive arrays, use a manual loop to convert\n```\n\n\n`Arrays.binarySearch()` performs binary search on a sorted array:\n\n\n```java\nint[] sorted = {1, 3, 5, 7, 9};\nint index = Arrays.binarySearch(sorted, 5); // Returns 2\nint missing = Arrays.binarySearch(sorted, 4); // Returns -3 (insertion point: -(2+1))\n```\n\n\nThe return value for a missing element is `-(insertion point) - 1`. This is useful but confusing, so writing your own binary search is often clearer in interviews.\n\n---\n\n# Strings\n\nStrings in Java are **immutable**. Every time you modify a string, Java creates a new object. This has a performance implication for DSA:\n\n\n```java\n// BAD: O(n^2) because each += creates a new String\nString result = \"\";\nfor (char c : chars) {\n result += c; // Creates a new string every iteration\n}\n\n// GOOD: O(n) with StringBuilder\nStringBuilder sb = new StringBuilder();\nfor (char c : chars) {\n sb.append(c);\n}\nString result = sb.toString();\n```\n\n\nCommon string methods:\n\n\n| Method | Returns | Example | DSA Use |\n|--------|---------|---------|---------|\n| `charAt(i)` | `char` | `s.charAt(0)` | Access individual characters |\n| `length()` | `int` | `s.length()` | Loop bounds (note: parentheses, unlike arrays) |\n| `substring(start, end)` | `String` | `s.substring(0, 3)` | Extract portions (start inclusive, end exclusive) |\n| `toCharArray()` | `char[]` | `s.toCharArray()` | When you need in-place modification |\n| `split(regex)` | `String[]` | `s.split(\" \")` | Tokenize strings |\n| `indexOf(str)` | `int` | `s.indexOf(\"ab\")` | Find substrings (-1 if not found) |\n| `equals(other)` | `boolean` | `s.equals(t)` | Content comparison |\n| `compareTo(other)` | `int` | `s.compareTo(t)` | Lexicographic comparison |\n| `trim()` | `String` | `s.trim()` | Remove leading/trailing whitespace |\n| `isEmpty()` | `boolean` | `s.isEmpty()` | Check if length is 0 |\n| `startsWith(prefix)` | `boolean` | `s.startsWith(\"ab\")` | Prefix check |\n| `contains(seq)` | `boolean` | `s.contains(\"ab\")` | Substring check |\n\n\nThe `equals()` vs `==` distinction is a common Java bug:\n\n\n```java\nString a = new String(\"hello\");\nString b = new String(\"hello\");\n\na == b // false (compares references, different objects)\na.equals(b) // true (compares content)\n```\n\n\n**Always use **`.equals()`** for string comparison.** The `==` operator compares memory addresses, not content. It sometimes works with string literals due to Java's string pool, but this behavior is unreliable and will create subtle bugs.\n\n**StringBuilder** is your tool for building strings efficiently:\n\n\n```java\nStringBuilder sb = new StringBuilder();\nsb.append(\"hello\"); // Add to end\nsb.append(' '); // Append char\nsb.insert(0, \"say \"); // Insert at position\nsb.reverse(); // Reverse in place\nsb.deleteCharAt(0); // Remove character\nsb.setCharAt(2, 'x'); // Replace character at index\nsb.length(); // Current length\nString result = sb.toString(); // Convert back to String\n```\n\n\nYou can also initialize `StringBuilder` with a capacity hint when you know the approximate size. This avoids internal buffer resizing:\n\n\n```java\nStringBuilder sb = new StringBuilder(word1.length() + word2.length());\n```\n\n\n**Character utilities** come up in problems involving letter manipulation:\n\n\n```java\nCharacter.isLetterOrDigit(c) // Alphanumeric check (valid palindrome)\nCharacter.isLetter(c) // Letter only\nCharacter.isDigit(c) // Digit only\nCharacter.isUpperCase(c) // Uppercase check\nCharacter.toLowerCase(c) // Case conversion\nCharacter.toUpperCase(c) // Case conversion\nc - 'a' // Map 'a'-'z' to 0-25 (frequency arrays)\nc - '0' // Map '0'-'9' to 0-9 (digit extraction)\n(char) ('a' + index) // Map 0-25 back to 'a'-'z'\n```\n\n\nThe `c - 'a'` pattern works because characters are stored as numbers. Subtracting `'a'` from a lowercase letter gives its zero-based position. This is how you build frequency arrays without a `HashMap`:\n\n\n```java\n// Frequency array for lowercase letters (26 slots)\nint[] freq = new int[26];\nfor (char c : s.toCharArray()) {\n freq[c - 'a']++;\n}\n// freq[0] = count of 'a', freq[1] = count of 'b', etc.\n```\n\n\nThis is faster and more memory-efficient than `HashMap` when you know the character set is limited to lowercase (or uppercase, or digits).\n\n---\n\n# Collections Framework\n\nThe Java Collections Framework provides the data structures used in nearly every DSA problem. Choosing the right collection is often the difference between an O(n) and an O(n^2) solution.\n\n\n```mermaid\nflowchart TD\n IT[\"Iterable\"]\n COL[\"Collection\"]\n LIST[\"List\"]\n SET[\"Set\"]\n QUEUE[\"Queue\"]\n DEQUE[\"Deque\"]\n MAP[\"Map
(separate hierarchy)\"]\n\n AL[\"ArrayList\"]\n LL[\"LinkedList\"]\n HS[\"HashSet\"]\n LHS[\"LinkedHashSet\"]\n TS[\"TreeSet\"]\n PQ[\"PriorityQueue\"]\n AD[\"ArrayDeque\"]\n HM[\"HashMap\"]\n LHM[\"LinkedHashMap\"]\n TM[\"TreeMap\"]\n STK[\"Stack
(avoid)\"]\n\n IT --> COL\n COL --> LIST\n COL --> SET\n COL --> QUEUE\n QUEUE --> DEQUE\n LIST --> AL\n LIST --> LL\n LIST --> STK\n SET --> HS\n SET --> LHS\n SET --> TS\n QUEUE --> PQ\n DEQUE --> AD\n DEQUE --> LL\n MAP --> HM\n MAP --> LHM\n MAP --> TM\n\n style IT fill:#00ceff,stroke:#000,color:#000\n style COL fill:#00ceff,stroke:#000,color:#000\n style LIST fill:#00ceff,stroke:#000,color:#000\n style SET fill:#00ceff,stroke:#000,color:#000\n style QUEUE fill:#00ceff,stroke:#000,color:#000\n style DEQUE fill:#00ceff,stroke:#000,color:#000\n style MAP fill:#00ceff,stroke:#000,color:#000\n style AL fill:#38d9a9,stroke:#000,color:#000\n style LL fill:#38d9a9,stroke:#000,color:#000\n style HS fill:#38d9a9,stroke:#000,color:#000\n style LHS fill:#38d9a9,stroke:#000,color:#000\n style TS fill:#38d9a9,stroke:#000,color:#000\n style PQ fill:#38d9a9,stroke:#000,color:#000\n style AD fill:#38d9a9,stroke:#000,color:#000\n style HM fill:#38d9a9,stroke:#000,color:#000\n style LHM fill:#38d9a9,stroke:#000,color:#000\n style TM fill:#38d9a9,stroke:#000,color:#000\n style STK fill:#ff8787,stroke:#000,color:#000\n```\n\n\n### ArrayList: Dynamic Arrays\n\nWhen you do not know the size upfront, or need to build a result list, use `ArrayList`:\n\n\n```java\nList result = new ArrayList<>();\nresult.add(42); // Append: O(1) amortized\nresult.get(0); // Access by index: O(1)\nresult.set(0, 99); // Update by index: O(1)\nresult.size(); // Current size\nresult.isEmpty(); // Check if empty\nresult.contains(42); // Search: O(n)\nresult.remove(0); // Remove by index: O(n) (shifts elements)\nresult.remove(Integer.valueOf(42)); // Remove by value: O(n)\n```\n\n\nThe two `remove` overloads behave differently. `remove(0)` removes the element at index 0. `remove(Integer.valueOf(42))` removes the first occurrence of the value 42. If you write `remove(42)` on a `List`, Java treats 42 as an index, not a value. This is a common source of bugs.\n\nA common pattern is building a list of lists for results like permutations or combinations:\n\n\n```java\nList> results = new ArrayList<>();\nresults.add(new ArrayList<>(currentPath)); // Add a COPY of current state\n```\n\n\n**Collections utility methods** that work on lists:\n\n\n```java\nCollections.reverse(list); // Reverse in place\nCollections.sort(list); // Sort ascending\nCollections.sort(list, Collections.reverseOrder()); // Sort descending\nCollections.swap(list, i, j); // Swap two elements\nCollections.min(list); // Find minimum\nCollections.max(list); // Find maximum\nCollections.frequency(list, element); // Count occurrences\n```\n\n\n### HashMap and HashSet: O(1) Lookups\n\n`HashMap` appears in most DSA problems. It provides O(1) average-case lookups, inserts, and deletes.\n\n\n```java\n// Frequency counting: the most common HashMap pattern\nMap freq = new HashMap<>();\nfor (char c : s.toCharArray()) {\n freq.put(c, freq.getOrDefault(c, 0) + 1);\n}\n\n// Check existence and retrieve\nif (freq.containsKey('a')) {\n int count = freq.get('a');\n}\n\n// Safe retrieval (avoids NullPointerException)\nint count = freq.getOrDefault('z', 0);\n\n// Iterate over all entries\nfor (Map.Entry entry : freq.entrySet()) {\n char key = entry.getKey();\n int value = entry.getValue();\n}\n\n// Iterate over keys only\nfor (Character key : freq.keySet()) { ... }\n\n// Iterate over values only\nfor (Integer value : freq.values()) { ... }\n\n// Remove a key\nfreq.remove('a');\n\n// Get size\nfreq.size();\n```\n\n\n**A null safety point:** `map.get(key)` returns `null` if the key does not exist. If you auto-unbox this to `int`, you get a `NullPointerException`:\n\n\n```java\nMap map = new HashMap<>();\nint val = map.get(\"missing\"); // NullPointerException!\nint val = map.getOrDefault(\"missing\", 0); // Safe: returns 0\n```\n\n\n`HashSet` provides O(1) membership testing:\n\n\n```java\nSet visited = new HashSet<>();\nvisited.add(node); // Returns true if newly added, false if already present\nvisited.contains(node); // O(1) lookup\nvisited.remove(node); // O(1) removal\nvisited.size(); // Number of elements\n```\n\n\n`add()` returns a boolean telling you whether the element was newly added (i.e., was not already present). This lets you detect duplicates in a single operation:\n\n\n```java\nSet seen = new HashSet<>();\nfor (int num : nums) {\n if (!seen.add(num)) {\n // num is a duplicate\n }\n}\n```\n\n\n### LinkedHashMap and LinkedHashSet: Insertion Order\n\n`LinkedHashMap` maintains insertion order, which is important for specific problems like LRU Cache:\n\n\n```java\n// Access-ordered LinkedHashMap (foundation for an LRU cache)\n// The 'true' parameter enables access-order: most recently accessed moves to end\nLinkedHashMap cache = new LinkedHashMap<>(16, 0.75f, true) {\n @Override\n protected boolean removeEldestEntry(Map.Entry eldest) {\n return size() > CAPACITY; // automatic eviction once size exceeds CAPACITY\n }\n};\n```\n\n\n`LinkedHashSet` similarly maintains insertion order for sets. Use these when the order in which elements were inserted matters.\n\n### TreeMap and TreeSet: Sorted Collections\n\nWhen you need keys in sorted order, `TreeMap` and `TreeSet` provide O(log n) operations backed by a red-black tree:\n\n\n```java\nTreeMap map = new TreeMap<>();\nmap.put(5, 10);\nmap.put(1, 20);\nmap.put(10, 30);\n\nmap.firstKey(); // 1 (smallest key)\nmap.lastKey(); // 10 (largest key)\nmap.floorKey(7); // 5 (largest key <= 7)\nmap.ceilingKey(7); // 10 (smallest key >= 7)\nmap.lowerKey(5); // 1 (largest key strictly < 5)\nmap.higherKey(5); // 10 (smallest key strictly > 5)\nmap.headMap(5); // All entries with key < 5\nmap.tailMap(5); // All entries with key >= 5\nmap.subMap(1, 10); // All entries with 1 <= key < 10\n```\n\n\n`TreeSet` offers the same navigational methods (`floor`, `ceiling`, `lower`, `higher`, `first`, `last`) for elements instead of keys.\n\nThese are useful for sliding window problems where you need sorted access to window elements, or for interval-based problems where you need to find the closest interval.\n\n### Queue with LinkedList: BFS Foundation\n\nEvery BFS implementation starts with a queue:\n\n\n```java\nQueue queue = new LinkedList<>();\nqueue.offer(new int[]{startRow, startCol}); // Enqueue\nwhile (!queue.isEmpty()) {\n int size = queue.size(); // Capture size for level-order traversal\n for (int i = 0; i < size; i++) {\n int[] cell = queue.poll(); // Dequeue\n // Process cell, add neighbors\n queue.offer(new int[]{newRow, newCol});\n }\n}\n```\n\n\nUse `offer()` and `poll()` instead of `add()` and `remove()`. The former return special values on failure (`false` / `null`), while the latter throw exceptions. In DSA, you almost always want the non-throwing versions.\n\nThe `queue.size()` capture before the inner loop is a common pattern for level-order BFS, where you need to process all nodes at the current level before moving to the next.\n\n### Deque and ArrayDeque: The Better Stack\n\nNever use `Stack` in Java. It extends `Vector`, which is synchronized (slow) and a legacy class. Use `ArrayDeque` instead:\n\n\n```java\n// As a stack (LIFO)\nDeque stack = new ArrayDeque<>();\nstack.push(42); // Push to top\nstack.pop(); // Remove and return top (throws if empty)\nstack.peek(); // View top without removing (returns null if empty)\nstack.isEmpty(); // Check before pop to avoid exception\n\n// As a double-ended queue (sliding window maximum, monotonic deque)\nDeque deque = new ArrayDeque<>();\ndeque.offerFirst(val); // Add to front\ndeque.offerLast(val); // Add to back\ndeque.pollFirst(); // Remove from front (returns null if empty)\ndeque.pollLast(); // Remove from back (returns null if empty)\ndeque.peekFirst(); // View front\ndeque.peekLast(); // View back\n```\n\n\n### PriorityQueue: Heaps\n\n`PriorityQueue` gives you a min-heap by default. It is used for problems involving top-K elements, merge-K-sorted, and Dijkstra's algorithm:\n\n\n```java\n// Min-heap (default): smallest element comes out first\nPriorityQueue minHeap = new PriorityQueue<>();\n\n// Max-heap: largest element comes out first\nPriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());\n\n// Custom comparator: sort by first element of array\nPriorityQueue pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));\n\npq.offer(element); // Insert: O(log n)\npq.poll(); // Remove min/max: O(log n)\npq.peek(); // View min/max: O(1)\npq.size(); // Current size\npq.isEmpty(); // Check if empty\n```\n\n\nOne important limitation: `PriorityQueue` does **not** support efficient removal of arbitrary elements. `pq.remove(element)` is O(n) because it has to search the heap linearly. If you need to remove arbitrary elements from a heap, consider using a `TreeMap` instead, or use lazy deletion (mark elements as deleted and skip them when they surface via `poll()`).\n\n### Collections Quick Reference\n\n\n| Collection | Interface | Key Methods | Time Complexity | DSA Use Case |\n|------------|-----------|-------------|-----------------|--------------|\n| `ArrayList` | `List` | `add`, `get`, `set`, `size` | O(1) get, O(1) add | Result lists, dynamic arrays |\n| `HashMap` | `Map` | `put`, `get`, `containsKey`, `getOrDefault` | O(1) average | Frequency counting, lookups |\n| `HashSet` | `Set` | `add`, `contains`, `remove` | O(1) average | Visited tracking, duplicates |\n| `LinkedHashMap` | `Map` | Same as HashMap + insertion order | O(1) average | LRU cache, ordered maps |\n| `LinkedHashSet` | `Set` | Same as HashSet + insertion order | O(1) average | Ordered unique elements |\n| `TreeMap` | `Map` | `put`, `floorKey`, `ceilingKey`, `firstKey` | O(log n) | Sorted access, range queries |\n| `TreeSet` | `Set` | `add`, `floor`, `ceiling`, `first` | O(log n) | Sorted unique elements |\n| `LinkedList` | `Queue` | `offer`, `poll`, `peek` | O(1) | BFS queues |\n| `ArrayDeque` | `Deque` | `push`, `pop`, `offerLast`, `pollFirst` | O(1) | Stacks, double-ended queues |\n| `PriorityQueue` | `Queue` | `offer`, `poll`, `peek` | O(log n) insert/remove | Heaps, top-K, Dijkstra |\n\n\n---\n\n# Sorting and Comparators\n\nSorting is a prerequisite for many algorithms: binary search, two pointers on sorted arrays, merge intervals, and greedy approaches.\n\n\n```java\n// Sort primitive array\nint[] nums = {3, 1, 4, 1, 5};\nArrays.sort(nums); // [1, 1, 3, 4, 5]\n\n// Sort a portion of an array (index 1 to 3, exclusive)\nArrays.sort(nums, 1, 4);\n\n// Sort a list\nList list = new ArrayList<>(Arrays.asList(3, 1, 4));\nCollections.sort(list);\n// Or equivalently:\nlist.sort(Comparator.naturalOrder());\n```\n\n\nFor custom sorting, Java uses `Comparator` with lambda expressions. The comparator receives two elements and returns a negative number if the first should come before the second, zero if they are equal, and a positive number if the first should come after.\n\n\n```java\n// Sort intervals by start time (merge intervals pattern)\nint[][] intervals = {{1,3}, {2,6}, {8,10}};\nArrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));\n\n// Sort strings by length, then alphabetically for ties\nArrays.sort(words, (a, b) -> {\n if (a.length() != b.length()) return Integer.compare(a.length(), b.length());\n return a.compareTo(b);\n});\n\n// Equivalent using Comparator chaining (cleaner for multi-key sorts)\nArrays.sort(words, Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));\n```\n\n\nThe subtraction form `(a, b) -> a[0] - b[0]` is common, but it can overflow when values are near `Integer.MAX_VALUE` or `Integer.MIN_VALUE`. For example, `Integer.MIN_VALUE - 1` wraps to `Integer.MAX_VALUE`, giving the wrong comparison result. Always use `Integer.compare(a, b)` for safe comparisons.\n\nFor descending order:\n\n\n```java\n// Sort Integer array in descending order\nInteger[] nums = {3, 1, 4};\nArrays.sort(nums, Collections.reverseOrder());\n\n// Sort list in descending order\nlist.sort(Collections.reverseOrder());\n\n// Note: Collections.reverseOrder() does not work with primitive arrays.\n// For primitive int[], sort ascending then reverse manually,\n// or use Integer[] instead.\n```\n\n\n---\n\n# Functional Patterns for DSA\n\nJava 8 introduced several methods on collections that make DSA code more concise. You do not need to master functional programming, but these patterns appear constantly:\n\n\n```java\n// 1. getOrDefault: safe frequency counting\nmap.getOrDefault(key, 0); // Returns 0 if key not found\n\n// 2. computeIfAbsent: build adjacency lists cleanly\nMap> graph = new HashMap<>();\ngraph.computeIfAbsent(node, k -> new ArrayList<>()).add(neighbor);\n\n// 3. merge: concise frequency counting\nmap.merge(key, 1, Integer::sum); // Increment count by 1\n\n// 4. putIfAbsent: set a value only if key is not already present\nmap.putIfAbsent(key, defaultValue);\n\n// 5. entrySet: iterate over key-value pairs\nfor (Map.Entry entry : map.entrySet()) {\n String key = entry.getKey();\n int value = entry.getValue();\n}\n```\n\n\nThe `computeIfAbsent` pattern is useful for building graph adjacency lists. Without it, you would need to check if the key exists, create the list if it does not, and then add the neighbor. With it, all of that happens in one line:\n\n\n```java\n// Without computeIfAbsent (verbose)\nif (!graph.containsKey(node)) {\n graph.put(node, new ArrayList<>());\n}\ngraph.get(node).add(neighbor);\n\n// With computeIfAbsent (clean)\ngraph.computeIfAbsent(node, k -> new ArrayList<>()).add(neighbor);\n```\n\n\n---\n\n# Null Handling\n\n`null` is a source of many runtime errors in Java. In DSA, it appears primarily in three situations: tree/linked list problems, map lookups, and uninitialized object arrays.\n\n**Rule 1: Always check for null before accessing fields or calling methods on an object.**\n\n\n```java\n// Tree traversal: always check for null children\nif (node.left != null) {\n queue.offer(node.left);\n}\n\n// Linked list: check before advancing\nwhile (current != null) {\n // process current\n current = current.next;\n}\n```\n\n\n**Rule 2: Use **`getOrDefault`** instead of **`get`** for maps.**\n\n\n```java\n// Dangerous: returns null if key missing, unboxing null throws NPE\nint count = map.get(\"key\");\n\n// Safe: returns default value\nint count = map.getOrDefault(\"key\", 0);\n```\n\n\n**Rule 3: Combine null and empty checks.**\n\n\n```java\nif (nums == null || nums.length == 0) return new int[0];\nif (s == null || s.isEmpty()) return \"\";\n```\n\n\nThese checks at the top of your solution handle edge cases cleanly and prevent null pointer exceptions on empty or missing inputs.\n\n---\n\n# Iterating and Modifying Collections Safely\n\nOne of Java's most common runtime errors is `ConcurrentModificationException`, thrown when you modify a collection while iterating over it with a for-each loop:\n\n\n```java\n// WRONG: throws ConcurrentModificationException\nList list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));\nfor (int num : list) {\n if (num % 2 == 0) {\n list.remove(Integer.valueOf(num));\n }\n}\n```\n\n\nThere are three safe alternatives:\n\n\n```java\n// Option 1: Use an Iterator with iterator.remove()\nIterator it = list.iterator();\nwhile (it.hasNext()) {\n if (it.next() % 2 == 0) {\n it.remove(); // Safe removal during iteration\n }\n}\n\n// Option 2: Collect items to remove, then remove after the loop\nList toRemove = new ArrayList<>();\nfor (int num : list) {\n if (num % 2 == 0) toRemove.add(num);\n}\nlist.removeAll(toRemove);\n\n// Option 3: Iterate backward with index-based loop (for ArrayList)\nfor (int i = list.size() - 1; i >= 0; i--) {\n if (list.get(i) % 2 == 0) {\n list.remove(i);\n }\n}\n```\n\n\nFor `HashSet` and `HashMap`, the same rules apply. If you need to remove entries while iterating, use the iterator's `remove()` method. In practice though, most DSA problems do not require removing during iteration. You are far more likely to build a new collection with the desired elements.\n\n---\n\n# Recursion and the Call Stack\n\nRecursion is the backbone of tree traversal, graph DFS, backtracking, and divide-and-conquer. Understanding how Java handles recursion matters for avoiding stack overflows and writing correct code.\n\nEvery method call in Java goes on the **call stack**, which has limited space (typically a few thousand frames, depending on stack size and frame size). If your recursion goes too deep, you get a `StackOverflowError`:\n\n\n```java\n// This will crash for large n (the exact limit depends on JVM stack\n// size and frame size, usually somewhere between 5,000 and 50,000)\nint factorial(int n) {\n if (n <= 1) return 1;\n return n * factorial(n - 1);\n}\n```\n\n\n**When to worry about stack depth:**\n\n\n| Scenario | Typical Depth | Risk |\n|----------|--------------|------|\n| Balanced binary tree (n nodes) | O(log n) | Safe for n up to 10^6 |\n| Linked list / skewed tree (n nodes) | O(n) | Dangerous if n > 5,000-10,000 |\n| Backtracking (k choices, depth d) | O(d) | Usually safe (d is small) |\n| DFS on graph (n nodes) | O(n) | Dangerous for large n |\n\n\n**The fix:** Convert deep recursion to an iterative approach using an explicit stack:\n\n\n```java\n// Recursive DFS (risks stack overflow for deep graphs)\n// Assumes `graph` is an adjacency list available as a field\nvoid dfs(int node, boolean[] visited) {\n visited[node] = true;\n for (int neighbor : graph.get(node)) {\n if (!visited[neighbor]) dfs(neighbor, visited);\n }\n}\n\n// Iterative DFS (safe for any depth)\nvoid dfs(int start, boolean[] visited) {\n Deque stack = new ArrayDeque<>();\n stack.push(start);\n while (!stack.isEmpty()) {\n int node = stack.pop();\n if (visited[node]) continue;\n visited[node] = true;\n for (int neighbor : graph.get(node)) {\n if (!visited[neighbor]) stack.push(neighbor);\n }\n }\n}\n```\n\n\nNote that Java does **not** optimize tail recursion. Unlike some functional languages, a tail-recursive method in Java still adds a frame to the call stack on every call. If your recursion depth is proportional to input size and the input can be large, convert to iteration.\n\n---\n\n# Graph Representation Patterns\n\nGraphs appear in a large portion of DSA problems. Java does not have a built-in graph class, so build representations manually. There are two common approaches:\n\n**Approach 1: Adjacency list with **`List>`**.** Use this when nodes are numbered 0 to n-1.\n\n\n```java\nint n = 5; // number of nodes\nList> graph = new ArrayList<>();\nfor (int i = 0; i < n; i++) {\n graph.add(new ArrayList<>());\n}\n\n// Add edges\nfor (int[] edge : edges) {\n graph.get(edge[0]).add(edge[1]);\n graph.get(edge[1]).add(edge[0]); // Omit for directed graphs\n}\n\n// Access neighbors\nfor (int neighbor : graph.get(node)) { ... }\n```\n\n\n**Approach 2: Adjacency list with **`HashMap>`**.** Use this when node IDs are not contiguous or are very large.\n\n\n```java\nMap> graph = new HashMap<>();\nfor (int[] edge : edges) {\n graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);\n graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);\n}\n\n// Access neighbors (with safety check)\nfor (int neighbor : graph.getOrDefault(node, Collections.emptyList())) { ... }\n```\n\n\n**Weighted graphs** use `int[]` pairs or a simple class to store neighbor and weight:\n\n\n```java\n// Adjacency list for weighted graph: List of [neighbor, weight] pairs\nList> graph = new ArrayList<>();\nfor (int i = 0; i < n; i++) graph.add(new ArrayList<>());\n\ngraph.get(from).add(new int[]{to, weight});\n\n// Used in Dijkstra:\nPriorityQueue pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));\npq.offer(new int[]{startNode, 0}); // [node, distance]\n```\n\n\n\n```mermaid\nflowchart LR\n subgraph AdjList[\"Adjacency List (List of Lists)\"]\n N0[\"Node 0\"] --> L0[\"[1, 2]\"]\n N1[\"Node 1\"] --> L1[\"[0, 3]\"]\n N2[\"Node 2\"] --> L2[\"[0, 3]\"]\n N3[\"Node 3\"] --> L3[\"[1, 2]\"]\n end\n\n subgraph AdjMap[\"Adjacency Map (HashMap)\"]\n K0[\"Key: 0\"] --> V0[\"[1, 2]\"]\n K1[\"Key: 1\"] --> V1[\"[0, 3]\"]\n K2[\"Key: 2\"] --> V2[\"[0, 3]\"]\n K3[\"Key: 3\"] --> V3[\"[1, 2]\"]\n end\n\n style N0 fill:#00ceff,stroke:#000,color:#000\n style N1 fill:#00ceff,stroke:#000,color:#000\n style N2 fill:#00ceff,stroke:#000,color:#000\n style N3 fill:#00ceff,stroke:#000,color:#000\n style L0 fill:#38d9a9,stroke:#000,color:#000\n style L1 fill:#38d9a9,stroke:#000,color:#000\n style L2 fill:#38d9a9,stroke:#000,color:#000\n style L3 fill:#38d9a9,stroke:#000,color:#000\n style K0 fill:#ffa94d,stroke:#000,color:#000\n style K1 fill:#ffa94d,stroke:#000,color:#000\n style K2 fill:#ffa94d,stroke:#000,color:#000\n style K3 fill:#ffa94d,stroke:#000,color:#000\n style V0 fill:#69db7c,stroke:#000,color:#000\n style V1 fill:#69db7c,stroke:#000,color:#000\n style V2 fill:#69db7c,stroke:#000,color:#000\n style V3 fill:#69db7c,stroke:#000,color:#000\n```\n\n\n\n| Approach | Pros | Cons | Use When |\n|----------|------|------|----------|\n| `List>` | Fast index access, no hashing overhead | Wastes space if node IDs are sparse | Nodes are 0 to n-1 |\n| `HashMap>` | Handles any node IDs, no wasted space | Slightly slower due to hashing | Node IDs are large, sparse, or non-numeric |\n\n\n---\n\n# Pair and Tuple Alternatives\n\nJava has no built-in `Pair` or `Tuple` class. When you need to store two or three values together, here are the common alternatives:\n\n**Option 1: **`int[]`** array (most common in DSA)**\n\n\n```java\n// Store [row, col] pair\nint[] cell = new int[]{row, col};\nqueue.offer(new int[]{row, col, distance}); // Can store 3+ values\n\n// Access\nint r = cell[0];\nint c = cell[1];\n```\n\n\nThis is the most common approach because it is fast and concise. The downside is that it is not type-safe and the meaning of each index is implicit.\n\n**Option 2: Custom class (when clarity matters)**\n\n\n```java\nclass Pair {\n int key;\n int value;\n Pair(int key, int value) {\n this.key = key;\n this.value = value;\n }\n}\n```\n\n\n**Option 3: **`Map.Entry`** (quick and dirty)**\n\n\n```java\nMap.Entry pair = Map.entry(1, 2); // Java 9+\n// Or for older versions:\nMap.Entry pair = new AbstractMap.SimpleEntry<>(1, 2);\npair.getKey(); // 1\npair.getValue(); // 2\n```\n\n\nIn practice, `int[]` is the standard approach in competitive programming and interviews. Use it unless the code becomes unclear.\n\n---\n\n# Deduplication Patterns\n\nMany DSA problems require avoiding duplicate results (e.g., 3Sum, 4Sum, permutations with duplicates). Java offers two approaches:\n\n**Approach 1: Sort and skip duplicates (preferred for sorted array problems)**\n\n\n```java\nArrays.sort(nums);\nfor (int i = 0; i < nums.length; i++) {\n // Skip duplicates: if this value is the same as the previous, skip it\n if (i > 0 && nums[i] == nums[i - 1]) continue;\n // Process nums[i]\n}\n```\n\n\nThis is the standard approach for problems like 3Sum and 4Sum. It runs in O(1) extra space (beyond the sort) and produces results in sorted order.\n\n**Approach 2: Use a Set to collect unique results**\n\n\n```java\nSet> resultSet = new HashSet<>();\n// ... generate candidates ...\nresultSet.add(Arrays.asList(a, b, c)); // Duplicates are automatically ignored\nreturn new ArrayList<>(resultSet);\n```\n\n\nThis is simpler to implement but uses more memory. Note that for `HashSet` to detect duplicate lists, the lists must contain the same elements in the same order. So you typically sort each candidate before adding it.\n\n---\n\n# Common DSA Idioms in Java\n\nCommon small patterns and utility calls:\n\n**Swapping elements** (Java has no built-in swap for arrays):\n\n\n```java\nint temp = arr[i];\narr[i] = arr[j];\narr[j] = temp;\n```\n\n\n**Sentinel values** for tracking min/max:\n\n\n```java\nint minVal = Integer.MAX_VALUE; // 2,147,483,647\nint maxVal = Integer.MIN_VALUE; // -2,147,483,648\nfor (int num : nums) {\n minVal = Math.min(minVal, num);\n maxVal = Math.max(maxVal, num);\n}\n```\n\n\nBe careful with `Integer.MIN_VALUE`. Negating it (`-Integer.MIN_VALUE`) overflows because the positive range is one less than the negative range. If you need to negate values that might be `Integer.MIN_VALUE`, use `long`.\n\n**Math utilities:**\n\n\n```java\nMath.max(a, b); // Larger of two values\nMath.min(a, b); // Smaller of two values\nMath.abs(a); // Absolute value (careful with MIN_VALUE)\n(int) Math.pow(2, 10); // Power (returns double, cast to int)\nMath.sqrt(n); // Square root (returns double)\nMath.log(n); // Natural logarithm\nMath.ceil(a / (double) b); // Ceiling division (cast to double first!)\n```\n\n\n**Ceiling division** without floating point:\n\n\n```java\n// Integer ceiling division: ceil(a / b) for positive a, b\nint ceil = (a + b - 1) / b;\n// Or equivalently:\nint ceil = (a - 1) / b + 1;\n```\n\n\n**Type conversions** come up when converting between arrays and collections, or between strings and numbers:\n\n\n```mermaid\nflowchart LR\n IA[\"int[]\"]\n LI[\"List<Integer>\"]\n STR[\"String\"]\n CA[\"char[]\"]\n INT[\"int\"]\n\n IA -->|\"manual loop\"| LI\n LI -->|\"manual loop\"| IA\n STR -->|\"toCharArray()\"| CA\n CA -->|\"new String(arr)\"| STR\n STR -->|\"Integer.parseInt()\"| INT\n INT -->|\"String.valueOf()\"| STR\n\n style IA fill:#00ceff,stroke:#000,color:#000\n style LI fill:#00ceff,stroke:#000,color:#000\n style STR fill:#ffa94d,stroke:#000,color:#000\n style CA fill:#ffa94d,stroke:#000,color:#000\n style INT fill:#69db7c,stroke:#000,color:#000\n```\n\n\n\n```java\n// int[] to List (no one-liner for primitives)\nList list = new ArrayList<>();\nfor (int num : nums) list.add(num);\n\n// List to int[]\nint[] arr = new int[list.size()];\nfor (int i = 0; i < list.size(); i++) arr[i] = list.get(i);\n\n// String <-> char[]\nchar[] chars = str.toCharArray();\nString str = new String(chars);\n\n// String <-> int\nint num = Integer.parseInt(\"42\");\nString str = String.valueOf(42);\n\n// int <-> long\nlong big = (long) smallInt;\nint small = (int) bigLong; // Careful: truncates if value exceeds int range\n\n// Array to List (for object arrays only)\nString[] arr = {\"a\", \"b\", \"c\"};\nList list = new ArrayList<>(Arrays.asList(arr));\n\n// List to array\nString[] arr = list.toArray(new String[0]);\n```\n\n\n**Deep copy vs shallow copy:**\n\nWhen you add a list to another list, you are adding a reference. If the original list changes later, the \"copy\" changes too:\n\n\n```java\nList path = new ArrayList<>();\npath.add(1);\npath.add(2);\n\nList> results = new ArrayList<>();\nresults.add(path); // BAD: adds reference\npath.add(3);\n// results now contains [1, 2, 3], not [1, 2]\n\nresults.add(new ArrayList<>(path)); // GOOD: adds a copy\n```\n\n\nFor arrays, use `Arrays.copyOf()` or `arr.clone()`:\n\n\n```java\nint[] copy = Arrays.copyOf(original, original.length);\nint[] copy = original.clone();\n```\n\n\nFor 2D arrays, `clone()` only copies the outer array. The inner arrays are still shared references. You need a manual deep copy:\n\n\n```java\nint[][] deepCopy = new int[matrix.length][];\nfor (int i = 0; i < matrix.length; i++) {\n deepCopy[i] = matrix[i].clone();\n}\n```\n\n\n---\n\n# OOP Basics for Design Problems\n\nDSA problems often define custom node classes. These definitions appear throughout the course.\n\n\n```java\n// Linked list node\nclass ListNode {\n int val;\n ListNode next;\n\n ListNode(int val) {\n this.val = val;\n this.next = null;\n }\n\n // Overloaded constructor (used in some problems)\n ListNode(int val, ListNode next) {\n this.val = val;\n this.next = next;\n }\n}\n\n// Binary tree node\nclass TreeNode {\n int val;\n TreeNode left;\n TreeNode right;\n\n TreeNode(int val) {\n this.val = val;\n }\n}\n\n// Graph node with neighbors\nclass Node {\n int val;\n List neighbors;\n\n Node(int val) {\n this.val = val;\n this.neighbors = new ArrayList<>();\n }\n}\n\n// Trie node\nclass TrieNode {\n TrieNode[] children;\n boolean isEndOfWord;\n\n TrieNode() {\n this.children = new TrieNode[26]; // For lowercase a-z\n this.isEndOfWord = false;\n }\n}\n```\n\n\nAll fields are package-private (no `private` keyword, no getters or setters). This is standard practice in DSA because it keeps the code concise and interview-focused. You are not building production software here. You are solving problems under time pressure, and the overhead of encapsulation adds no value.\n\nThe `this` keyword refers to the current instance. It appears most often in constructors to distinguish the parameter from the field (`this.val = val`).\n\n**Constructor overloading** allows multiple constructors with different parameters:\n\n\n```java\nclass ListNode {\n int val;\n ListNode next;\n\n ListNode() {} // Default\n ListNode(int val) { this.val = val; } // Value only\n ListNode(int val, ListNode next) { this.val = val; this.next = next; } // Value + next\n}\n```\n\n\nLeetCode often provides these overloaded constructors. The two-argument constructor is handy for building linked lists concisely:\n\n\n```java\n// Build list: 1 -> 2 -> 3 -> null\nListNode head = new ListNode(1, new ListNode(2, new ListNode(3)));\n```\n","pageType":"dsa"}

Get Premium