Java for Data Structures and Algorithms

1. Java Program Basics

Main Method and Program Structure

Every Java program starts with a main method. This is the entry point for execution.

public class Solution {

public static void main(String[] args) {
[Link]("Hello, DSA!");
}
}

Key points: ‑ Class name must match the ilename ([Link] for Solution class) ‑ main method
must be public static void ‑ args is a String array for command‑line input (rarely used in DSA)
‑ public class is required; can also be package‑private (no modi ier)

Printing Output

// Standard output
[Link]("Value: " + 5); // Prints and adds newline
[Link]("No newline"); // No newline at end
[Link]("%d %s\n", 10, "text"); // Formatted output

Fast Input Using Scanner

import [Link];

public class Solution {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);

int n = [Link]();
double d = [Link]();
String s = [Link](); // Single word
String line = [Link](); // Entire line
boolean b = [Link](); // Check if next token is int

[Link](); // Good practice to close

1
 }
}

Common pattern in online judges:

import [Link];

public class Solution {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int t = [Link](); // Number of test cases

while (t-- > 0) {

int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = [Link]();
}
// Solve and print answer
}
[Link]();
}
}

Fast I/O for Competitive Programming

For very fast input/output, use BufferedReader (faster than Scanner):

import [Link].*;

public class Solution {

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader([Link]));
PrintWriter pw = new PrintWriter([Link]);

int n = [Link]([Link]());
String[] parts = [Link]().split(" ");

[Link]("Answer");
[Link](); // Important: flush before closing

2
 [Link]();
}
}

2. Data Types and Variables

Primitive Data Types

// Integer types
int x = 10; // 32-bit, range: -2^31 to 2^31-1
long y = 10000000000L; // 64-bit, must end with 'L'
short s = 100; // 16-bit (rarely used)
byte b = 10; // 8-bit (rarely used)

// Floating-point
double d = 3.14; // 64-bit (default)
float f = 3.14f; // 32-bit (rarely used in DSA)

// Character and boolean

char c = 'A'; // Single character, stored as int code
boolean flag = true; // true or false

Reference Types

Variables that reference objects, not primitives:

String str = "hello";

int[] arr = new int[5];
ArrayList<Integer> list = new ArrayList<>();

Memory difference: ‑ Primitive: value stored directly in variable ‑ Reference: variable stores mem‑
ory address of object

Over low and Type Casting

// Overflow: value wraps around

int max = Integer.MAX_VALUE; // 2147483647
int overflow = max + 1; // Wraps to -2147483648 (WRONG!)

3
// Solution: use long for large numbers
long safeValue = (long) max + 1; // Correctly becomes 2147483648L

// Type casting
int i = 10;
long l = (long) i; // Widening (implicit)
int j = (int) l; // Narrowing (explicit cast required)
double d = 3.14;
int k = (int) d; // Loses decimal part: k = 3

Useful Constants

int maxInt = Integer.MAX_VALUE; // 2147483647

int minInt = Integer.MIN_VALUE; // -2147483648
long maxLong = Long.MAX_VALUE; // 9223372036854775807L
long minLong = Long.MIN_VALUE;
double maxDouble = Double.MAX_VALUE;
double minDouble = Double.MIN_VALUE;

// Character codes
char zero = '0'; // Unicode 48
char a = 'a'; // Unicode 97

When to Use Long

• Array size or loop count exceeds 10^6? Use int ( ine)

• Multiplication result might exceed 2 × 10^9? Use long
• Factorial, Fibonacci, or products? Use long
• Time calculations in milliseconds? Use long
• Safe rule: when in doubt, use long

// Problem: Count pairs in array of size 10^5

// Wrong: int count = 0; // Could overflow
// Right:
long count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
count++; // Could reach ~5 × 10^9
}

4
}

3. Control Flow
If‑Else Statements

int x = 10;

if (x > 0) {
[Link]("Positive");
} else if (x < 0) {
[Link]("Negative");
} else {
[Link]("Zero");
}

// Ternary operator (inline conditional)

String result = (x > 0) ? "Positive" : "Not positive";

For Loop

// Traditional for loop (used most in DSA)

for (int i = 0; i < 5; i++) {
[Link](i); // 0 1 2 3 4
}

// For-each loop (iterate over array/collection)

int[] arr = {1, 2, 3};
for (int num : arr) {
[Link](num);
}

// Iterate over strings

String s = "hello";
for (char c : [Link]()) {
[Link](c);
}

5
// Reverse loop
for (int i = n - 1; i >= 0; i--) {
[Link](i);
}

// Multiple variables
for (int i = 0, j = 10; i < 5; i++, j--) {
[Link](i + " " + j);
}

While and Do‑While

int i = 0;
while (i < 5) {
[Link](i);
i++;
}

// Do-while: executes at least once

int j = 5;
do {
[Link](j);
j++;
} while (j < 5); // Won't execute loop body, but do executes once

Break and Continue

for (int i = 0; i < 10; i++) {

if (i == 5) break; // Exit loop
if (i == 2) continue; // Skip to next iteration
[Link](i); // 0 1 3 4
}

// Label break (exit outer loop)

outerLoop:
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i == 1 && j == 1) break outerLoop;

6
 [Link](i + " " + j);
}
}

4. Methods
De ining and Calling Methods

public class Solution {

// Method definition
static int add(int a, int b) {
return a + b;
}

// Method with no return value

static void printNumber(int n) {
[Link](n);
}

// Method with multiple parameters

static double average(int x, int y, int z) {
return (x + y + z) / 3.0;
}

public static void main(String[] args) {

int result = add(5, 3); // Call: 8
printNumber(10);
double avg = average(10, 20, 30); // 20.0
}
}

Method signature: static returnType methodName(paramType param, ...)

Return Types

static int getValue() {

return 42;
}

7
static String getText() {
return "hello";
}

static int[] getArray() {

return new int[]{1, 2, 3};
}

static List<Integer> getList() {

return new ArrayList<>();
}

static void doNothing() {

// No return statement needed
}

Variable Scope

static void demo() {

int x = 5; // Scope: entire method

if (true) {
int y = 10; // Scope: only inside if block
[Link](x); // OK
}
// [Link](y); // ERROR: y out of scope
}

Recursion Basics

// Factorial: n! = n * (n-1)!
static int factorial(int n) {
if (n == 0) return 1; // Base case
return n * factorial(n - 1); // Recursive case
}

// Fibonacci: fib(n) = fib(n-1) + fib(n-2)

static int fib(int n) {

8
 if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}

// Reverse array using recursion

static void reverseArray(int[] arr, int start, int end) {
if (start >= end) return; // Base case

// Swap
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;

reverseArray(arr, start + 1, end - 1);

}

Stack over low: Too deep recursion causes StackOver lowError. Use iterative approach for n >
10000.

5. Arrays
1D Arrays

// Declaration and initialization

int[] arr = new int[5]; // Size 5, default values: 0
int[] arr2 = {1, 2, 3, 4, 5}; // Literal initialization
Integer[] arr3 = new Integer[5]; // Default: null

// Accessing elements
arr[0] = 10;
[Link](arr[0]);

// Length
int size = [Link];

// Iteration
for (int i = 0; i < [Link]; i++) {

9
 [Link](arr[i]);
}

for (int num : arr) {

[Link](num);
}

2D Arrays

// Declaration and initialization

int[][] matrix = new int[3][4]; // 3 rows, 4 columns
int[][] matrix2 = {{1, 2}, {3, 4}}; // Literal init

// Accessing
matrix[0][1] = 5;
[Link](matrix[0][1]);

// Iteration
for (int i = 0; i < [Link]; i++) {
for (int j = 0; j < matrix[i].length; j++) {
[Link](matrix[i][j]);
}
}

// For-each
for (int[] row : matrix) {
for (int val : row) {
[Link](val);
}
}

// Jagged array (rows have different lengths)

int[][] jagged = new int[3][];
jagged[0] = new int[2];
jagged[1] = new int[4];
jagged[2] = new int[1];

10
Common Array Operations

// Copy array
int[] original = {1, 2, 3};
int[] copy = [Link]();
// OR
int[] copy2 = new int[[Link]];
[Link](original, 0, copy2, 0, [Link]);

// Fill array
[Link](arr, 0); // Fill all with 0
[Link](arr, 2, 5, 99); // Fill index 2 to 4 with 99

// Sort array
[Link](arr); // Ascending order

// Binary search (requires sorted array)

int index = [Link](arr, 5);

// Convert array to string

[Link]([Link](arr));

// Check if array contains value

boolean contains = [Link](arr).anyMatch(x -> x == 5);

Passing Arrays to Methods

static void modifyArray(int[] arr) {

arr[0] = 100; // Changes original array
}

static int[] returnArray() {

return new int[]{1, 2, 3};
}

public static void main(String[] args) {

int[] arr = {1, 2, 3};
modifyArray(arr);

11
 [Link](arr[0]); // 100 (modified!)
}

Important: Arrays are passed by reference. Changes inside the method affect the original array.

Common Mistakes

// MISTAKE 1: Using == to compare arrays

int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
[Link](a == b); // false (different objects)
[Link]([Link](a, b)); // true (correct)

// MISTAKE 2: Off-by-one error

int[] arr = new int[5]; // Indices: 0, 1, 2, 3, 4
// arr[5] = 10; // ERROR: IndexOutOfBoundsException

// MISTAKE 3: Accessing array before initialization

int[] arr2;
// [Link](arr2[0]); // ERROR: arr2 not initialized

// MISTAKE 4: Modifying array while iterating (for-each)

ArrayList<Integer> list = new ArrayList<>([Link](1, 2, 3));
for (int num : list) {
if (num == 2) [Link]((Integer) num); // Causes issues
}
// Better: use iterator or loop backwards

6. Strings
String Basics

// Strings are immutable in Java

String s1 = "hello";
String s2 = new String("hello"); // Usually not needed

// String concatenation
String s3 = "Hello" + " " + "World"; // "Hello World"

12
String s4 = s1 + 123; // "hello123"

// String length
int len = [Link](); // 5

// Empty string check

boolean isEmpty = [Link]();

Common String Methods

String s = "hello";

// Character access
char c = [Link](0); // 'h'
char[] chars = [Link](); // ['h','e','l','l','o']

// Substring
String sub = [Link](1); // "ello" (from index 1 to end)
String sub2 = [Link](1, 3); // "el" (from 1 to 3 exclusive)

// Case conversion
String upper = [Link](); // "HELLO"
String lower = "HELLO".toLowerCase(); // "hello"

// Trimming whitespace
String trimmed = " hello ".trim(); // "hello"

// Splitting
String[] parts = "a,b,c".split(","); // ["a", "b", "c"]

// Finding substring
int index = [Link]('e'); // 1
int index2 = [Link]("ll"); // 2
boolean contains = [Link]("ell"); // true

// Replacing
String replaced = [Link]('l', 'x'); // "hexxo"
String replaced2 = [Link]("l", "x"); // "hexxo"

13
// Starting and ending
boolean startsWithH = [Link]("he"); // true
boolean endsWithO = [Link]("lo"); // true

Comparing Strings

String s1 = "hello";
String s2 = "hello";
String s3 = new String("hello");

// WRONG: Never use == for string comparison

[Link](s1 == s2); // true (same object - luck)
[Link](s1 == s3); // false (different objects)

// RIGHT: Use equals()

[Link]([Link](s2)); // true
[Link]([Link](s3)); // true
[Link]([Link]("HELLO")); // true

// Compare lexicographically
int cmp = [Link](s2); // 0 if equal, <0 if s1 < s2, >0 if s1 > s2

StringBuilder for Fast String Operations

// Problem: String concatenation in loop creates new objects

String result = "";
for (int i = 0; i < 1000; i++) {
result += i; // Slow! Creates 1000 new String objects
}

// Solution: Use StringBuilder

StringBuilder sb = new StringBuilder();
for (int i = 0; i < 1000; i++) {
[Link](i);
}
String result = [Link]();

// Common StringBuilder methods

14
[Link]("hello"); // Add at end
[Link](0, "start"); // Insert at position
[Link](0); // Delete character at index
[Link](0, 5); // Delete range
[Link](); // Reverse
[Link](0, 'H'); // Set character at index
String str = [Link](); // Convert to String
int len = [Link](); // Length

Character Operations

char c = 'A';

// Character classification
boolean isDigit = [Link](c); // false
boolean isLetter = [Link](c); // true
boolean isLowerCase = [Link](c); // false
boolean isUpperCase = [Link](c); // true

// Case conversion
char lower = [Link](c); // 'a'
char upper = [Link](c); // 'A'

// Get numeric value

int digitValue = [Link]('5'); // 5

// Character codes
char fromCode = (char) 65; // 'A'
int code = (int) 'A'; // 65

Converting Between String and Array

// String to char array

String s = "hello";
char[] chars = [Link]();

// Char array to String

char[] arr = {'h', 'e', 'l', 'l', 'o'};
String str = new String(arr);

15
String str2 = [Link](arr);

// String to int array

String numbers = "1 2 3 4";
int[] arr = [Link]([Link](" "))
.mapToInt(Integer::parseInt)
.toArray();

// Simpler way for DSA

String[] parts = "1 2 3 4".split(" ");
int[] arr2 = new int[[Link]];
for (int i = 0; i < [Link]; i++) {
arr2[i] = [Link](parts[i]);
}

// String to digit array

String digits = "12345";
int[] arr3 = new int[[Link]()];
for (int i = 0; i < [Link](); i++) {
arr3[i] = [Link](i) - '0'; // '1' - '0' = 1
}

7. Java Collections for DSA

ArrayList

import [Link];
import [Link];

// Creation and initialization

ArrayList<Integer> list = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>([Link](1, 2, 3, 4));

// Add and remove

[Link](5); // Add at end
[Link](0, 10); // Add at index 0
[Link](0); // Remove at index 0

16
[Link]((Integer) 5); // Remove first occurrence of value
[Link](); // Remove all

// Access
int val = [Link](0);
[Link](0, 100); // Update value at index

// Size and check

int size = [Link]();
boolean isEmpty = [Link]();
boolean contains = [Link](5);

// Iteration
for (int i = 0; i < [Link](); i++) {
[Link]([Link](i));
}

for (int num : list) {

[Link](num);
}

// Convert to array
int[] arr = [Link]().mapToInt(i -> i).toArray();
Integer[] arr2 = [Link](new Integer[0]);

// Common operations
[Link](5); // First index of value
[Link](5); // Last index of value
ArrayList<Integer> subList = new ArrayList<>([Link](0, 3));

When to use: Variable‑size collections, need indexing, frequent access by index.

LinkedList

import [Link];

LinkedList<Integer> list = new LinkedList<>();

// Add

17
[Link](5); // Add at end
[Link](1); // Add at beginning
[Link](10); // Add at end

// Remove
[Link](); // Remove first element
[Link](); // Remove last element
[Link](0); // Remove at index

// Access
int first = [Link]();
int last = [Link]();
int val = [Link](0);

// Iteration
for (int num : list) {
[Link](num);
}

When to use: Frequent additions/removals at both ends (not common in DSA).

Stack (Using Deque)

import [Link];
import [Link];

Deque<Integer> stack = new ArrayDeque<>();

// Push (add to top)

[Link](5);

// Pop (remove from top)

int top = [Link]();

// Peek (view top without removing)

int top2 = [Link]();
int top3 = [Link]();

// Size and check

18
int size = [Link]();
boolean isEmpty = [Link]();

// Iteration (from top to bottom)

for (int num : stack) {
[Link](num);
}

Common uses: DFS, expression evaluation, backtracking, undo operations.

Queue (Using Deque or Queue)

import [Link];
import [Link];
import [Link];

// Using ArrayDeque (faster)

Queue<Integer> queue = new ArrayDeque<>();

// Using LinkedList (also works)

Queue<Integer> queue2 = new LinkedList<>();

// Enqueue (add to rear)

[Link](5); // or add(5)

// Dequeue (remove from front)

int front = [Link](); // Returns null if empty
int front2 = [Link](); // Throws exception if empty

// Peek (view front)

int val = [Link](); // Returns null if empty
int val2 = [Link](); // Throws exception if empty

// Size and check

int size = [Link]();
boolean isEmpty = [Link]();

// Iteration
for (int num : queue) {

19
 [Link](num);
}

Common uses: BFS, level‑order traversal, sliding window.

PriorityQueue (Heap)

import [Link];
import [Link];

// Min-heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
[Link](5);
[Link](3);
[Link](7);
[Link]([Link]()); // 3

// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>([Link]());
[Link](5);
[Link](3);
[Link](7);
[Link]([Link]()); // 7

// Peek (view top without removing)

int top = [Link]();

// Common operations
int size = [Link]();
boolean isEmpty = [Link]();
[Link]();

// Custom comparator (for objects)

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // Max-heap

// Using with custom objects

class Item {
int value;
Item(int value) { [Link] = value; }

20
}

PriorityQueue<Item> pq2 = new PriorityQueue<>((a, b) -> [Link]([Link], [Link]))

[Link](new Item(5));
[Link](new Item(3));
Item top2 = [Link](); // Item with value 3

Common uses: Top K elements, Dijkstra’s algorithm, median inding, task scheduling.

HashSet

import [Link];
import [Link];

Set<Integer> set = new HashSet<>();

// Add
[Link](5);
[Link](3);
[Link](5); // Duplicate, not added

// Remove
[Link](5);
[Link]();

// Check membership
boolean contains = [Link](3);

// Size
int size = [Link]();
boolean isEmpty = [Link]();

// Iteration (order not guaranteed)

for (int num : set) {
[Link](num);
}

// Convert to array
Integer[] arr = [Link](new Integer[0]);

21
// Set operations
Set<Integer> s1 = new HashSet<>([Link](1, 2, 3));
Set<Integer> s2 = new HashSet<>([Link](2, 3, 4));

[Link](s2); // Intersection: s1 becomes {2, 3}

[Link](s2); // Union
[Link](s2); // Difference

Common uses: Remove duplicates, check membership, ind unique elements.

HashMap

import [Link];
import [Link];

Map<String, Integer> map = new HashMap<>();

// Put (add/update)
[Link]("apple", 5);
[Link]("banana", 3);

// Get
Integer value = [Link]("apple"); // 5
Integer value2 = [Link]("cherry", 0); // 0 if key not found

// Remove
[Link]("apple");
[Link]();

// Check
boolean hasKey = [Link]("banana");
boolean hasValue = [Link](3);

// Size
int size = [Link]();
boolean isEmpty = [Link]();

// Iteration

22
for (String key : [Link]()) {
[Link](key + " -> " + [Link](key));
}

for ([Link]<String, Integer> entry : [Link]()) {

[Link]([Link]() + " -> " + [Link]());
}

for (Integer val : [Link]()) {

[Link](val);
}

// Common operations
[Link]("apple", 10); // Only put if key doesn't exist
[Link]("apple", (k, v) -> v == null ? 1 : v + 1); // Update with function

Common uses: Frequency counting, key‑value storage, caching, grouping.

TreeMap and TreeSet

import [Link];
import [Link];

// TreeMap: sorted by key

TreeMap<Integer, String> treeMap = new TreeMap<>();
[Link](5, "apple");
[Link](3, "banana");
[Link](7, "cherry");

// Keys are in sorted order

for (Integer key : [Link]()) {
[Link](key); // 3, 5, 7
}

// Useful methods
Integer firstKey = [Link](); // 3
Integer lastKey = [Link](); // 7
Integer floorKey = [Link](4); // 3 (greatest <= 4)
Integer ceilingKey = [Link](4); // 5 (least >= 4)

23
Integer lower = [Link](5); // 3 (strictly less)
Integer higher = [Link](5); // 7 (strictly greater)

// TreeSet: sorted set

TreeSet<Integer> treeSet = new TreeSet<>();
[Link](5);
[Link](3);
[Link](7);

// Same floor/ceiling/lower/higher methods

[Link]([Link](4)); // 3
[Link]([Link](4)); // 5

When to use: Need sorted order, range queries, median in stream (use two heaps usually).

Deque (Double‑Ended Queue)

import [Link];
import [Link];

Deque<Integer> deque = new ArrayDeque<>();

// Add at both ends

[Link](1); // Add at front
[Link](5); // Add at rear
[Link](0); // Add at front
[Link](10); // Add at rear

// Remove from both ends

int front = [Link](); // Remove from front
int rear = [Link](); // Remove from rear
int front2 = [Link](); // Remove from front (null if empty)
int rear2 = [Link](); // Remove from rear (null if empty)

// Peek both ends

int first = [Link]();
int last = [Link]();
int first2 = [Link](); // null if empty
int last2 = [Link]();

24
// Iteration
for (int num : deque) {
[Link](num);
}

Common uses: Sliding window maximum, palace checker (palindrome), sliding window variants.

8. Sorting and Searching Helpers

Sorting Arrays

import [Link];

int[] arr = {5, 2, 8, 1, 9};

// Sort in ascending order

[Link](arr); // arr is now {1, 2, 5, 8, 9}

// Sort a range
int[] arr2 = {5, 2, 8, 1, 9};
[Link](arr2, 1, 4); // Sort from index 1 to 3 (exclusive 4)

// Sort in descending order (for Integer, not int)

Integer[] arr3 = {5, 2, 8, 1, 9};
[Link](arr3, [Link]());

// Custom sorting with comparator

[Link](arr3, (a, b) -> b - a); // Descending
[Link](arr3, (a, b) -> a - b); // Ascending (default)

Sorting Collections

import [Link];
import [Link];

ArrayList<Integer> list = new ArrayList<>([Link](5, 2, 8, 1));

25
// Sort in ascending order
[Link](list);

// Sort in descending order

[Link](list, [Link]());

// Custom comparator
[Link](list, (a, b) -> a - b); // Ascending
[Link](list, (a, b) -> b - a); // Descending

// Reverse a list
[Link](list);

Custom Comparators

// Comparator syntax: (a, b) -> return value

// Return < 0: a comes before b
// Return = 0: a equals b (no reorder)
// Return > 0: a comes after b

// Sort by absolute value

[Link](arr, (a, b) -> [Link]([Link](a), [Link](b)));

// Sort by multiple criteria

Integer[][] pairs = {{1, 2}, {1, 1}, {2, 1}};
[Link](pairs, (a, b) -> {
if (a[0] != b[0]) {
return a[0] - b[0]; // First by first element
}
return a[1] - b[1]; // Then by second element
});

// Reverse within the comparator

[Link](arr, (a, b) -> [Link](b, a)); // Descending

Binary Search

import [Link];

26
int[] arr = {1, 3, 5, 7, 9};

// Binary search on sorted array

int index = [Link](arr, 5); // Returns 2 (index of 5)
int notFound = [Link](arr, 4); // Returns -(2+1) = -3

// If not found, can use: index = -index - 1 to get insertion point

if (index < 0) {
int insertionPoint = -index - 1; // Where 4 should be inserted
}

// Using [Link] on List

List<Integer> list = new ArrayList<>([Link](1, 3, 5, 7, 9));
int index2 = [Link](list, 5);

// Lambda sorting and searching example

class Person {
String name;
int age;
Person(String name, int age) {
[Link] = name;
[Link] = age;
}
}

Person[] people = {new Person("Alice", 30), new Person("Bob", 25)};

[Link](people, (a, b) -> [Link]([Link], [Link]));

9. Custom Classes
Simple Class De inition

class Node {
int val;
Node next;

Node(int val) {

27
 [Link] = val;
[Link] = null;
}
}

class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int val) {
[Link] = val;
[Link] = null;
[Link] = null;
}
}

class Pair {
int first;
int second;

Pair(int first, int second) {

[Link] = first;
[Link] = second;
}
}

Usage in DSA

// Using custom classes

Node head = new Node(1);
[Link] = new Node(2);
[Link] = new Node(3);

// Traverse linked list

Node current = head;
while (current != null) {
[Link]([Link]);

28
 current = [Link];
}

// Using Pair in ArrayList

ArrayList<Pair> pairs = new ArrayList<>();
[Link](new Pair(1, 2));
[Link](new Pair(3, 4));

for (Pair p : pairs) {

[Link]([Link] + " " + [Link]);
}

Class with Comparator (for sorting)

class Person implements Comparable<Person> {

String name;
int age;

Person(String name, int age) {

[Link] = name;
[Link] = age;
}

@Override
public int compareTo(Person other) {
return [Link]([Link], [Link]);
}
}

// Usage
ArrayList<Person> people = new ArrayList<>();
[Link](new Person("Alice", 30));
[Link](new Person("Bob", 25));
[Link](people); // Sorted by age

// Or use lambda
[Link](people, (a, b) -> [Link]([Link], [Link]));

29
10. Common DSA Patterns in Java
Two Pointers

// Example: Two Sum in sorted array

int[] arr = {1, 3, 5, 7, 9};
int target = 12;

int left = 0, right = [Link] - 1;

while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
[Link](left + " " + right);
break;
} else if (sum < target) {
left++;
} else {
right--;
}
}

// Example: Reverse array

void reverseArray(int[] arr) {
int left = 0, right = [Link] - 1;
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}

Sliding Window

// Example: Maximum sum of subarray of size k

int[] arr = {1, 3, 2, 6, -1, 4, 1, 8};
int k = 3;

30
int maxSum = 0;
int currentSum = 0;

// Initial window
for (int i = 0; i < k; i++) {
currentSum += arr[i];
}
maxSum = currentSum;

// Slide the window

for (int i = k; i < [Link]; i++) {
currentSum = currentSum - arr[i - k] + arr[i];
maxSum = [Link](maxSum, currentSum);
}

[Link](maxSum); // 18 (6 + -1 + 4 + 1 + 8)

Fast and Slow Pointers

// Example: Detect cycle in linked list

class ListNode {
int val;
ListNode next;
ListNode(int val) { [Link] = val; }
}

boolean hasCycle(ListNode head) {

if (head == null) return false;
ListNode slow = head, fast = head;

while (fast != null && [Link] != null) {

slow = [Link];
fast = [Link];

if (slow == fast) return true; // Cycle detected

}
return false;
}

31
// Example: Find middle of linked list
ListNode findMiddle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && [Link] != null) {
slow = [Link];
fast = [Link];
}
return slow; // Middle node
}

Pre ix Sum

// Example: Range sum query

int[] arr = {1, 2, 3, 4, 5};
int[] prefix = new int[[Link] + 1];

// Build prefix sum array

for (int i = 0; i < [Link]; i++) {
prefix[i + 1] = prefix[i] + arr[i];
}
// prefix = {0, 1, 3, 6, 10, 15}

// Query sum from index l to r (inclusive)

int l = 1, r = 3;
int sum = prefix[r + 1] - prefix[l]; // arr[1] + arr[2] + arr[3] = 2 + 3 + 4 = 9

Binary Search Template

// Template 1: Finding exact value

int[] arr = {1, 3, 5, 7, 9};
int target = 5;

int left = 0, right = [Link] - 1;

while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
[Link](mid);
break;

32
 } else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}

// Template 2: Finding leftmost position

int left = 0, right = [Link] - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
[Link](result);

// Template 3: Finding rightmost position

left = 0;
right = [Link] - 1;
result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
[Link](result);

33
BFS (Breadth‑First Search)

import [Link];
import [Link];
import [Link];

class Node {
int val;
ArrayList<Node> neighbors;
Node(int val) {
[Link] = val;
neighbors = new ArrayList<>();
}
}

// BFS traversal
void bfs(Node start) {
Queue<Node> queue = new ArrayDeque<>();
Set<Node> visited = new HashSet<>();

[Link](start);
[Link](start);

while (![Link]()) {
Node node = [Link]();
[Link]([Link]);

for (Node neighbor : [Link]) {

if () {
[Link](neighbor);
[Link](neighbor);
}
}
}
}

// BFS with level tracking

void bfsWithLevels(Node start) {

34
 Queue<Node> queue = new ArrayDeque<>();
[Link](start);

while (![Link]()) {
int levelSize = [Link]();
for (int i = 0; i < levelSize; i++) {
Node node = [Link]();
[Link]([Link] + " ");

for (Node neighbor : [Link]) {

[Link](neighbor);
}
}
[Link](); // New level
}
}

DFS (Depth‑First Search)

// DFS recursive
void dfsRecursive(Node node, Set<Node> visited) {
[Link](node);
[Link]([Link]);

for (Node neighbor : [Link]) {

if () {
dfsRecursive(neighbor, visited);
}
}
}

// DFS iterative
void dfsIterative(Node start) {
Deque<Node> stack = new ArrayDeque<>();
Set<Node> visited = new HashSet<>();

[Link](start);
[Link](start);

35
 while (![Link]()) {
Node node = [Link]();
[Link]([Link]);

for (Node neighbor : [Link]) {

if () {
[Link](neighbor);
[Link](neighbor);
}
}
}
}

// DFS on tree (no visited set needed)

void dfsTree(TreeNode root) {
if (root == null) return;

[Link]([Link]);
dfsTree([Link]);
dfsTree([Link]);
}

Recursion and Backtracking

// Example: Generate all permutations

void permute(int[] nums, List<Integer> current, boolean[] used, List<List<Integer>> result)
if ([Link]() == [Link]) {
[Link](new ArrayList<>(current));
return;
}

for (int i = 0; i < [Link]; i++) {

if (used[i]) continue;

// Choose
[Link](nums[i]);
used[i] = true;

36
 // Explore
permute(nums, current, used, result);

// Unchoose (backtrack)
[Link]([Link]() - 1);
used[i] = false;
}
}

// Example: Combination sum

void combinationSum(int[] candidates, int target, int start, List<Integer> current, List<Li
if (target == 0) {
[Link](new ArrayList<>(current));
return;
}
if (target < 0) return;

for (int i = start; i < [Link]; i++) {

[Link](candidates[i]);
combinationSum(candidates, target - candidates[i], i, current, result);
[Link]([Link]() - 1);
}
}

11. Input Size and Performance Tips

When to Use Long

// Rule: If result or intermediate computation exceeds 2 × 10^9, use long

// Example 1: Array element count

if (n > 10^6) {
long count = 0; // Safe
// ...
}

37
// Example 2: Product of two numbers
int a = 100000, b = 100000;
long product = (long) a * b; // 10^10, exceeds int range

// Example 3: Sum of array elements

long sum = 0;
for (int num : arr) {
sum += num;
}

// Example 4: Time/index calculations

long totalTimeMs = (long) n * n; // Avoid overflow

Avoiding Slow Operations

// SLOW: String concatenation in loop

String result = "";
for (int i = 0; i < 10000; i++) {
result += i; // Creates 10000 new String objects
}

// FAST: Use StringBuilder

StringBuilder sb = new StringBuilder();
for (int i = 0; i < 10000; i++) {
[Link](i);
}
String result = [Link]();

// SLOW: Accessing ArrayList by index in nested loop

for (int i = 0; i < [Link](); i++) {
for (int j = 0; j < [Link](); j++) {
int val = [Link](i); // OK for ArrayList
}
}

// Check complexity of operations:

// [Link](i): O(1)
// [Link]()/remove(0): O(n)

38
// [Link](i): O(n)
// [Link](0)/remove(0): O(1)
// [Link]/remove/contains: O(1) avg
// [Link]/get: O(1) avg
// TreeSet/TreeMap operations: O(log n)

Pre‑sizing Collections

// BAD: ArrayList grows dynamically

ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
[Link](i); // Causes resizing at certain points
}

// GOOD: Pre-size the ArrayList

ArrayList<Integer> list = new ArrayList<>(100000);
for (int i = 0; i < 100000; i++) {
[Link](i);
}

// GOOD: Use array if size is known

int[] arr = new int[100000];
for (int i = 0; i < 100000; i++) {
arr[i] = i;
}

Time Complexity Awareness

// O(n): Simple loop

for (int i = 0; i < n; i++) {
// O(1) operation
}

// O(n log n): Sorting or using TreeSet/TreeMap

[Link](arr);
TreeSet<Integer> set = new TreeSet<>();

// O(n^2): Nested loop

for (int i = 0; i < n; i++) {

39
 for (int j = 0; j < n; j++) {
// O(1) operation
}
}

// Acceptable for DSA (n � 10^6):

// - O(n): Always safe
// - O(n log n): Safe (sorting, tree operations)
// - O(n√n): Safe for n � 10^5

// Acceptable for DSA (n � 10^5):

// - O(n^2): Borderline, might TLE
// - O(n^2 log n): Only if optimized

// Not acceptable:
// - O(2^n): Only for n � 20
// - O(n!): Only for n � 10

12. Java Gotchas in DSA

== vs equals()

// GOTCHA: == compares object references, not values

String s1 = new String("hello");
String s2 = new String("hello");
[Link](s1 == s2); // false (different objects)
[Link]([Link](s2)); // true (same content)

// Integer special case: caching

Integer a = 100;
Integer b = 100;
[Link](a == b); // true (cached -128 to 127)

Integer c = 128;
Integer d = 128;
[Link](c == d); // false (not cached)

40
// CORRECT: Always use equals() for objects
if ([Link](s2)) { }
if ([Link](b)) { }

// For primitives, == is fine

int x = 5;
int y = 5;
[Link](x == y); // true

NullPointerException

// GOTCHA: Accessing properties of null

String s = null;
// [Link]([Link]()); // NullPointerException

// CORRECT: Check for null

if (s != null) {
[Link]([Link]());
}

// Safe navigation
String length = s != null ? [Link]([Link]()) : "N/A";

// In collections
ArrayList<Integer> list = null;
// for (int num : list) { } // NullPointerException

// Check before using

if (list != null && ![Link]()) {
for (int num : list) { }
}

// Common: get() returns null if key not found

Map<String, Integer> map = new HashMap<>();
Integer value = [Link]("missing"); // null
int v = value + 1; // NullPointerException!

// CORRECT: Use getOrDefault or check

41
int v = [Link]("missing", 0) + 1;

Off‑by‑One Errors

// GOTCHA: Array length is n, but last index is n-1

int[] arr = new int[5];
// arr[5] = 0; // IndexOutOfBoundsException

// Correct iteration
for (int i = 0; i < [Link]; i++) {
arr[i] = i;
}

// GOTCHA: substring uses exclusive end

String s = "hello";
[Link]([Link](0, 2)); // "he" (not including index 2)
[Link]([Link](2)); // "llo" (from index 2 to end)

// GOTCHA: [Link] uses exclusive end

List<Integer> list = new ArrayList<>([Link](1, 2, 3, 4, 5));
List<Integer> sub = [Link](1, 3); // Indices 1, 2 (not 3)
[Link](sub); // [2, 3]

// GOTCHA: Loop boundaries

for (int i = 0; i <= n; i++) { // Includes n (n+1 iterations)
// ...
}

for (int i = 0; i < n; i++) { // Excludes n (n iterations)

// ...
}

Modulo with Negatives

// GOTCHA: Java modulo preserves sign of dividend

[Link](-5 % 3); // -2 (not 1)
[Link](5 % -3); // 2 (not -1)

// CORRECT: For positive result, add modulo

42
int mod = (n % m + m) % m; // Always positive result

// Example
int result = (-5 % 3 + 3) % 3; // 1

Over low

// GOTCHA: Integer overflow wraps around

int x = Integer.MAX_VALUE; // 2147483647
int y = x + 1; // Wraps to -2147483648 (WRONG!)

// CORRECT: Use long

long y = (long) x + 1; // 2147483648L

// GOTCHA: Overflow in intermediate calculation

int a = 100000, b = 100000;
int product = a * b; // Overflows before converting
long product = (long) a * b; // CORRECT: cast before multiplication

// GOTCHA: Subtraction can also overflow

int a = Integer.MIN_VALUE;
// int b = a - 1; // Overflow
long b = (long) a - 1; // CORRECT

Integer Caching Edge Cases

// Cached: -128 to 127

Integer a = 127;
Integer b = 127;
[Link](a == b); // true

Integer c = 128;
Integer d = 128;
[Link](c == d); // false

// SOLUTION: Always use equals() or unwrap to int

[Link]([Link](b)); // true (both cases)

43
Floating‑Point Precision

// GOTCHA: Floating-point precision issues

double a = 0.1 + 0.2;
[Link](a); // 0.30000000000000004 (not 0.3)

// CORRECT: Use epsilon for comparison

double epsilon = 1e-9;
if ([Link](a - 0.3) < epsilon) {
[Link]("Equal");
}

// In DSA: Avoid floating-point when possible

// Use integer arithmetic instead

13. Useful Built‑in Classes

Arrays Utility

import [Link];

int[] arr = {5, 2, 8, 1, 9};

// Sort
[Link](arr);

// Binary search (requires sorted array)

int index = [Link](arr, 5);

// Fill
[Link](arr, 0); // Fill all
[Link](arr, 2, 4, 99); // Fill range

// Copy
int[] copy = [Link](arr, [Link]);
int[] partial = [Link](arr, 1, 4);

44
// Convert to string
[Link]([Link](arr));

// Multi-dimensional array to string

int[][] matrix = {{1, 2}, {3, 4}};
[Link]([Link](matrix));

// Check equality
int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
[Link]([Link](a, b)); // true

Collections Utility

import [Link];
import [Link];

ArrayList<Integer> list = new ArrayList<>([Link](5, 2, 8, 1));

// Sort
[Link](list);

// Reverse sort
[Link](list, [Link]());

// Reverse
[Link](list);

// Min and max

int min = [Link](list);
int max = [Link](list);

// Shuffle
[Link](list);

// Rotate
[Link](list, 2);

45
// Copy
ArrayList<Integer> copy = new ArrayList<>(list);

// Fill
[Link](list, 0);

// Frequency
int count = [Link](list, 5);

Math Utility

import [Link];

// Basic
int abs = [Link](-5);
double sqrt = [Link](16); // 4.0
double pow = [Link](2, 3); // 8.0

// Min and max

int min = [Link](5, 3);
int max = [Link](5, 3);

// Rounding
double round = [Link](3.7); // 4.0
double floor = [Link](3.7); // 3.0
double ceil = [Link](3.2); // 4.0

// Constants
double pi = [Link];
double e = Math.E;

// Random
int random = (int) ([Link]() * 100); // 0 to 99

Deque

import [Link];
import [Link];

46
Deque<Integer> deque = new ArrayDeque<>();

// Add
[Link](1);
[Link](2);

// Remove
int first = [Link]();
int last = [Link]();

// Peek
int peekFirst = [Link]();
int peekLast = [Link]();

// Check
boolean isEmpty = [Link]();
int size = [Link]();

Comparator and Comparable

// Comparable: Natural ordering

class Person implements Comparable<Person> {
int age;
String name;

@Override
public int compareTo(Person other) {
return [Link]([Link], [Link]);
}
}

// Comparator: Custom ordering

Comparator<Person> byName = (a, b) -> [Link]([Link]);
Comparator<Person> byAge = (a, b) -> [Link]([Link], [Link]);

// Chaining comparators
Comparator<Person> combined = [Link](byName);

47
// Usage
List<Person> people = new ArrayList<>();
[Link](new Person(30, "Alice"));
[Link](new Person(25, "Bob"));

[Link](people, byAge); // Sort by age

[Link](people, combined); // Sort by age, then name

14. Basic Exception Awareness

Common Exceptions in DSA

// IndexOutOfBoundsException
int[] arr = new int[5];
// arr[5] = 0; // IndexOutOfBoundsException

// NullPointerException
String s = null;
// [Link](); // NullPointerException

// NumberFormatException
// int x = [Link]("abc"); // NumberFormatException

// ArithmeticException
// int x = 5 / 0; // ArithmeticException

// InputMismatchException (Scanner)
Scanner sc = new Scanner("abc");
// int x = [Link](); // InputMismatchException

// To avoid: Always check boundaries and null

if (i >= 0 && i < [Link]) {
arr[i] = 5;
}

if (s != null) {
[Link]();

48
}

try {
int x = [Link](input);
} catch (NumberFormatException e) {
x = 0;
}

try‑catch (rarely needed in DSA)

try {
int x = [Link]("123");
int[] arr = new int[x];
arr[x] = 100; // IndexOutOfBoundsException
} catch (NumberFormatException e) {
[Link]("Invalid number");
} catch (ArrayIndexOutOfBoundsException e) {
[Link]("Array index out of bounds");
}

// In online judges: Usually let exceptions crash (helps debug)

// Only catch if you need to handle gracefully

15. Templates Section

Fast Input/Output Template

import [Link].*;

public class Solution {

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader([Link]));
PrintWriter pw = new PrintWriter([Link]);

int t = [Link]([Link]());
while (t-- > 0) {
int n = [Link]([Link]());

49
 String[] parts = [Link]().split(" ");
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = [Link](parts[i]);
}

// Solve
int answer = solve(arr);

[Link](answer);
}
[Link]();
[Link]();
}

static int solve(int[] arr) {

// Implementation
return 0;
}
}

BFS Template

Queue<Node> queue = new ArrayDeque<>();

Set<Node> visited = new HashSet<>();

[Link](startNode);
[Link](startNode);

while (![Link]()) {
Node node = [Link]();

for (Node neighbor : [Link]) {

if () {
[Link](neighbor);
[Link](neighbor);
}
}

50
}

// With distance tracking

Queue<Node> queue = new ArrayDeque<>();
Map<Node, Integer> distance = new HashMap<>();

[Link](startNode);
[Link](startNode, 0);

while (![Link]()) {
Node node = [Link]();

for (Node neighbor : [Link]) {

if () {
[Link](neighbor, [Link](node) + 1);
[Link](neighbor);
}
}
}

DFS Recursive Template

void dfs(Node node, Set<Node> visited) {

[Link](node);

// Process node
[Link]([Link]);

for (Node neighbor : [Link]) {

if () {
dfs(neighbor, visited);
}
}
}

// With return value

int dfs(Node node, Set<Node> visited) {
[Link](node);

51
 int result = [Link];

for (Node neighbor : [Link]) {

if () {
result += dfs(neighbor, visited);
}
}
return result;
}

DFS Iterative Template

Deque<Node> stack = new ArrayDeque<>();

Set<Node> visited = new HashSet<>();

[Link](startNode);
[Link](startNode);

while (![Link]()) {
Node node = [Link]();

// Process node
[Link]([Link]);

for (Node neighbor : [Link]) {

if () {
[Link](neighbor);
[Link](neighbor);
}
}
}

Binary Search Template

// Left-most position of target

int left = 0, right = [Link] - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;

52
 if (arr[mid] >= target) {
result = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
[Link](result);

// Right-most position of target

left = 0;
right = [Link] - 1;
result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
[Link](result);

Union‑Find Template

class UnionFind {
int[] parent;
int[] rank;

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

53
 int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}

boolean union(int x, int y) {

int rootX = find(x);
int rootY = find(y);

if (rootX == rootY) return false;

// Union by rank
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
}

// Usage
UnionFind uf = new UnionFind(n);
[Link](0, 1);
[Link](1, 2);
[Link]([Link](0) == [Link](2)); // true

Heap (PriorityQueue) Template

// Min-heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
[Link](5);

54
[Link](3);
[Link](7);
[Link]([Link]()); // 3

// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>([Link]());
[Link](5);
[Link](3);
[Link](7);
[Link]([Link]()); // 7

// Top K elements (min-heap of size k)

PriorityQueue<Integer> topK = new PriorityQueue<>();
for (int num : nums) {
[Link](num);
if ([Link]() > k) {
[Link]();
}
}

// Custom object heap

class Item {
int priority;
String value;
Item(int priority, String value) {
[Link] = priority;
[Link] = value;
}
}

PriorityQueue<Item> pq = new PriorityQueue<>((a, b) ->

[Link]([Link], [Link]));
[Link](new Item(5, "apple"));
[Link](new Item(3, "banana"));
Item top = [Link](); // priority 3

55
Graph Adjacency List Template

// Using ArrayList
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
[Link](new ArrayList<>());
}

// Add edge
[Link](0).add(1); // Edge from 0 to 1
[Link](1).add(0); // Undirected: add reverse edge

// Iterate neighbors
for (int neighbor : [Link](0)) {
[Link](neighbor);
}

// Using HashMap (for weighted graphs)

Map<Integer, ArrayList<int[]>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
[Link](i, new ArrayList<>());
}

// Add edge with weight

[Link](0).add(new int[]{1, 5}); // Edge to 1 with weight 5

// Iterate
for (int[] edge : [Link](0)) {
int neighbor = edge[0];
int weight = edge[1];
}

Sliding Window Template

// Fixed window size

int k = 3;
int[] arr = {1, 3, 2, 6, -1, 4, 1, 8};

56
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
int maxSum = windowSum;

for (int i = k; i < [Link]; i++) {

windowSum = windowSum - arr[i - k] + arr[i];
maxSum = [Link](maxSum, windowSum);
}

// Variable window
int left = 0, right = 0;
int sum = 0;
int target = 10;

while (right < [Link]) {

sum += arr[right];

while (sum > target && left <= right) {

sum -= arr[left];
left++;
}

// Process window [left, right]

right++;
}

Backtracking Template

void backtrack(List<Integer> current, int[] candidates, int target, int start, List<List<In
// Base case
if (target == 0) {
[Link](new ArrayList<>(current));
return;
}
if (target < 0) return;

57
 // Explore
for (int i = start; i < [Link]; i++) {
// Choose
[Link](candidates[i]);

// Recurse
backtrack(current, candidates, target - candidates[i], i, result);

// Unchoose
[Link]([Link]() - 1);
}
}

// Usage
List<List<Integer>> result = new ArrayList<>();
backtrack(new ArrayList<>(), new int[]{2, 3, 6}, 7, 0, result);

Segment Tree Template

class SegmentTree {
int[] tree;
int n;

SegmentTree(int[] arr) {
n = [Link];
tree = new int[4 * n];
build(arr, 0, 0, n - 1);
}

void build(int[] arr, int node, int start, int end) {

if (start == end) {
tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build(arr, 2 * node + 1, start, mid);
build(arr, 2 * node + 2, mid + 1, end);
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];

58
 }
}

int query(int node, int start, int end, int l, int r) {

if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];

int mid = (start + end) / 2;

return query(2 * node + 1, start, mid, l, r) +
query(2 * node + 2, mid + 1, end, l, r);
}

void update(int node, int start, int end, int idx, int val) {
if (start == end) {
tree[node] = val;
} else {
int mid = (start + end) / 2;
if (idx <= mid) {
update(2 * node + 1, start, mid, idx, val);
} else {
update(2 * node + 2, mid + 1, end, idx, val);
}
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
}

// Usage
int[] arr = {1, 2, 3, 4, 5};
SegmentTree st = new SegmentTree(arr);
[Link]([Link](0, 0, [Link] - 1, 1, 3)); // Sum of [1, 3]
[Link](0, 0, [Link] - 1, 2, 10);

Quick Reference: Collections Performance

59
Operation ArrayList LinkedList HashSet TreeSet HashMap TreeMap

get(i) O(1) O(n) ‑ ‑ ‑ ‑

add(E) O(1) O(1) O(1) avg O(log n) ‑ ‑
amortized
add(0, E) O(n) O(1) ‑ ‑ ‑ ‑
remove(E) O(n) O(n) O(1) avg O(log n) ‑ ‑
contains(E) O(n) O(n) O(1) avg O(log n) O(1) avg O(log n)
put/get ‑ ‑ ‑ ‑ O(1) avg O(log n)
sort O(n log n) O(n log n) ‑ auto ‑ auto

Common Data Structure Initialization Patterns

// Array
int[] arr = new int[n];
int[][] matrix = new int[rows][cols];

// 2D ArrayList
ArrayList<ArrayList<Integer>> grid = new ArrayList<>();
for (int i = 0; i < rows; i++) {
[Link](new ArrayList<>());
}

// HashMap with default value

Map<String, Integer> freq = new HashMap<>();
[Link](key, [Link](key, 0) + 1);

// HashMap with ArrayList value

Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
if () {
[Link](u, new ArrayList<>());
}
[Link](u).add(v);

// Sorted collection initialization

Set<Integer> sorted = new TreeSet<>(unsortedList);

60
// Priority queue with custom order
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

Final Checklist Before Submitting

1. Check for null pointers: All object accesses
2. Check for over low: Products, sums, indices
3. Check array bounds: Loop conditions, array access
4. Check string/array comparison: Use equals() and [Link]()
5. Check off‑by‑one errors: Substring, loop ranges, binary search
6. Check modulo with negatives: Add modulo value for positive result
7. Use long for large numbers: Especially intermediate calculations
8. Use StringBuilder for string concatenation: In loops
9. Pre‑size collections: If size is known
10. Close resources: Scanner, BufferedReader

Good luck with your DSA preparation and placements!

61