DSA in Java — Complete Study Guide

DSA IN JAVA
Complete Study Guide
Beginner to Advanced

Covering All Major Topics | Interview Ready | College Exam Prep

Data Structures | Algorithms | Problem Solving Patterns

© 2025 | For Students & Professionals

Page 1 of 45
DSA in Java — Complete Study Guide

Table of Contents
Table of Contents ............................................................................................................................ 2
1. Java Basics for DSA .................................................................................................................... 5
1.1 Variables & Data Types .......................................................................................................... 5
Primitive Data Types ................................................................................................................. 5
1.2 Operators ............................................................................................................................... 5
1.3 Input / Output.......................................................................................................................... 6
1.4 Arrays in Java......................................................................................................................... 6
1.5 Java Collections Framework................................................................................................... 6
Interview Questions — Java Basics.............................................................................................. 7
2. Arrays .......................................................................................................................................... 8
2.1 Definition ................................................................................................................................ 8
2.2 Key Operations & Complexity ................................................................................................. 8
2.3 Prefix Sum .............................................................................................................................. 8
2.4 Sliding Window ....................................................................................................................... 8
2.5 Kadane's Algorithm (Maximum Subarray Sum) ...................................................................... 9
2.6 Two Pointer Technique ........................................................................................................... 9
Real-World Use Cases ............................................................................................................... 10
Common Interview Questions..................................................................................................... 10
3. Strings ....................................................................................................................................... 11
3.1 Definition .............................................................................................................................. 11
3.2 Key String Methods .............................................................................................................. 11
3.3 StringBuilder (Mutable Strings) ............................................................................................. 11
3.4 Anagram Check.................................................................................................................... 12
3.5 KMP Algorithm (Pattern Matching) ....................................................................................... 12
String Complexity Summary ....................................................................................................... 13
Common Interview Questions..................................................................................................... 13
4. Linked List.................................................................................................................................. 14
4.1 Definition .............................................................................................................................. 14
4.2 Node Implementation ........................................................................................................... 14
4.3 Basic Operations .................................................................................................................. 14
4.4 Reverse a Linked List ........................................................................................................... 15
4.5 Detect Loop — Floyd's Algorithm ......................................................................................... 15
4.6 Merge Two Sorted Lists ........................................................................................................ 16
Complexity Summary ................................................................................................................. 16

Page 2 of 45
DSA in Java — Complete Study Guide

Common Interview Questions..................................................................................................... 16

5. Stack & Queue ........................................................................................................................... 17
5.1 Stack — Definition ................................................................................................................ 17
5.2 Balanced Parentheses ......................................................................................................... 17
5.3 Next Greater Element (Monotonic Stack) ............................................................................. 17
5.4 Queue — Definition .............................................................................................................. 18
5.5 Priority Queue (Heap-based) ................................................................................................ 18
Complexity Summary ................................................................................................................. 18
Common Interview Questions..................................................................................................... 19
6. Hashing ..................................................................................................................................... 20
6.1 Definition .............................................................................................................................. 20
6.2 HashMap Operations............................................................................................................ 20
6.3 Two Sum using HashMap..................................................................................................... 20
6.4 HashSet Usage .................................................................................................................... 21
Complexity ................................................................................................................................. 21
Common Interview Questions..................................................................................................... 21
7. Recursion & Backtracking .......................................................................................................... 22
7.1 Recursion — Definition ......................................................................................................... 22
7.2 Backtracking ......................................................................................................................... 22
7.3 N-Queens Problem ............................................................................................................... 23
Common Interview Questions..................................................................................................... 23
8. Trees & Binary Search Trees ..................................................................................................... 24
8.1 Binary Tree ........................................................................................................................... 24
8.2 Tree Traversals .................................................................................................................... 24
8.3 Binary Search Tree (BST) .................................................................................................... 25
8.4 Lowest Common Ancestor (LCA) ......................................................................................... 25
Complexity Summary ................................................................................................................. 26
Common Interview Questions..................................................................................................... 26
9. Heap .......................................................................................................................................... 27
9.1 Definition .............................................................................................................................. 27
9.2 Top K Elements .................................................................................................................... 27
9.3 Heap Sort ............................................................................................................................. 27
Common Interview Questions..................................................................................................... 28
10. Graphs ..................................................................................................................................... 29
10.1 Definition ............................................................................................................................ 29
10.2 Graph Representation ........................................................................................................ 29

Page 3 of 45
DSA in Java — Complete Study Guide

10.3 BFS (Breadth-First Search) ................................................................................................ 29

10.4 DFS (Depth-First Search) ................................................................................................... 29
10.5 Dijkstra's Shortest Path ...................................................................................................... 30
10.6 Union-Find (Disjoint Set Union) .......................................................................................... 30
Graph Algorithm Complexity ....................................................................................................... 31
Common Interview Questions..................................................................................................... 31
11. Sorting & Searching Algorithms ............................................................................................... 32
11.1 Sorting Algorithms Overview .............................................................................................. 32
11.2 Merge Sort.......................................................................................................................... 32
11.3 Quick Sort .......................................................................................................................... 32
11.4 Binary Search ..................................................................................................................... 33
Common Interview Questions..................................................................................................... 33
12. Dynamic Programming............................................................................................................. 35
12.1 Definition ............................................................................................................................ 35
12.2 Two Approaches ................................................................................................................ 35
12.3 0/1 Knapsack...................................................................................................................... 35
12.4 Longest Common Subsequence (LCS) .............................................................................. 36
12.5 Longest Increasing Subsequence (LIS) .............................................................................. 36
Common DP Interview Questions ............................................................................................... 36
13. Bit Manipulation ....................................................................................................................... 38
13.1 Bitwise Operators Cheat Sheet........................................................................................... 38
Common Interview Questions..................................................................................................... 38
14. Greedy Algorithms & Mathematical Algorithms ........................................................................ 40
14.1 Greedy Algorithms .............................................................................................................. 40
14.2 Mathematical Algorithms .................................................................................................... 40
15. Advanced DSA Topics ............................................................................................................. 42
15.1 Trie (Prefix Tree) ................................................................................................................ 42
15.2 Segment Tree..................................................................................................................... 42
16. 30-Day DSA Roadmap............................................................................................................. 44
Best Practice Platforms .............................................................................................................. 44
Top Interview Preparation Tips ................................................................................................... 44
Must-Know DSA Problems (Top 25) ........................................................................................... 44
Mini Projects Using DSA in Java ................................................................................................ 45

Page 4 of 45
DSA in Java — Complete Study Guide

1. Java Basics for DSA

Before diving into Data Structures and Algorithms, it is essential to have a solid foundation
in Java. This section covers the core concepts you need to write efficient DSA solutions.

1.1 Variables & Data Types

A variable is a container that stores data values. Java is statically typed, meaning every
variable must be declared with a data type.

Primitive Data Types

// Integer types
byte b = 127; // 1 byte | -128 to 127
short s = 32767; // 2 bytes | -32,768 to 32,767
int n = 2147483647; // 4 bytes | ~-2.1B to 2.1B (most common)
long l = 9876543210L; // 8 bytes | very large numbers

// Floating point
float f = 3.14f; // 4 bytes | ~7 decimal digits
double d = 3.141592653589; // 8 bytes | ~15 decimal digits

// Other
char c = 'A'; // 2 bytes | Unicode character
boolean flag = true; // 1 bit | true or false

In DSA, int is used most frequently. Use long when values exceed 2 billion (e.g.,
NOTE
Fibonacci, large factorials).

1.2 Operators
Java provides arithmetic, relational, logical, bitwise, and assignment operators used
extensively in algorithms.
// Arithmetic: + - * / %
int sum = 10 + 3; // 13
int rem = 10 % 3; // 1 (modulo — very useful in DSA!)

// Relational: == != > < >= <=

boolean eq = (5 == 5); // true

// Logical: && || !
boolean result = (x > 0 && x < 10);

// Bitwise: & | ^ ~ << >> >>>

int and = 5 & 3; // 1 (0101 & 0011 = 0001)
int xor = 5 ^ 3; // 6 (0101 ^ 0011 = 0110)
int lsh = 1 << 3; // 8 (left shift = multiply by 2^3)

Page 5 of 45
DSA in Java — Complete Study Guide

int rsh = 8 >> 1; // 4 (right shift = divide by 2)

1.3 Input / Output

import [Link];

public class IODemo {

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

int n = [Link](); // read integer

long l = [Link](); // read long
double d = [Link](); // read double
String str = [Link](); // read token (no spaces)
String line= [Link](); // read full line

[Link]("Value: " + n); // print with newline

[Link]("Pi = %.2f%n", d); // formatted output
[Link]();
}
}

For competitive programming, use BufferedReader for faster I/O: BufferedReader br =

TIP
new BufferedReader(new InputStreamReader([Link]));

1.4 Arrays in Java

// 1D Array declaration and initialization
int[] arr = new int[5]; // default 0
int[] arr2 = {10, 20, 30, 40, 50}; // direct init

// 2D Array
int[][] matrix = new int[3][3];
int[][] grid = {{1,2,3},{4,5,6},{7,8,9}};

// Useful Array utilities

import [Link];
[Link](arr); // O(n log n)
[Link](arr, 0); // fill all with 0
int idx = [Link](arr, 30); // O(log n)
int[] copy = [Link](arr, [Link]);

1.5 Java Collections Framework

The Collections Framework provides ready-made data structures. Understanding these is
critical for DSA problem solving.

Page 6 of 45
DSA in Java — Complete Study Guide

import [Link].*;

// ArrayList — dynamic array

List<Integer> list = new ArrayList<>();
[Link](10); [Link](20); [Link](0);

// LinkedList — doubly linked list + deque

LinkedList<Integer> ll = new LinkedList<>();
[Link](1); [Link](2); [Link]();

// Stack
Deque<Integer> stack = new ArrayDeque<>();
[Link](5); int top = [Link](); [Link]();

// Queue
Queue<Integer> q = new LinkedList<>();
[Link](1); int front = [Link](); [Link]();

// PriorityQueue (Min Heap by default)

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

// HashMap
Map<String, Integer> map = new HashMap<>();
[Link]("a", 1); [Link]("a"); [Link]("a");

// HashSet
Set<Integer> set = new HashSet<>();
[Link](5); [Link](5); [Link](5);

Interview Questions — Java Basics

1. What is the difference between int and Integer in Java?
2. Why is String immutable in Java?
3. Explain the difference between ArrayList and LinkedList.
4. What is autoboxing and unboxing?
5. How does HashMap work internally?

Java uses pass-by-value. Primitives are copied; object references are copied (but point
REMEMBER
to the same object). This matters in recursive DSA problems.

Page 7 of 45
DSA in Java — Complete Study Guide

2. Arrays

2.1 Definition
An array is a contiguous block of memory that stores a fixed-size collection of elements of
the same data type. Arrays provide O(1) random access using an index.

2.2 Key Operations & Complexity

Operation Time Complexity Space Complexity
Access by index O(1) O(1)
Search (unsorted) O(n) O(1)
Search (sorted) O(log n) O(1)
Insertion (end) O(1) amortized O(1)
Insertion (middle) O(n) O(1)
Deletion (middle) O(n) O(1)

2.3 Prefix Sum

Prefix Sum allows range-sum queries in O(1) after O(n) preprocessing. Extremely useful in
sliding window and subarray problems.
// Build prefix sum array
int[] arr = {3, 1, 4, 1, 5, 9, 2};
int n = [Link];
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + arr[i];
}

// Range sum [l, r] (0-indexed) in O(1)

// Sum = prefix[r+1] - prefix[l]
int sumL2R4 = prefix[5] - prefix[2]; // sum of index 2..4 = 4+1+5 = 10
[Link](sumL2R4); // Output: 10

2.4 Sliding Window

The Sliding Window technique maintains a 'window' of elements and slides it across an
array, often reducing O(n^2) solutions to O(n).
// Maximum sum of subarray of size k
public static int maxSumSubarray(int[] arr, int k) {
int n = [Link];
int windowSum = 0, maxSum = 0;

Page 8 of 45
DSA in Java — Complete Study Guide

// First window
for (int i = 0; i < k; i++) windowSum += arr[i];
maxSum = windowSum;

// Slide the window

for (int i = k; i < n; i++) {
windowSum += arr[i] - arr[i - k]; // add new, remove old
maxSum = [Link](maxSum, windowSum);
}
return maxSum;
}
// Time: O(n) Space: O(1)

2.5 Kadane's Algorithm (Maximum Subarray Sum)

// Finds the maximum sum of any contiguous subarray
public static int kadane(int[] arr) {
int maxSoFar = arr[0];
int maxEndingHere = arr[0];

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

// Either extend current subarray or start fresh
maxEndingHere = [Link](arr[i], maxEndingHere + arr[i]);
maxSoFar = [Link](maxSoFar, maxEndingHere);
}
return maxSoFar;
}

// Example: arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4}

// Output: 6 (subarray [4,-1,2,1])
// Time: O(n) Space: O(1)

2.6 Two Pointer Technique

// Check if a sorted array has a pair with given sum
public static boolean hasPairWithSum(int[] arr, int target) {
int left = 0, right = [Link] - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) return true;
else if (sum < target) left++;
else right--;
}
return false;
}
// Time: O(n) Space: O(1)

Page 9 of 45
DSA in Java — Complete Study Guide

Real-World Use Cases

• Image processing: 2D pixel arrays
• Database: storing rows of data
• Game boards: chess, tic-tac-toe grids
• Signal processing: audio sample buffers

Common Interview Questions

6. Find the maximum subarray sum (Kadane's Algorithm)
7. Rotate an array by k positions
8. Find all pairs in array with given sum
9. Merge two sorted arrays
10. Find the missing number in array 1..n
11. Move all zeros to the end
12. Longest subarray with sum = k

Page 10 of 45
DSA in Java — Complete Study Guide

3. Strings

3.1 Definition
A String in Java is an immutable sequence of characters. Java provides the String class
and StringBuilder for string manipulation.

3.2 Key String Methods

String s = "Hello, World!";

[Link]() // 13
[Link](0) // 'H'
[Link](7, 12) // "World"
[Link]('o') // 4
[Link]() // "hello, world!"
[Link]() // "HELLO, WORLD!"
[Link]() // removes leading/trailing spaces
[Link]('l', 'r') // "Herro, Worrd!"
[Link](", ") // ["Hello", "World!"]
[Link]("World") // true
[Link]("Hello") // true
[Link]("Hello, World!")// true — use equals(), NOT ==

// Convert to char array

char[] chars = [Link]();

// String to int
int n = [Link]("42");
// int to String
String ns = [Link](42); // or [Link](42)

3.3 StringBuilder (Mutable Strings)

Use StringBuilder when you need to modify strings repeatedly. String concatenation in a
loop creates O(n^2) garbage; StringBuilder is O(n).
StringBuilder sb = new StringBuilder();
[Link]("Hello");
[Link](", ");
[Link]("World");
[Link](5, "!!!"); // insert at index 5
[Link](5, 8); // remove index 5..7
[Link](); // reverse entire builder
String result = [Link]();

// Check palindrome efficiently

public static boolean isPalindrome(String s) {

Page 11 of 45
DSA in Java — Complete Study Guide

int l = 0, r = [Link]() - 1;
while (l < r) {
if ([Link](l++) != [Link](r--)) return false;
}
return true;
}

3.4 Anagram Check

// Two strings are anagrams if they have same character frequencies
public static boolean isAnagram(String s, String t) {
if ([Link]() != [Link]()) return false;
int[] freq = new int[26];
for (char c : [Link]()) freq[c - 'a']++;
for (char c : [Link]()) {
freq[c - 'a']--;
if (freq[c - 'a'] < 0) return false;
}
return true;
}
// Time: O(n) Space: O(1) — fixed 26 array

3.5 KMP Algorithm (Pattern Matching)

Knuth-Morris-Pratt algorithm finds all occurrences of a pattern in a text in O(n+m) time,
avoiding naive O(n*m) complexity.
public static int[] buildLPS(String pattern) {
int m = [Link]();
int[] lps = new int[m];
int len = 0, i = 1;
while (i < m) {
if ([Link](i) == [Link](len)) { lps[i++] = ++len; }
else if (len != 0) { len = lps[len - 1]; }
else { lps[i++] = 0; }
}
return lps;
}

public static List<Integer> KMPSearch(String text, String pattern) {

List<Integer> result = new ArrayList<>();
int n = [Link](), m = [Link]();
int[] lps = buildLPS(pattern);
int i = 0, j = 0;
while (i < n) {
if ([Link](i) == [Link](j)) { i++; j++; }
if (j == m) { [Link](i - j); j = lps[j - 1]; }
else if (i < n && [Link](i) != [Link](j)) {
if (j != 0) j = lps[j - 1]; else i++;
}

Page 12 of 45
DSA in Java — Complete Study Guide

}
return result;
}
// Time: O(n + m) Space: O(m)

String Complexity Summary

Operation Time Complexity Space Complexity
charAt / length O(1) O(1)
substring O(n) O(n)
indexOf / contains O(n*m) O(1)
KMP search O(n + m) O(m)
StringBuilder append O(1) amortized O(n)
String concatenation O(n) per concat O(n^2) total
(+)

Common Interview Questions

13. Reverse a string without extra space
14. Find the longest palindromic substring
15. Group anagrams from a list of strings
16. Implement strStr() — find needle in haystack
17. Longest substring without repeating characters
18. Count and say problem
19. Minimum window substring

Page 13 of 45
DSA in Java — Complete Study Guide

4. Linked List

4.1 Definition
A Linked List is a linear data structure where each element (node) stores data and a
reference (pointer) to the next node. Unlike arrays, linked lists do not store elements
contiguously in memory.

4.2 Node Implementation

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

// Doubly Linked List Node

class DListNode {
int val;
DListNode prev, next;
DListNode(int val) { [Link] = val; }
}

4.3 Basic Operations

// Insert at head — O(1)
public ListNode insertHead(ListNode head, int val) {
ListNode node = new ListNode(val);
[Link] = head;
return node;
}

// Insert at tail — O(n)

public void insertTail(ListNode head, int val) {
ListNode cur = head;
while ([Link] != null) cur = [Link];
[Link] = new ListNode(val);
}

// Delete a node by value — O(n)

public ListNode delete(ListNode head, int val) {
if (head == null) return null;
if ([Link] == val) return [Link];
ListNode cur = head;
while ([Link] != null && [Link] != val)
cur = [Link];
if ([Link] != null) [Link] = [Link];

Page 14 of 45
DSA in Java — Complete Study Guide

return head;
}

4.4 Reverse a Linked List

// Iterative — O(n) time, O(1) space
public ListNode reverse(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode next = [Link];
[Link] = prev;
prev = cur;
cur = next;
}
return prev;
}

// Recursive — O(n) time, O(n) space

public ListNode reverseRec(ListNode head) {
if (head == null || [Link] == null) return head;
ListNode rest = reverseRec([Link]);
[Link] = head;
[Link] = null;
return rest;
}

4.5 Detect Loop — Floyd's Algorithm

// Floyd's Cycle Detection (Fast & Slow Pointer)
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && [Link] != null) {
slow = [Link];
fast = [Link];
if (slow == fast) return true; // cycle detected
}
return false;
}

// Find start of cycle

public ListNode detectCycleStart(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && [Link] != null) {
slow = [Link]; fast = [Link];
if (slow == fast) {
slow = head;
while (slow != fast) { slow = [Link]; fast = [Link]; }
return slow; // start of cycle
}

Page 15 of 45
DSA in Java — Complete Study Guide

}
return null;
}

4.6 Merge Two Sorted Lists

public ListNode mergeSorted(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if ([Link] <= [Link]) { [Link] = l1; l1 = [Link]; }
else { [Link] = l2; l2 = [Link]; }
cur = [Link];
}
[Link] = (l1 != null) ? l1 : l2;
return [Link];
}
// Time: O(m+n) Space: O(1)

Complexity Summary
Operation Time Complexity Space Complexity
Access by index O(n) O(1)
Insert/Delete at head O(1) O(1)
Insert/Delete at tail O(n) O(1)
Search O(n) O(1)
Reverse O(n) O(1)

Common Interview Questions

20. Find the middle of a linked list (slow/fast pointer)
21. Reverse a linked list in groups of k
22. Remove nth node from end of list
23. Check if linked list is a palindrome
24. Add two numbers represented as linked lists
25. Flatten a multilevel doubly linked list

Page 16 of 45
DSA in Java — Complete Study Guide

5. Stack & Queue

5.1 Stack — Definition

A Stack is a LIFO (Last-In, First-Out) data structure. The element inserted last is the first to
be removed. Think of a stack of plates.
// Using Deque (preferred over Stack class)
Deque<Integer> stack = new ArrayDeque<>();

[Link](10); // add to top — O(1)

[Link](20);
[Link](30);
int top = [Link](); // view top: 30 — O(1)
[Link](); // remove top: 30 — O(1)
boolean empty = [Link]();

5.2 Balanced Parentheses

public static boolean isBalanced(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : [Link]()) {
if (c=='(' || c=='{' || c=='[') {
[Link](c);
} else {
if ([Link]()) return false;
char top = [Link]();
if (c==')' && top!='(') return false;
if (c=='}' && top!='{') return false;
if (c==']' && top!='[') return false;
}
}
return [Link]();
}
// "({[]})" -> true "{(}" -> false

5.3 Next Greater Element (Monotonic Stack)

// For each element, find the next greater element to the right
public static int[] nextGreater(int[] arr) {
int n = [Link];
int[] result = new int[n];
[Link](result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // stores indices

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

while (![Link]() && arr[i] > arr[[Link]()]) {
result[[Link]()] = arr[i];

Page 17 of 45
DSA in Java — Complete Study Guide

}
[Link](i);
}
return result;
}
// arr=[4,5,2,10,8] -> [5,10,10,-1,-1]
// Time: O(n) Space: O(n)

5.4 Queue — Definition

A Queue is a FIFO (First-In, First-Out) data structure. Elements are added at the rear and
removed from the front. Think of a printer queue.
Queue<Integer> queue = new LinkedList<>();

[Link](10); // enqueue — O(1)

[Link](20);
[Link](30);
int front = [Link](); // view front: 10 — O(1)
[Link](); // dequeue: 10 — O(1)

// Deque as both stack and queue

Deque<Integer> deque = new ArrayDeque<>();
[Link](1); // add to front
[Link](2); // add to rear
[Link](); // remove from front
[Link](); // remove from rear

5.5 Priority Queue (Heap-based)

// Min Heap — smallest element first
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
[Link](30); [Link](10); [Link](20);
[Link]([Link]()); // 10 (minimum)

// Max Heap — largest element first

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

// Custom comparator (sort by frequency)

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);

Complexity Summary
Operation Time Complexity Space Complexity
Stack push/pop/peek O(1) O(n)
Queue enqueue/dequeue O(1) O(n)

Page 18 of 45
DSA in Java — Complete Study Guide

Priority Queue insert O(log n) O(n)

Priority Queue poll O(log n) O(n)

Common Interview Questions

26. Implement a queue using two stacks
27. Design a stack that supports getMin() in O(1)
28. Evaluate postfix/prefix expression using stack
29. Sliding window maximum using Deque
30. LRU Cache implementation

Page 19 of 45
DSA in Java — Complete Study Guide

6. Hashing

6.1 Definition
Hashing maps data of arbitrary size to fixed-size values (hash codes) using a hash
function. It enables average O(1) lookup, insertion, and deletion.

6.2 HashMap Operations

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

// Basic operations — all O(1) average

[Link]("apple", 3);
[Link]("banana", 5);
[Link]("apple"); // 3
[Link]("cherry", 0); // 0 (key absent)
[Link]("banana"); // true
[Link]("banana");
[Link](); // 1

// Iteration patterns
for ([Link]<String, Integer> entry : [Link]()) {
[Link]([Link]() + " = " + [Link]());
}

// Frequency count — classic pattern

int[] arr = {1, 2, 2, 3, 3, 3};
Map<Integer, Integer> freq = new HashMap<>();
for (int x : arr)
[Link](x, [Link](x, 0) + 1);
// {1=1, 2=2, 3=3}

6.3 Two Sum using HashMap

// Classic interview problem: find indices of two numbers that add to target
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < [Link]; i++) {
int complement = target - nums[i];
if ([Link](complement))
return new int[]{[Link](complement), i};
[Link](nums[i], i);
}
return new int[]{};
}
// nums=[2,7,11,15], target=9 -> [0,1]
// Time: O(n) Space: O(n)

Page 20 of 45
DSA in Java — Complete Study Guide

6.4 HashSet Usage

Set<Integer> set = new HashSet<>();
[Link](1); [Link](2); [Link](3); [Link](2); // duplicate ignored
[Link](2); // true — O(1)
[Link](); // 3

// Find duplicates in array

public static List<Integer> findDuplicates(int[] arr) {
Set<Integer> seen = new HashSet<>();
List<Integer> dups = new ArrayList<>();
for (int x : arr) {
if () [Link](x); // add() returns false if already present
}
return dups;
}

Complexity
Operation Time Complexity Space Complexity
HashMap get/put/remove O(1) average, O(n) O(n)
worst
HashSet add/contains O(1) average, O(n) O(n)
worst
LinkedHashMap (ordered) O(1) average O(n)
TreeMap (sorted) O(log n) O(n)

Common Interview Questions

31. Find the first non-repeating character in a string
32. Group anagrams together
33. Longest consecutive sequence
34. Subarray sum equals k (prefix sum + hashmap)
35. Find all pairs with given sum

Page 21 of 45
DSA in Java — Complete Study Guide

7. Recursion & Backtracking

7.1 Recursion — Definition

Recursion is a technique where a function calls itself to solve smaller instances of the same
problem. Every recursive function must have a base case to prevent infinite recursion.
// Factorial — classic recursion
public static long factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive call
}
// factorial(5) = 5 * 4 * 3 * 2 * 1 = 120

// Fibonacci with memoization

static long[] memo = new long[100];
public static long fib(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n];
return memo[n] = fib(n-1) + fib(n-2);
}
// Without memo: O(2^n) | With memo: O(n) Space: O(n)

7.2 Backtracking
Backtracking explores all possible solutions by building them incrementally and abandoning
(backtracking) as soon as a solution cannot be completed. It uses a 'try, explore, undo'
pattern.
// Generate all permutations of an array
public static void permutations(int[] arr, int start, List<List<Integer>> result) {
if (start == [Link]) {
List<Integer> perm = new ArrayList<>();
for (int x : arr) [Link](x);
[Link](perm);
return;
}
for (int i = start; i < [Link]; i++) {
swap(arr, start, i); // choose
permutations(arr, start+1, result);// explore
swap(arr, start, i); // undo (backtrack)
}
}

static void swap(int[] arr, int i, int j) {

int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
// Time: O(n!) Space: O(n)

Page 22 of 45
DSA in Java — Complete Study Guide

7.3 N-Queens Problem

public static void solveNQueens(int n) {
int[] board = new int[n]; // board[row] = col
solve(board, 0, n);
}

static void solve(int[] board, int row, int n) {

if (row == n) { printBoard(board, n); return; }
for (int col = 0; col < n; col++) {
if (isSafe(board, row, col)) {
board[row] = col; // place queen
solve(board, row+1, n); // explore
// backtrack is implicit (board[row] overwritten next iteration)
}
}
}

static boolean isSafe(int[] board, int row, int col) {

for (int r = 0; r < row; r++) {
if (board[r] == col) return false; // same column
if ([Link](board[r]-col)==[Link](r-row)) return false; // diagonal
}
return true;
}

Common Interview Questions

36. Generate all subsets of a set (Power Set)
37. Solve Sudoku using backtracking
38. Word search in a 2D grid
39. Combination Sum — find all combos that sum to target
40. Palindrome partitioning of a string
41. Rat in a maze problem

Page 23 of 45
DSA in Java — Complete Study Guide

8. Trees & Binary Search Trees

8.1 Binary Tree

A tree is a hierarchical data structure. A Binary Tree is one where each node has at most
two children (left and right).
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { [Link] = val; }
}

8.2 Tree Traversals

// Inorder: Left -> Root -> Right (gives sorted output for BST)
void inorder(TreeNode root) {
if (root == null) return;
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
}

// Preorder: Root -> Left -> Right (used for copying tree)
void preorder(TreeNode root) {
if (root == null) return;
[Link]([Link] + " ");
preorder([Link]);
preorder([Link]);
}

// Postorder: Left -> Right -> Root (used for deletion)

void postorder(TreeNode root) {
if (root == null) return;
postorder([Link]);
postorder([Link]);
[Link]([Link] + " ");
}

// Level Order (BFS) — use Queue

void levelOrder(TreeNode root) {
if (root == null) return;
Queue<TreeNode> q = new LinkedList<>();
[Link](root);
while (![Link]()) {
int size = [Link]();
for (int i = 0; i < size; i++) {
TreeNode node = [Link]();
[Link]([Link] + " ");

Page 24 of 45
DSA in Java — Complete Study Guide

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

if ([Link] != null) [Link]([Link]);
}
[Link](); // new level
}
}

8.3 Binary Search Tree (BST)

In a BST: all nodes in the left subtree have values less than the root, and all nodes in the
right subtree have values greater. This enables O(log n) average operations.
// BST Search
TreeNode search(TreeNode root, int key) {
if (root == null || [Link] == key) return root;
if (key < [Link]) return search([Link], key);
return search([Link], key);
}

// BST Insert
TreeNode insert(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < [Link]) [Link] = insert([Link], val);
else [Link] = insert([Link], val);
return root;
}

// BST Delete
TreeNode delete(TreeNode root, int key) {
if (root == null) return null;
if (key < [Link]) [Link] = delete([Link], key);
else if (key > [Link]) [Link] = delete([Link], key);
else {
if ([Link] == null) return [Link];
if ([Link] == null) return [Link];
// Node with two children: get inorder successor
TreeNode minNode = getMin([Link]);
[Link] = [Link];
[Link] = delete([Link], [Link]);
}
return root;
}
TreeNode getMin(TreeNode node) {
while ([Link] != null) node = [Link];
return node;
}

8.4 Lowest Common Ancestor (LCA)

Page 25 of 45
DSA in Java — Complete Study Guide

// LCA in Binary Tree

TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lca([Link], p, q);
TreeNode right = lca([Link], p, q);
if (left != null && right != null) return root; // split point
return (left != null) ? left : right;
}

Complexity Summary
Operation Time Complexity Space Complexity
BST O(log n) O(log n) stack
Search/Insert/Delete
(avg)
BST O(n) skewed O(n) stack
Search/Insert/Delete
(worst)
Tree Traversals (all) O(n) O(n) stack
Level Order BFS O(n) O(n) queue

Common Interview Questions

42. Height / depth of a binary tree
43. Check if a binary tree is balanced
44. Validate if a tree is a valid BST
45. Right view / Left view of binary tree
46. Diameter of binary tree (longest path)
47. Serialize and deserialize a binary tree
48. Kth smallest element in BST

Page 26 of 45
DSA in Java — Complete Study Guide

9. Heap

9.1 Definition
A Heap is a complete binary tree satisfying the heap property. In a Min Heap, every parent
is smaller than its children. In a Max Heap, every parent is larger. Java's PriorityQueue
implements a min heap by default.
// Min Heap (default PriorityQueue)
PriorityQueue<Integer> minH = new PriorityQueue<>();
[Link](5); [Link](2); [Link](8); [Link](1);
[Link]([Link]()); // 1 (minimum)

// Max Heap
PriorityQueue<Integer> maxH = new PriorityQueue<>([Link]());
[Link](5); [Link](2); [Link](8); [Link](1);
[Link]([Link]()); // 8 (maximum)

9.2 Top K Elements

// Find K largest elements using min heap of size K
public static int[] topKLargest(int[] arr, int k) {
PriorityQueue<Integer> minH = new PriorityQueue<>();
for (int x : arr) {
[Link](x);
if ([Link]() > k) [Link](); // remove smallest
}
int[] result = new int[k];
for (int i = k-1; i >= 0; i--) result[i] = [Link]();
return result;
}
// arr=[3,2,1,5,6,4], k=2 -> [5,6]
// Time: O(n log k) Space: O(k)

9.3 Heap Sort

public static void heapSort(int[] arr) {
int n = [Link];
// Build max heap
for (int i = n/2 - 1; i >= 0; i--) heapify(arr, n, i);
// Extract elements one by one
for (int i = n-1; i > 0; i--) {
int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; // swap max to end
heapify(arr, i, 0);
}
}

static void heapify(int[] arr, int n, int i) {

Page 27 of 45
DSA in Java — Complete Study Guide

int largest = i, l = 2*i+1, r = 2*i+2;

if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) {
int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
heapify(arr, n, largest);
}
}
// Time: O(n log n) Space: O(1) — in-place

Common Interview Questions

49. Find the median of a data stream (two heaps)
50. Kth largest element in an array
51. Merge K sorted lists
52. Task scheduler — minimum intervals
53. Find K closest points to origin

Page 28 of 45
DSA in Java — Complete Study Guide

10. Graphs

10.1 Definition
A Graph is a collection of vertices (nodes) and edges (connections). Graphs can be
directed/undirected, weighted/unweighted, cyclic/acyclic.

10.2 Graph Representation

// Adjacency List (preferred for sparse graphs)
int V = 5;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) [Link](new ArrayList<>());

// Add undirected edge between 0 and 1

[Link](0).add(1);
[Link](1).add(0);

// Adjacency Matrix (preferred for dense graphs)

int[][] matrix = new int[V][V];
matrix[0][1] = 1; // directed edge from 0 to 1
matrix[1][0] = 1; // undirected: add both

10.3 BFS (Breadth-First Search)

public static void bfs(List<List<Integer>> adj, int start, int V) {
boolean[] visited = new boolean[V];
Queue<Integer> q = new LinkedList<>();
visited[start] = true;
[Link](start);

while (![Link]()) {
int node = [Link]();
[Link](node + " ");
for (int neighbor : [Link](node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
[Link](neighbor);
}
}
}
}
// Time: O(V + E) Space: O(V)

10.4 DFS (Depth-First Search)

public static void dfs(List<List<Integer>> adj, int node, boolean[] visited) {

Page 29 of 45
DSA in Java — Complete Study Guide

visited[node] = true;
[Link](node + " ");
for (int neighbor : [Link](node)) {
if (!visited[neighbor]) dfs(adj, neighbor, visited);
}
}
// Time: O(V + E) Space: O(V) for recursion stack

10.5 Dijkstra's Shortest Path

// Single-source shortest path for non-negative weights
public static int[] dijkstra(int[][] graph, int src, int V) {
int[] dist = new int[V];
[Link](dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]);
[Link](new int[]{0, src}); // {distance, node}

while (![Link]()) {
int[] curr = [Link]();
int d = curr[0], u = curr[1];
if (d > dist[u]) continue; // stale entry
for (int v = 0; v < V; v++) {
if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
[Link](new int[]{dist[v], v});
}
}
}
return dist;
}
// Time: O((V+E) log V) Space: O(V)

10.6 Union-Find (Disjoint Set Union)

class DSU {
int[] parent, rank;
DSU(int n) {
parent = new int[n]; rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // path compression
return parent[x];
}
void union(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return;
if (rank[px] < rank[py]) { int t=px; px=py; py=t; }

Page 30 of 45
DSA in Java — Complete Study Guide

parent[py] = px;
if (rank[px] == rank[py]) rank[px]++;
}
boolean connected(int x, int y) { return find(x) == find(y); }
}
// Nearly O(1) per operation (inverse Ackermann)

Graph Algorithm Complexity

Operation Time Complexity Space Complexity
BFS / DFS O(V + E) O(V)
Dijkstra (adj matrix) O(V^2) O(V)
Dijkstra (adj list + O((V+E) log V) O(V+E)
heap)
Bellman-Ford O(V * E) O(V)
Floyd-Warshall (all O(V^3) O(V^2)
pairs)
Kruskal's MST O(E log E) O(V+E)
Prim's MST O(E log V) O(V+E)

Common Interview Questions

54. Number of islands (flood fill using BFS/DFS)
55. Detect cycle in directed / undirected graph
56. Topological sort using Kahn's algorithm (BFS)
57. Find shortest path in a maze
58. Course schedule — can all courses be completed?
59. Clone a graph

Page 31 of 45
DSA in Java — Complete Study Guide

11. Sorting & Searching Algorithms

11.1 Sorting Algorithms Overview

Operation Time Complexity Space Complexity
Bubble Sort O(n^2) O(1)
Selection Sort O(n^2) O(1)
Insertion Sort O(n^2) O(1)
Merge Sort O(n log n) O(n)
Quick Sort O(n log n) avg O(log n)
Heap Sort O(n log n) O(1)
Counting Sort O(n + k) O(k)
Radix Sort O(d*(n+k)) O(n+k)

11.2 Merge Sort

public static void mergeSort(int[] arr, int l, int r) {
if (l >= r) return;
int mid = l + (r - l) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid+1, r);
merge(arr, l, mid, r);
}

static void merge(int[] arr, int l, int mid, int r) {

int[] tmp = new int[r - l + 1];
int i = l, j = mid+1, k = 0;
while (i <= mid && j <= r)
tmp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
while (i <= mid) tmp[k++] = arr[i++];
while (j <= r) tmp[k++] = arr[j++];
for (int x = 0; x < [Link]; x++) arr[l+x] = tmp[x];
}
// Stable sort | Time: O(n log n) | Space: O(n)

11.3 Quick Sort

public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}

Page 32 of 45
DSA in Java — Complete Study Guide

static int partition(int[] arr, int low, int high) {

int pivot = arr[high]; // last element as pivot
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}
}
int tmp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = tmp;
return i + 1;
}
// Avg: O(n log n) | Worst: O(n^2) | Space: O(log n) | In-place

11.4 Binary Search

// Classic Binary Search on sorted array
public static int binarySearch(int[] arr, int target) {
int lo = 0, hi = [Link] - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // avoids integer overflow
if (arr[mid] == target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // not found
}

// Binary Search on Answer — find first bad version

public static int firstBadVersion(int n) {
int lo = 1, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (isBadVersion(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
// Time: O(log n) Space: O(1)

Common Interview Questions

60. Find the square root of a number using binary search
61. Search in a rotated sorted array
62. Count inversions in an array (modified merge sort)
63. Kth largest element (quick select)

Page 33 of 45
DSA in Java — Complete Study Guide

64. Find peak element in an array

Page 34 of 45
DSA in Java — Complete Study Guide

12. Dynamic Programming

12.1 Definition
Dynamic Programming (DP) solves problems by breaking them into overlapping
subproblems, solving each once, and storing results. It applies when a problem has optimal
substructure and overlapping subproblems.

12.2 Two Approaches

// ─── MEMOIZATION (Top-Down) ───
// Recursive with caching
int[] dp = new int[n + 1];
[Link](dp, -1);
int memo(int n) {
if (n <= 1) return n;
if (dp[n] != -1) return dp[n];
return dp[n] = memo(n-1) + memo(n-2); // Fibonacci
}

// ─── TABULATION (Bottom-Up) ───

// Iterative, fills table from base cases
int tabFib(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}

12.3 0/1 Knapsack

// Given weights[], values[], capacity W — maximize value
public static int knapsack(int[] wt, int[] val, int W, int n) {
int[][] dp = new int[n+1][W+1];
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
dp[i][w] = dp[i-1][w]; // don't take item i
if (wt[i-1] <= w) // take item i
dp[i][w] = [Link](dp[i][w],
val[i-1] + dp[i-1][w - wt[i-1]]);
}
}
return dp[n][W];
}
// Time: O(n*W) Space: O(n*W)

Page 35 of 45
DSA in Java — Complete Study Guide

12.4 Longest Common Subsequence (LCS)

public static int lcs(String s, String t) {
int m = [Link](), n = [Link]();
int[][] dp = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if ([Link](i-1) == [Link](j-1))
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = [Link](dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
// lcs("AGGTAB", "GXTXAYB") = 4 (GTAB)
// Time: O(m*n) Space: O(m*n)

12.5 Longest Increasing Subsequence (LIS)

// O(n^2) DP approach
public static int lis(int[] arr) {
int n = [Link];
int[] dp = new int[n];
[Link](dp, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i])
dp[i] = [Link](dp[i], dp[j] + 1);
}
maxLen = [Link](maxLen, dp[i]);
}
return maxLen;
}
// arr=[10,9,2,5,3,7,101,18] -> 4 (2,3,7,101)

Common DP Interview Questions

65. Coin change — minimum coins to make amount
66. Edit distance (Levenshtein distance)
67. Unique paths in a grid
68. Word break problem
69. Maximum product subarray
70. Partition equal subset sum
71. Egg drop problem

Page 36 of 45
DSA in Java — Complete Study Guide

Page 37 of 45
DSA in Java — Complete Study Guide

13. Bit Manipulation

13.1 Bitwise Operators Cheat Sheet

Operation Time Complexity Space Complexity
a & b AND — both bits 1 0101 & 0011 = 0001
a | b OR — at least one 1 0101 | 0011 = 0111
a ^ b XOR — exactly one 1 0101 ^ 0011 = 0110
~a NOT — flip all bits ~0101 = 1010
a << k Left shift (x 2^k) 0001 << 3 = 1000 (8)
a >> k Right shift (/ 2^k) 1000 >> 2 = 0010 (2)

// Common bit tricks

int n = 45; // 101101

// Check if ith bit is set

boolean isSet = (n & (1 << i)) != 0;

// Set ith bit

n = n | (1 << i);

// Clear ith bit

n = n & ~(1 << i);

// Toggle ith bit

n = n ^ (1 << i);

// Count set bits (Brian Kernighan)

int count = 0;
while (n > 0) { n &= (n - 1); count++; } // clears lowest set bit

// Check if power of 2
boolean isPow2 = (n > 0) && (n & (n-1)) == 0;

// XOR trick: find single number in array where all others appear twice
int single = 0;
for (int x : arr) single ^= x; // all pairs cancel out

Common Interview Questions

72. Find the single non-duplicate element (XOR)
73. Number of 1 bits (Hamming weight)
74. Reverse bits of a 32-bit integer

Page 38 of 45
DSA in Java — Complete Study Guide

75. Sum of two integers without + operator

76. Generate all subsets using bit masking

Page 39 of 45
DSA in Java — Complete Study Guide

14. Greedy Algorithms & Mathematical Algorithms

14.1 Greedy Algorithms

Greedy algorithms make the locally optimal choice at each step, hoping to find the global
optimum. They work when the problem has the greedy choice property and optimal
substructure.
// Activity Selection — maximize non-overlapping activities
// Sort by end time, then greedily pick non-conflicting activities
public static int activitySelection(int[] start, int[] end) {
int n = [Link];
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
[Link](idx, (a, b) -> end[a] - end[b]); // sort by end time

int count = 1, lastEnd = end[idx[0]];

for (int i = 1; i < n; i++) {
if (start[idx[i]] >= lastEnd) {
count++;
lastEnd = end[idx[i]];
}
}
return count;
}
// Time: O(n log n) Space: O(n)

14.2 Mathematical Algorithms

// Sieve of Eratosthenes — all primes up to n
public static boolean[] sieve(int n) {
boolean[] isPrime = new boolean[n + 1];
[Link](isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i*i; j <= n; j += i) isPrime[j] = false;
}
}
return isPrime;
}
// Time: O(n log log n) Space: O(n)

// GCD using Euclidean algorithm

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

Page 40 of 45
DSA in Java — Complete Study Guide

// Fast exponentiation (modular)

public static long modPow(long base, long exp, long mod) {
long result = 1;
base %= mod;
while (exp > 0) {
if ((exp & 1) == 1) result = result * base % mod;
base = base * base % mod;
exp >>= 1;
}
return result;
}
// Time: O(log exp) Space: O(1)

Page 41 of 45
DSA in Java — Complete Study Guide

15. Advanced DSA Topics

15.1 Trie (Prefix Tree)

A Trie is a tree-like data structure used for efficient retrieval of strings, especially for prefix
matching and autocomplete.
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd = false;
}

class Trie {
TrieNode root = new TrieNode();

void insert(String word) {

TrieNode cur = root;
for (char c : [Link]()) {
int idx = c - 'a';
if ([Link][idx] == null)
[Link][idx] = new TrieNode();
cur = [Link][idx];
}
[Link] = true;
}

boolean search(String word) {

TrieNode cur = root;
for (char c : [Link]()) {
int idx = c - 'a';
if ([Link][idx] == null) return false;
cur = [Link][idx];
}
return [Link];
}

boolean startsWith(String prefix) {

TrieNode cur = root;
for (char c : [Link]()) {
int idx = c - 'a';
if ([Link][idx] == null) return false;
cur = [Link][idx];
}
return true;
}
}
// Insert/Search/Prefix: O(m) where m = word length

15.2 Segment Tree

Page 42 of 45
DSA in Java — Complete Study Guide

A Segment Tree supports efficient range queries (sum, min, max) and point updates in
O(log n) time.
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 l, int r) {
if (l == r) { tree[node] = arr[l]; return; }
int mid = (l + r) / 2;
build(arr, 2*node+1, l, mid);
build(arr, 2*node+2, mid+1, r);
tree[node] = tree[2*node+1] + tree[2*node+2]; // sum query
}
int query(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0; // out of range
if (ql <= l && r <= qr) return tree[node]; // fully in range
int mid = (l + r) / 2;
return query(2*node+1, l, mid, ql, qr) +
query(2*node+2, mid+1, r, ql, qr);
}
void update(int node, int l, int r, int idx, int val) {
if (l == r) { tree[node] = val; return; }
int mid = (l + r) / 2;
if (idx <= mid) update(2*node+1, l, mid, idx, val);
else update(2*node+2, mid+1, r, idx, val);
tree[node] = tree[2*node+1] + tree[2*node+2];
}
}
// Build: O(n) | Query/Update: O(log n) | Space: O(n)

Page 43 of 45
DSA in Java — Complete Study Guide

16. 30-Day DSA Roadmap

Follow this structured plan to go from beginner to interview-ready in 30 days. Spend 2-3
hours daily.

Operation Time Complexity Space Complexity

Week 1 (Days 1-7) Java Basics, Arrays,
Strings, Prefix Sum,
Sliding Window, Two
Pointers
Week 2 (Days 8-14) Linked Lists, Stack,
Queue, Hashing, Basic
Recursion
Week 3 (Days 15-21) Trees, BST, Heaps,
Backtracking, Sorting &
Searching
Week 4 (Days 22-30) Graphs (BFS/DFS),
Dynamic Programming,
Greedy, Tries, Bit
Manipulation

Best Practice Platforms

• LeetCode — [Link] (Most important for interviews)
• GeeksforGeeks — [Link] (Theory + Practice)
• Codeforces — [Link] (Competitive programming)
• HackerRank — [Link] (Structured tracks)
• Coding Ninjas (Code360) — [Link]

Top Interview Preparation Tips

77. Understand the problem before coding — think out loud, draw examples
78. Always clarify edge cases: empty array, single element, negatives, overflow
79. Start with brute force, then optimize
80. Know time and space complexity of your solution
81. Practice problems from FAANG companies: Amazon, Google, Microsoft, Meta
82. Do at least 150+ LeetCode problems (Easy: 50, Medium: 80, Hard: 20+)
83. Review solutions even for problems you solved — learn optimal approaches
84. Mock interviews: practice explaining your thought process aloud

Must-Know DSA Problems (Top 25)

Page 44 of 45
DSA in Java — Complete Study Guide

85. Two Sum — HashMap

86. Maximum Subarray — Kadane's
87. Valid Parentheses — Stack
88. Merge Intervals — Sorting
89. Number of Islands — BFS/DFS
90. Climbing Stairs — DP
91. Coin Change — DP
92. LCS / Edit Distance — DP
93. Binary Search variants
94. Reverse Linked List
95. Detect cycle in Linked List
96. LRU Cache — HashMap + Doubly Linked List
97. Word Search — Backtracking
98. N-Queens — Backtracking
99. Lowest Common Ancestor — Tree
100. Serialize / Deserialize Binary Tree
101. Course Schedule — Topological Sort
102. Dijkstra's Shortest Path
103. Top K Frequent Elements — Heap
104. Find Median from Data Stream — Two Heaps
105. Trapping Rain Water — Two Pointers / Stack
106. Longest Palindromic Substring — DP / Expand Around Center
107. Subarray Sum Equals K — Prefix Sum + HashMap
108. Single Number — XOR
109. Product of Array Except Self — Prefix/Suffix

Mini Projects Using DSA in Java

• Contact Book — HashMap + sorting + binary search
• Simple Expression Evaluator — Stack (infix to postfix)
• Autocomplete System — Trie
• Social Network Friends Graph — Graph BFS/DFS
• Task Scheduler — Priority Queue (heap)
• Shortest Path Finder (Maze) — BFS / Dijkstra

Consistency beats intensity. Solve 2-3 problems daily rather than 20 in one day. Review,
FINAL TIP
revise, and revisit topics weekly. Track your progress and celebrate small wins!

Page 45 of 45