☕ Java for DSA

The Complete One-Day Beginner's Guide

Every Concept · Every Exception · Real-Time Scenarios · 15+ Pages
─────────────────────────────────────────────────────
Based on: Head First Java • Effective Java • Introduction to Algorithms (CLRS)
📋 Table of Contents

1. Java Basics — Data Types, Variables & Type Casting ...... Page 2
2. Operators & Expressions ...... Page 3
3. Control Flow — if/else, switch, loops ...... Page 3
4. Arrays (1D & 2D) ...... Page 4
5. Strings & StringBuilder ...... Page 5
6. Methods & Recursion ...... Page 6
7. Object-Oriented Programming (OOP) ...... Page 7
8. Exception Handling ...... Page 8
9. Generics ...... Page 9
10. Collections Framework — List, Stack, Queue, Deque ...... Page 9
11. HashMap, HashSet & TreeMap / TreeSet ...... Page 11
12. Sorting — [Link], Comparator, [Link] ...... Page 12
13. Searching — Linear & Binary Search ...... Page 13
14. Bit Manipulation ...... Page 13
15. Math Utility Methods ...... Page 14
16. Time & Space Complexity (Big-O) ...... Page 14
17. Common DSA Patterns Cheat-Sheet ...... Page 15
18. Recommended Books & Resources ...... Page 16
1. Java Basics — Data Types, Variables & Type Casting
Java is a statically-typed language — every variable must have a declared type before you use it. This
is the foundation of DSA in Java because choosing the wrong type can cause overflow, precision loss,
or runtime errors.

1.1 Primitive Data Types

Type Size Range DSA Use-Case
byte 1 byte -128 to 127 Pixel data, small arrays
short 2 bytes -32,768 to 32,767 Rarely used in DSA
int 4 bytes -2^31 to 2^31-1 Default for indices,
(~2 billion) counters, sums
long 8 bytes -2^63 to 2^63-1 Large sums, factorial, graph
weights
float 4 bytes ~6-7 decimal Avoid in DSA (use double)
digits
double 8 bytes ~15 decimal Geometric distances,
digits probabilities
char 2 bytes 0 to 65,535 String traversal, frequency
(Unicode) arrays
boolean 1 bit true / false Visited flags in BFS/DFS, DP
memos

1.2 Variables & Type Casting

int a = 5; // literal int
long big = 10_000_000_000L; // L suffix mandatory
double pi = 3.14159;
char ch = 'A'; // single quotes
boolean flag = true;

// IMPLICIT (widening) — safe, automatic

int x = 100; long y = x; // int → long automatically

// EXPLICIT (narrowing) — may lose data, needs cast

double d = 9.99; int i = (int) d; // i = 9 (truncated)

// Wrapper Classes (object form of primitives)

Integer n = 42; // auto-boxing
int raw = n; // auto-unboxing
String s = [Link](n);
int parsed = [Link]("123");

📍 Real-Time Scenario: Array index vs. large sum

Use int for array indices (fast, no overflow for n<=10^9).
Use long when summing up to 10^9 values of 10^9 each — int overflows!
Example: prefix[i] = prefix[i-1] + arr[i]; // use long[]

Exception Type Cause Example

NumberFormatException [Link]("abc") — bad parseInt("12a")
string
ArithmeticException int / 0 (divide by zero) 5 / 0
ClassCastException Bad explicit cast at runtime (String)
(Object)42
StackOverflowError Infinite recursion / deep call f() calls f()
stack
2. Operators & Expressions
Operators are the building blocks of logic inside every DSA problem. Understanding every operator
prevents subtle bugs.

// ARITHMETIC
int sum = 7 + 3; // 10
int rem = 7 % 3; // 1 ← modulo, critical for circular arrays/hashing
int div = 7 / 2; // 3 ← integer division (floors toward zero)
double exact = 7.0 / 2; // 3.5

// COMPARISON
a == b, a != b, a < b, a > b, a <= b, a >= b // returns boolean

// LOGICAL
&& (AND), || (OR), ! (NOT)
if (i >= 0 && i < n) // safe bounds check BEFORE arr[i]

// BITWISE (extremely useful in DSA!)

a & b // AND — check bit: if ((n & 1) == 0) → n is even
a | b // OR — set bit
a ^ b // XOR — find unique element trick
a << 1 // left shift = a * 2
a >> 1 // right shift = a / 2
~a // bitwise NOT

// TERNARY
int max = (a > b) ? a : b;

// COMPOUND ASSIGNMENT
a += b; a -= b; a *= b; a /= b; a %= b;

📝 Quick Notes
• In Java, % on negative numbers returns negative: -7 % 3 = -1. Use [Link](-7,3) = 2
for true modulo.
• Integer.MAX_VALUE = 2147483647. Adding 1 causes overflow → wraps to negative!
• Use (long)a * b to avoid overflow BEFORE multiplication.

3. Control Flow — if/else, switch, loops

3.1 if / else if / else

if (n == 0) {
[Link]("Zero");
} else if (n > 0) {
[Link]("Positive");
} else {
[Link]("Negative");
}
3.2 switch
switch (day) {
case 1: [Link]("Mon"); break;
case 2: [Link]("Tue"); break;
default: [Link]("Other");
}
// Java 14+ enhanced switch expression:
String name = switch(day) { case 1 -> "Mon"; default -> "?"; };

3.3 Loops — for, while, do-while, for-each

// Standard for — index-controlled (most common in DSA)
for (int i = 0; i < n; i++) { /* ... */ }

// Reverse traversal
for (int i = n-1; i >= 0; i--) { /* ... */ }

// Nested loops — O(n^2) — e.g. bubble sort, matrix fill

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

// while — unknown iterations (e.g. binary search manually)

int lo = 0, hi = n-1;
while (lo <= hi) { int mid = lo + (hi-lo)/2; /* ... */ }

// do-while — runs at least once

do { [Link](n--); } while (n > 0);

// for-each — cleaner iteration over collections

for (int val : arr) { sum += val; }

// break / continue
for (int i=0;i<n;i++) {
if (arr[i]==target) { found=i; break; } // exit loop
if (arr[i]<0) continue; // skip iteration
}

// LABELS — break out of outer loop

outer:
for (int i=0;i<n;i++) for (int j=0;j<m;j++) if (condition) break outer;

Exception Type Cause Example

ArrayIndexOutOfBoundsExce Loop index exceeds array length arr[n] in
ption for(i<=n)
NullPointerException Calling methods on null [Link]() if
variable str=null
StackOverflowError Infinite loop calling recursion while(true) +
recurse
4. Arrays (1D & 2D)
Arrays are contiguous memory blocks — O(1) access by index. They are the most fundamental data
structure in DSA.

4.1 1D Arrays — Declaration, Init & Operations

// Declaration and initialization
int[] arr = new int[5]; // default: all zeros
int[] arr2 = {10, 20, 30}; // literal
int[] arr3 = new int[]{5,6,7};

// Access & modify

arr[0] = 100;
int val = arr[0];
int len = [Link]; // NOT [Link]()

// Common patterns in DSA

// 1. Prefix sum array
int[] prefix = new int[n+1];
for (int i=0;i<n;i++) prefix[i+1] = prefix[i] + arr[i];
// Range sum [l,r]: prefix[r+1] - prefix[l]

// 2. Frequency array (chars a-z)

int[] freq = new int[26];
for (char c : [Link]()) freq[c-'a']++;

// 3. Sorting
[Link](arr); // O(n log n) - dual pivot quicksort

// 4. Copy
int[] copy = [Link](arr, [Link]);
int[] slice = [Link](arr, 2, 5); // [2,5)

// 5. Fill
[Link](arr, -1);

// 6. Binary search (must be sorted first!)

int idx = [Link](arr, target); // -ve = not found

4.2 2D Arrays (Matrix)

int[][] mat = new int[3][4]; // 3 rows, 4 cols
int[][] mat2 = {{1,2},{3,4},{5,6}}; // literal

// Row length
int rows = [Link];
int cols = mat[0].length;

// Traverse
for (int i=0;i<rows;i++)
for (int j=0;j<cols;j++)
[Link](mat[i][j]+" ");

// Diagonal check (square matrix)

 if (i == j) // main diagonal
if (i+j == n-1) // anti-diagonal

// Jagged (irregular) arrays

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

📍 Real-Time Scenario: Rotate Matrix 90° (Google Interview Classic)

Step 1: Transpose matrix → swap mat[i][j] with mat[j][i]
Step 2: Reverse each row → use two-pointer swap left↔right
Both steps use 2D array indexing mastered above.

Exception Type Cause Example

ArrayIndexOutOfBoundsExce Accessing index >= length arr[5] on
ption int[5]
NegativeArraySizeExceptio new int[-1] n computed as -
n 1
NullPointerException int[][] mat; mat[0][0] = 1; mat not
initialized
OutOfMemoryError new int[10_000][10_000] 100M ints on
heap
5. Strings & StringBuilder
Strings are immutable objects in Java. Every modification creates a new object — use StringBuilder
when you need mutable/efficient string building in DSA.

5.1 String Methods (Must-Know)

String s = "Hello World";

[Link]() // 11
[Link](0) // 'H'
[Link]('o') // 4
[Link]('o') // 7
[Link](6) // "World"
[Link](0, 5) // "Hello" [start, end)
[Link]() // "hello world"
[Link]() // "HELLO WORLD"
[Link]() // remove leading/trailing spaces
[Link]('l','r') // "Herro Worrd"
[Link]("World") // true
[Link]("He") // true
[Link]("ld") // true
[Link]("Hello World") // true ← always use equals(), not ==
[Link]("hello world") // true
[Link](" ") // ["Hello", "World"]
[Link]() // char array for iteration
[Link](42) // "42"
[Link]("-","a","b") // "a-b"
[Link]() // false
[Link]() // false (Java 11+)
[Link]() // IntStream of char values
[Link]("Hi") // lexicographic compare (<0,0,>0)

5.2 StringBuilder (Use for Mutable Strings)

StringBuilder sb = new StringBuilder();
[Link]('H');
[Link]("ello");
[Link](0, "Say: ");
[Link](0, 5);
[Link](); // very useful in palindrome problems
[Link](i);
[Link](i, 'X');
[Link]();
[Link](); // convert back to String

// Why StringBuilder?
// String s=""; for(int i=0;i<n;i++) s+=arr[i]; → O(n^2) BAD
// Use StringBuilder → O(n) GOOD

📍 Real-Time Scenario: Check if a String is Palindrome

char[] ch = [Link]();
int l=0, r=[Link]-1;
while(l<r) { if(ch[l]!=ch[r]) return false; l++; r--; }
return true; // Also: [Link](new StringBuilder(s).reverse().toString())

Exception Type Cause Example

StringIndexOutOfBoundsExc charAt(i) where i >= length [Link](11) on
eption "Hello"
NullPointerException [Link]() or [Link]() String s=null;
[Link]()
NumberFormatException [Link](invalid parseInt("12.3"
string) )
6. Methods & Recursion

6.1 Method Anatomy

// accessModifier returnType methodName(params) { body }
public static int add(int a, int b) {
return a + b;
}

// void method
public static void printArr(int[] arr) {
for (int x : arr) [Link](x + " ");
[Link]();
}

// Variable arguments (varargs)

public static int sum(int... nums) {
int total = 0;
for (int n : nums) total += n;
return total;
}
sum(1,2,3,4,5); // 15

6.2 Recursion — The Heart of DSA

Recursion = A method that calls itself. Every recursive solution needs: (1) Base case (stops the
recursion) and (2) Recursive case (reduces the problem).

// Factorial — O(n) time, O(n) stack space

public static long factorial(int n) {
if (n <= 1) return 1; // BASE CASE
return n * factorial(n-1); // RECURSIVE CASE
}

// Fibonacci — O(2^n) naive, O(n) with memoization

public static int fib(int n, int[] memo) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n]; // return cached
memo[n] = fib(n-1, memo) + fib(n-2, memo);
return memo[n];
}

// Binary Search — Recursive

public static int binarySearch(int[] arr, int lo, int hi, int t) {
if (lo > hi) return -1;
int mid = lo + (hi-lo)/2;
if (arr[mid] == t) return mid;
if (arr[mid] < t) return binarySearch(arr, mid+1, hi, t);
return binarySearch(arr, lo, mid-1, t);
}

📍 Real-Time Scenario: Subsets / Power Set (Backtracking)

public static void subsets(int[] arr, int i, List<Integer> curr) {
if (i == [Link]) { print(curr); return; }
 [Link](arr[i]); subsets(arr, i+1, curr); // include
[Link]([Link]()-1); // backtrack
subsets(arr, i+1, curr); // exclude
}

Exception Type Cause Example

StackOverflowError No base case or base case never factorial(-1)
reached
OutOfMemoryError Memoization array too large int[[Link]
_VALUE]
7. Object-Oriented Programming (OOP)
OOP is essential for implementing custom data structures (Node, Graph, Trie) in DSA interviews.

7.1 Classes & Objects

class Node { // Linked List node
int val;
Node next;
Node(int val) { [Link] = val; [Link] = null; }
}

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

7.2 Interfaces — Comparable & Comparator

// Comparable — natural ordering (inside the class)
class Student implements Comparable<Student> {
int marks;
Student(int m) { marks=m; }
@Override
public int compareTo(Student o) { return [Link] - [Link]; }
}
// [Link](students) → sorts by marks ascending

// Comparator — external custom order (lambda preferred)

[Link](arr, (a,b) -> b-a); // descending
[Link](strings, (a,b)->[Link]()-[Link]()); // by length

// Priority Queue with custom Comparator

PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[1]-b[1]);
// sorts int[] by second element — used in Dijkstra's algorithm

7.3 Inheritance & Polymorphism

class Shape { public double area() { return 0; } }

class Circle extends Shape {

double r;
Circle(double r) { this.r=r; }
@Override public double area() { return [Link]*r*r; }
}

// Polymorphism
Shape s = new Circle(5);
[Link]([Link]()); // calls Circle's area()

Exception Type Cause Example

NullPointerException Accessing field of null object [Link] when
node=null
ClassCastException Wrong downcast (Circle)(new
Shape())
AbstractMethodError Interface not fully implemented class missing
override
IllegalArgumentException Constructor receives invalid new Node(-999)
value if not guarded
8. Exception Handling
Proper exception handling prevents crashes in competitive coding when edge cases hit unexpected
input.

// try-catch-finally
try {
int result = [Link](input);
[Link](10 / result);
} catch (NumberFormatException e) {
[Link]("Not a number!");
} catch (ArithmeticException e) {
[Link]("Divide by zero!");
} finally {
[Link]("Always runs — cleanup here");
}

// Multi-catch (Java 7+)

catch (NumberFormatException | ArithmeticException e) { ... }

// throws — declare checked exceptions

public static void readFile(String path) throws IOException { ... }

// throw — manually throw

if (n < 0) throw new IllegalArgumentException("n must be >= 0");

// Custom Exception
class GraphException extends RuntimeException {
GraphException(String msg) { super(msg); }
}

Complete Exception Hierarchy for DSA

Throwable
├── Error (JVM errors — don't catch these)
│ ├── StackOverflowError → deep recursion
│ └── OutOfMemoryError → huge arrays / memory leak
└── Exception
├── RuntimeException (unchecked — compiler won't warn you)
│ ├── NullPointerException → null dereference
│ ├── ArrayIndexOutOfBoundsException → bad index
│ ├── StringIndexOutOfBoundsException → bad char idx
│ ├── ClassCastException → wrong cast
│ ├── ArithmeticException → /0
│ ├── NumberFormatException → parseInt fails
│ ├── IllegalArgumentException → bad method arg
│ ├── IllegalStateException → wrong object state
│ ├── UnsupportedOperationException → e.g. unmodifiable list
│ ├── ConcurrentModificationException → modifying while iterating
│ └── EmptyStackException → pop from empty Stack
└── Checked Exceptions (must handle or declare)
├── IOException → file/stream errors
└── SQLException → database errors
9. Generics
Generics allow you to write type-safe, reusable code. All Java Collections use generics — essential for
DSA.

// Generic method
public static <T> void swap(T[] arr, int i, int j) {
T temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}

// Generic class — custom Pair (very useful in DSA)

class Pair<A, B> {
A first; B second;
Pair(A a, B b) { first=a; second=b; }
@Override
public String toString() { return "("+first+","+second+")"; }
}
Pair<Integer,String> p = new Pair<>(1, "one");

// Bounded generics
public static <T extends Comparable<T>> T max(T a, T b) {
return [Link](b) >= 0 ? a : b;
}
max(3,7) // 7
max("apple","mango") // "mango"
10. Collections Framework — List, Stack, Queue, Deque
The Java Collections Framework is your toolbox for DSA. Choosing the right data structure often
determines whether your solution is O(n) or O(n²).

10.1 ArrayList (Dynamic Array)

ArrayList<Integer> list = new ArrayList<>();
[Link](10); // append: O(1) amortized
[Link](0, 5); // insert at index: O(n)
[Link](0); // access: O(1)
[Link](0, 99); // update: O(1)
[Link](0); // remove by index: O(n)
[Link]([Link](10)); // remove by value: O(n)
[Link]();
[Link]();
[Link](10);
[Link](10);
[Link](list); // O(n log n)
[Link](list);
[Link](list);
[Link](list);
[Link](1, 4); // view [1,4) — do NOT store long-term

10.2 LinkedList (as Deque / Queue)

LinkedList<Integer> ll = new LinkedList<>();
[Link](1); [Link](2);
[Link](); [Link]();
[Link](); [Link]();
// Use as Queue (FIFO):
Queue<Integer> q = new LinkedList<>();
[Link](10); // enqueue (use offer not add — no exception)
[Link](); // dequeue: removes & returns head, null if empty
[Link](); // view head without removing

10.3 Stack (LIFO)

// Legacy Stack class
Stack<Integer> st = new Stack<>();
[Link](1); [Link](2); [Link](3);
[Link](); // 3 — removes top
[Link](); // 2 — views top
[Link](); [Link]();

// PREFERRED: Deque as Stack (faster)

Deque<Integer> stack = new ArrayDeque<>();
[Link](1); // = addFirst
[Link](); // = removeFirst
[Link](); // = peekFirst

📍 Real-Time Scenario: Valid Parentheses — Stack Classic (LeetCode #20)

 Deque<Character> st = new ArrayDeque<>();
for (char c : [Link]()) {
if (c=='('||c=='['||c=='{') [Link](c);
else if ([Link]()) return false;
else if (c==')' && [Link]()!='(') return false;
else [Link]();
}
return [Link]();

10.4 PriorityQueue (Min-Heap by default)

PriorityQueue<Integer> minPQ = new PriorityQueue<>();
PriorityQueue<Integer> maxPQ = new PriorityQueue<>([Link]());

[Link](5); [Link](1); [Link](3);

[Link](); // returns 1 (smallest)
[Link](); // returns 3 (next smallest)

// Dijkstra / Prim: store [node, dist] pairs

PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[1]-b[1]);
[Link](new int[]{node, dist});
int[] curr = [Link]();

10.5 ArrayDeque (Sliding Window / Monotonic Queue)

Deque<Integer> dq = new ArrayDeque<>();
// Add
[Link](x); [Link](x);
// Remove
[Link](); [Link]();
// Peek
[Link](); [Link]();

// PATTERN: Sliding window maximum (Monotonic Deque)

// Keep indices of candidates in decreasing order of arr values
for (int i=0;i<n;i++) {
while(![Link]()&&arr[[Link]()]<=arr[i]) [Link]();
[Link](i);
if([Link]()<i-k+1) [Link](); // out of window
if(i>=k-1) result[i-k+1] = arr[[Link]()];
}

Exception Type Cause Example

NoSuchElementException remove()/element() on empty [Link]()
collection empty
ConcurrentModificationExc Modifying list while for-each [Link]
eption runs inside for-each
EmptyStackException [Link]() when stack is empty [Link]() empty
Stack
ClassCastException Adding wrong type to raw raw List
collection add/get
UnsupportedOperationExcep [Link]() → cannot asList().add(x)
tion add/remove
11. HashMap, HashSet, TreeMap & TreeSet

11.1 HashMap — O(1) average get/put

HashMap<String, Integer> map = new HashMap<>();
[Link]("apple", 3);
[Link]("apple"); // 3
[Link]("mango", 0); // 0 (not found → default)
[Link]("apple"); // true
[Link](3); // true
[Link]("apple");
[Link](); [Link]();
[Link]("banana", 1);
[Link]("apple", 1, Integer::sum); // increment frequency

// Iterate
for ([Link]<String,Integer> e : [Link]())
[Link]([Link]() + " → " + [Link]());

// Frequency pattern (most common in DSA)

for (int n : arr) [Link](n, 1, Integer::sum);
// OR
for (int n : arr) [Link](n, [Link](n,0)+1);

11.2 HashSet — O(1) contains, no duplicates

HashSet<Integer> set = new HashSet<>();
[Link](5); [Link](3); [Link](5); // {3,5} — no duplicate
[Link](5); // true
[Link](3);
[Link]();

// Two-sum pattern
Set<Integer> seen = new HashSet<>();
for (int n : arr) {
if ([Link](target - n)) return true;
[Link](n);
}

11.3 TreeMap & TreeSet — Sorted, O(log n)

TreeMap<Integer,String> tm = new TreeMap<>();
[Link](3,"c"); [Link](1,"a"); [Link](2,"b");
[Link](); // 1 (smallest)
[Link](); // 3 (largest)
[Link](2); // 2 (≤ 2)
[Link](2); // 2 (≥ 2)
[Link](2); // 1 (< 2)
[Link](2); // 3 (> 2)

TreeSet<Integer> ts = new TreeSet<>();

[Link](5); [Link](2); [Link](8);
[Link](6); // 5 ← used in: find next smaller element
[Link](6);// 8 ← used in: find next greater element
📍 Real-Time Scenario: Longest Consecutive Sequence — O(n) with HashSet
Set<Integer> set = new HashSet<>([Link](arr));
int best = 0;
for (int n : set) {
if () { // start of sequence
int len=1; while([Link](n+len)) len++;
best = [Link](best, len);
}
}
return best;

Exception Type Cause Example

ConcurrentModificationExc Modifying map/set while [Link] in
eption iterating for-each
NullPointerException TreeMap/TreeSet does not allow [Link](null,"x"
null key )
ClassCastException Storing non-Comparable in TreeSet of
TreeSet custom class
12. Sorting — [Link], Comparator & Custom Sort
// Primitive arrays — dual pivot quicksort O(n log n)
int[] arr = {5,2,8,1};
[Link](arr); // ascending

// Sort range only

[Link](arr, 2, 5); // sorts [2,5)

// Object arrays with Comparator — descending

Integer[] arr2 = {5,2,8,1};
[Link](arr2, (a,b) -> b-a); // descending
[Link](arr2, [Link]());

// Sort 2D array by column

int[][] intervals = {{1,3},{2,4},{0,2}};
[Link](intervals, (a,b) -> a[0]-b[0]); // by start time

// Sort by multiple keys

[Link](people, (a,b) -> [Link]!=[Link] ? [Link] : [Link]([Link]));

// [Link] for List

List<Integer> list = [Link](5,2,8,1);
[Link](list);
[Link]((a,b)->b-a); // lambda on list

Sorting Algorithm Complexity Table

[Link] (primitives) → Dual-Pivot QuickSort → O(n log n) avg — NOT stable
[Link] (objects) → TimSort → O(n log n) worst — STABLE
[Link] → TimSort → O(n log n) worst — STABLE
Bubble Sort (manual impl) → O(n^2) — only use to learn, never in interviews
Selection Sort (manual) → O(n^2) — same as above
Insertion Sort (manual) → O(n^2) worst, O(n) best — good for nearly sorted
Merge Sort (manual) → O(n log n) — stable, good for Linked Lists
Counting Sort → O(n+k) — perfect for small-range integers (0..k)
13. Searching — Linear & Binary Search

13.1 Linear Search — O(n)

public static int linearSearch(int[] arr, int target) {
for (int i=0;i<[Link];i++)
if (arr[i]==target) return i;
return -1;
}

13.2 Binary Search — O(log n) — MUST on sorted array

// Iterative (preferred — no stack overhead)
public static int binarySearch(int[] arr, int target) {
int lo=0, hi=[Link]-1;
while (lo<=hi) {
int mid = lo + (hi-lo)/2; // avoids overflow vs (lo+hi)/2
if (arr[mid]==target) return mid;
else if (arr[mid]<target) lo=mid+1;
else hi=mid-1;
}
return -1;
}

// Find leftmost index (lower bound)

public static int lowerBound(int[] arr, int target) {
int lo=0, hi=[Link];
while(lo<hi) { int mid=(lo+hi)/2; if(arr[mid]<target) lo=mid+1; else hi=mid; }
return lo;
}

// Binary search on ANSWER (search space, not array)

// e.g. 'find minimum capacity such that ship finishes in D days'
int lo=maxWeight, hi=totalWeight;
while(lo<hi) {
int mid=(lo+hi)/2;
if(canFinish(weights,mid,D)) hi=mid;
else lo=mid+1;
}
// answer is lo
14. Bit Manipulation — Essential Tricks
// Check if even: (n & 1) == 0
// Check if odd: (n & 1) == 1
// Multiply by 2: n << 1
// Divide by 2: n >> 1
// Check bit at pos i: (n >> i) & 1
// Set bit at pos i: n | (1 << i)
// Clear bit at pos i: n & ~(1 << i)
// Toggle bit at pos i: n ^ (1 << i)
// Remove last set bit: n & (n-1) ← count set bits with this
// Isolate last set bit:n & (-n)
// Is power of 2: n>0 && (n&(n-1))==0
// XOR trick — find single number:
int result=0; for(int n:arr) result^=n; // all pairs cancel, unique remains

// Count set bits (Brian Kernighan)

int count=0;
while(n!=0) { n &= (n-1); count++; }

// Swap without temp

a ^= b; b ^= a; a ^= b;

📍 Real-Time Scenario: Subsets using Bitmask — enumerate all 2^n subsets

for (int mask=0; mask<(1<<n); mask++) {
for (int i=0; i<n; i++)
if ((mask>>i & 1)==1) [Link](arr[i]+" ");
[Link]();
}
// Used in: DP on subsets (Travelling Salesman, min cost problems)
15. Math Utility Methods
[Link](-5) // 5
[Link](3, 7) // 7
[Link](3, 7) // 3
[Link](2, 10) // 1024.0 → cast to int if needed
[Link](144) // 12.0
[Link](Math.E) // 1.0 (natural log)
Math.log10(100) // 2.0
[Link](3.9) // 3.0
[Link](3.1) // 4.0
[Link](3.5) // 4
[Link] // 3.14159...
[Link]() // [0.0, 1.0)
[Link](-7, 3) // 2 (true modulo, never negative)

// GCD (recursive Euclidean)

static int gcd(int a, int b) { return b==0 ? a : gcd(b, a%b); }
// LCM
static long lcm(long a, long b) { return a / gcd((int)a,(int)b) * b; }

// Integer limits — useful for initializing min/max

Integer.MAX_VALUE // 2147483647
Integer.MIN_VALUE // -2147483648
Long.MAX_VALUE // 9223372036854775807
16. Time & Space Complexity (Big-O)
Notation Name Example n=10^6 ops/sec
O(1) Constant Array access Instant
O(log n) Logarithmic Binary search ~20 ops
O(n) Linear Linear scan 1 million ops
O(n log n) Linearithmic Merge sort ~20M ops
O(n²) Quadratic Bubble sort 10^12 — TLE!
O(2ⁿ) Exponential Subsets Way too slow >n=30
O(n!) Factorial Permutations Impossible >n=12

Rules of Thumb for Competitive Coding

• n ≤ 10 → O(n!) is fine (backtracking, all permutations)
• n ≤ 25 → O(2^n) is fine (bitmask DP, subsets)
• n ≤ 500 → O(n^3) might pass
• n ≤ 10,000 → O(n^2) usually passes (3 sec TL)
• n ≤ 10^6 → Need O(n log n) or better
• n ≤ 10^8 → Must be O(n) or O(log n)
• Space: 256 MB limit ≈ 64 million ints (int = 4 bytes)
17. Common DSA Patterns Cheat-Sheet
Pattern Java Tool Classic Problem
Two Pointers int l=0,r=n-1 Two-sum sorted, Container
With Most Water
Sliding Window int l=0; for r... Longest substring without
repeat, Max sum subarray
Prefix Sum int[] prefix Range sum queries, Subarray
sum = k
Hash Frequency HashMap + merge() Group anagrams, Top-k
frequent elements
Stack (Monotonic) Deque<Integer> Next Greater Element, Largest
Rectangle in Histogram
BFS (Level-order) Queue<Integer> Shortest path unweighted,
Binary tree BFS
DFS (Backtracking) Recursion + Permutations, N-Queens, Word
visited[] Search
Binary Search lo + (hi-lo)/2 Search rotated array, Kth
smallest element
Priority Queue PriorityQueue<int[]> Dijkstra, K closest points,
Merge K sorted lists
Union-Find int[] parent, rank Number of islands
(optimized), Kruskal MST
DP — 1D int[] dp Climbing stairs, House
robber, Coin change
DP — 2D int[][] dp Longest Common Subsequence,
Edit distance
Trie TrieNode class Word search II, Auto-complete
Segment Tree int[] tree (array) Range min/max/sum queries
with updates

17.1 Quick Template — BFS

Queue<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[n];
[Link](start); visited[start] = true;
while (![Link]()) {
int node = [Link]();
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
[Link](neighbor);
}
}
}
17.2 Quick Template — DFS
boolean[] visited = new boolean[n];
void dfs(int node) {
visited[node] = true;
for (int neighbor : graph[node])
if (!visited[neighbor]) dfs(neighbor);
}

17.3 Quick Template — Union-Find

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

int find(int x) { return parent[x]==x ? x : (parent[x]=find(parent[x])); }

void union(int a, int b) {

int pa=find(a), pb=find(b);
if(pa==pb) return;
if(rank[pa]<rank[pb]) parent[pa]=pb;
else if(rank[pa]>rank[pb]) parent[pb]=pa;
else { parent[pb]=pa; rank[pa]++; }
}
18. Recommended Books & Resources

📚 Java Language Books

• Head First Java (3rd Ed.) — Kathy Sierra & Bert Bates → Best visual beginner book. Teaches
OOP, collections, exceptions with fun examples.
• Effective Java (3rd Ed.) — Joshua Bloch → Industry bible. Learn best practices: generics,
collections, lambdas. Read after basics.
• Java: The Complete Reference — Herbert Schildt → Encyclopedia-style. Best for looking up
any Java API or syntax detail.
• Core Java Vol I & II — Cay Horstmann → University-level comprehensive. Deep dive into
collections, concurrency, streams.

📚 DSA Books
• Introduction to Algorithms (CLRS) — Cormen, Leiserson, Rivest, Stein → The gold standard for
algorithm theory. Pseudocode that maps cleanly to Java.
• Algorithms (4th Ed.) — Sedgewick & Wayne → All code in Java! Perfect companion to this
guide. Free on [Link]
• Data Structures and Algorithms in Java — Goodrich, Tamassia & Goldwasser → University
textbook with Java implementations throughout.
• Grokking Algorithms — Aditya Bhargava → Visual, beginner-friendly. Great for understanding
Big-O and core algorithms intuitively.

Practice Platforms
• LeetCode ([Link]) — #1 for interview prep. Start with NeetCode 150 roadmap.
• GeeksForGeeks ([Link]) — Best explanations with Java code for every DSA topic.
• Codeforces / AtCoder — Competitive programming. Train speed and edge-case thinking.
• Visualgo ([Link]) — Animate sorting, graphs, DP — see algorithms run step by step.
• CS50 / MIT OpenCourseWare — Free university-level courses covering algorithms deeply.

Recommended Learning Roadmap (1 Day → 1 Month)

1. Day 1: Sections 1-5 of this guide (types, loops, arrays, strings) + LeetCode Easy arrays
2. Week 1: Recursion, OOP, Collections (ArrayList, HashMap, Stack, Queue)
3. Week 2: Sorting, Binary Search, Two-pointer, Sliding Window (30 LeetCode Mediums)
4. Week 3: Graphs (BFS/DFS), Trees, Priority Queue, Union-Find
5. Week 4: Dynamic Programming 1D & 2D, Tries, Segment Trees

All the best on your DSA journey! 🚀 Consistency beats talent — code every single day.