DSA Java Notes 🧠

A structured Data Structures & Algorithms learning path — Beginner → Advanced — documented in Java, following a phase-wise roadmap. Each topic links to its own Markdown notes (pattern explanation, visual walkthrough, complexity, Java implementation, and related LeetCode problems).

Progress Legend

✅ Done   🔄 In Progress   ⬜ Not Started

---

📂 Repository Structure

dsa-java-notes/
├── phase-1-foundations/
├── phase-2-linear-data-structures/
├── phase-3-recursion-thinking-patterns/
├── phase-4-non-linear-data-structures/
├── phase-5-greedy/
├── phase-6-dynamic-programming/
└── phase-7-advanced-range-structures/

---

Phase 1: Foundations

Sorting Algorithms

• ⬜ Bubble Sort
• ⬜ Selection Sort
• ⬜ Insertion Sort
• ⬜ Merge Sort
• ⬜ Quick Sort
• ⬜ Heap Sort
• ⬜ Counting Sort
• ⬜ Radix Sort
• ⬜ Bucket Sort

Bit Manipulation

Core

• ⬜ XOR Pattern
• ⬜ Bit Masking

Usage

• ⬜ Bit Checks
• ⬜ Subset via Bits
• ⬜ Prefix XOR

---

Phase 2: Linear Data Structures

Array

Two Pointer

• ⬜ Opposite ends (left + right)
• ⬜ Same direction (fast & slow pointers)
• ⬜ Partition / Dutch flag

Sliding Window

• ⬜ Fixed Size
• ⬜ Variable Size
• ⬜ Expand–Shrink
• ⬜ Monotonic Window

Prefix Based

• ⬜ Prefix Sum
• ⬜ Prefix XOR
• ⬜ 2D Prefix

Kadane's / Subarray

• ⬜ Max subarray sum (Kadane's)
• ⬜ Max product subarray
• ⬜ Subarray with given XOR / sum

Binary Search

• ⬜ On index
• ⬜ On answer

Hash Map

• ⬜ Frequency Based
• ⬜ Lookup Based
• ⬜ Set Based
• ⬜ Index Mapping
• ⬜ Grouping Pattern

String

Two Pointers

• ⬜ Palindrome check
• ⬜ Reverse words / characters
• ⬜ String compression

Sliding Window

• ⬜ Longest substring without repeat
• ⬜ Minimum window substring
• ⬜ Anagram / permutation in string

Pattern Matching

• ⬜ KMP (failure function)
• ⬜ Rabin-Karp (rolling hash)
• ⬜ Z-algorithm

Linked List

Pointer Techniques

• ⬜ Fast–Slow
• ⬜ Cycle Detection
• ⬜ Finding Middle

Reversal

• ⬜ Full Reverse

• ⬜ Partial (k-group)

• ⬜ Merge Lists

Stack

Monotonic Stack

• ⬜ Increasing
• ⬜ Decreasing

Nearest Element

• ⬜ Next Greater

• ⬜ Next Smaller

• ⬜ Previous Variants

• ⬜ Range / Span

• ⬜ Min/Max Stack

• ⬜ Expression Handling

• ⬜ Histogram Pattern

Queue / Deque

• ⬜ FIFO Processing
• ⬜ Level-wise Processing
• ⬜ Circular Queue Pattern
• ⬜ Deque Based

---

Phase 3: Recursion & Thinking Patterns

Recursion

Divide & Conquer

• ⬜ Merge sort pattern
• ⬜ Quick select (Kth largest)
• ⬜ Count inversions

Backtracking — Exploration

• ⬜ Decision Tree
• ⬜ Choose–Explore–Unchoose
• ⬜ Subsets (power set)
• ⬜ Permutations / Combinations (nCr)
• ⬜ Word search on grid
• ⬜ Palindrome partitioning

Backtracking — Pruning / State Tracking

• ⬜ Pruning / State Tracking

---

Phase 4: Non-Linear Data Structures

Trees

Traversal

• ⬜ DFS (Pre / In / Post order)
• ⬜ BFS (Level Order / zigzag / right side view)

Recursion Patterns

• ⬜ Top Down approach
• ⬜ Bottom Up approach

Path Based

• ⬜ Max path sum

• ⬜ Diameter / Height / depth

• ⬜ BST (Binary Search Tree)

Heap

• ⬜ Top K / Kth Element / K closest points

Greedy + Heap

• ⬜ Task scheduler

• ⬜ Meeting rooms

• ⬜ Reorganize string

• ⬜ Huffman encoding

• ⬜ K-way Merge

Trie

Prefix Based

• ⬜ Insert / Search

• ⬜ Prefix Match

• ⬜ Bitwise Trie

Graphs

Traversal

• ⬜ BFS
• ⬜ DFS

Cycle Detection

• ⬜ Directed
• ⬜ Undirected

Topological Sort

• ⬜ Kahn's algorithm (BFS in-degree)
• ⬜ Topological Sort (BFS / DFS)
• ⬜ DFS-based topo sort

Shortest Path

• ⬜ Dijkstra
• ⬜ Bellman-Ford
• ⬜ Floyd-Warshall (all pairs)

Spanning Tree

• ⬜ Kruskal

• ⬜ Prims

• ⬜ Union-Find (DSU) — Detect cycle in undirected

• ⬜ Bipartite / Multi-source BFS / 0-1 BFS

---

Phase 5: Greedy

Greedy

Interval Greedy

• ⬜ Activity Selection
• ⬜ Non-overlapping Intervals
• ⬜ Minimum Removals

Scheduling Greedy

• ⬜ Deadline Based Scheduling
• ⬜ Profit Based Selection

Resource Allocation

• ⬜ Minimum Platforms / Rooms

• ⬜ Meeting Rooms

• ⬜ Jump Game Pattern

• ⬜ Huffman / Merge Cost

---

Phase 6: Dynamic Programming

Dynamic Programming

Core

• ⬜ 1D
• ⬜ 2D

Optimization

• ⬜ Memoization
• ⬜ Tabulation

Transition Type

• ⬜ Linear DP
• ⬜ Grid DP
• ⬜ Decision DP

Pattern Types

• ⬜ Knapsack
• ⬜ Sequence DP
• ⬜ Partition DP
• ⬜ Interval DP

Advanced

• ⬜ Bitmask DP
• ⬜ Digit DP
• ⬜ DP on Trees

---

Phase 7: Advanced Range Structures

Range Structures

Segment Tree

• ⬜ Range Query
• ⬜ Lazy Propagation

Fenwick Tree

• ⬜ Prefix Query

---

📄 Documentation Format

Every algorithm/pattern note follows a fixed template:

• What It Is — plain-language explanation
• Visual Walkthrough — step-by-step trace on a sample input
• Time & Space Complexity — using Ω (best), Θ (average), O (worst) notation
• Optimized Java Implementation — LeetCode-style, function-only, no built-ins
• Related LeetCode Problems — hyperlinked
• When to Use — practical guidance

---

🎯 Goal

Build a strong DSA foundation in Java toward becoming a well-paid software engineer, covering DSA → DAA → System Design → Java Full Stack.