🧠 DSA Practice — Java

A structured Java project for practicing Data Structures & Algorithms (LeetCode-style). Every problem has a detailed explanation and JUnit 5 tests.

---

🚀 Quick Start

Prerequisites

• Java 17+
• Maven 3.6+

Run All Tests

mvn test

Run Tests for One Category

mvn test -pl . -Dtest="com.dsa.arrays.*"
mvn test -pl . -Dtest="com.dsa.linkedlist.*"
mvn test -pl . -Dtest="com.dsa.trees.*"

Run a Single Test Class

mvn test -Dtest="LRUCacheTest"
mvn test -Dtest="TwoSumTest"

---

📁 Project Structure

dsa-practice/
├── pom.xml
└── src/
    ├── main/java/com/dsa/
    │   ├── datastructures/          ← Shared data structures
    │   │   ├── ListNode.java        ← Linked list node (with builder)
    │   │   └── TreeNode.java        ← Binary tree node (with builder)
    │   ├── utils/
    │   │   └── ArrayUtils.java      ← Helper utilities
    │   └── problems/
    │       ├── TEMPLATE.java        ← Copy this when adding a new problem
    │       ├── arrays/
    │       ├── strings/
    │       ├── linkedlist/
    │       ├── trees/
    │       ├── graphs/
    │       ├── dp/
    │       ├── stack/
    │       ├── heap/
    │       ├── twopointers/
    │       ├── slidingwindow/
    │       ├── backtracking/
    │       ├── greedy/
    │       └── bitsmanipulation/
    └── test/java/com/dsa/
        ├── arrays/
        ├── strings/
        ├── linkedlist/
        ├── trees/
        ├── graphs/
        ├── dp/
        ├── stack/
        ├── twopointers/
        └── slidingwindow/

---

📚 Problems Included

📦 Arrays

#	Problem	Difficulty	Key Concept
1	Two Sum	🟢 Easy	HashMap
11	Container With Most Water	🟡 Medium	Two Pointers
53	Maximum Subarray	🟡 Medium	Kadane's Algorithm
121	Best Time to Buy & Sell Stock	🟢 Easy	Single Pass
238	Product of Array Except Self	🟡 Medium	Prefix × Suffix

🔤 Strings

#	Problem	Difficulty	Key Concept
3	Longest Substring Without Repeating	🟡 Medium	Sliding Window
125	Valid Palindrome	🟢 Easy	Two Pointers
242	Valid Anagram	🟢 Easy	Frequency Count

🔗 Linked List

#	Problem	Difficulty	Key Concept
21	Merge Two Sorted Lists	🟢 Easy	Dummy Node
141	Linked List Cycle	🟢 Easy	Floyd's Algorithm
146	LRU Cache	🟡 Medium	HashMap + DLL
206	Reverse Linked List	🟢 Easy	Iterative + Recursive

🌳 Trees

#	Problem	Difficulty	Key Concept
98	Validate BST	🟡 Medium	DFS with bounds
104	Maximum Depth	🟢 Easy	DFS + BFS
226	Invert Binary Tree	🟢 Easy	DFS

📊 Dynamic Programming

#	Problem	Difficulty	Key Concept
70	Climbing Stairs	🟢 Easy	Fibonacci DP
322	Coin Change	🟡 Medium	Bottom-Up DP
1143	Longest Common Subsequence	🟡 Medium	2D DP

🕸️ Graphs

#	Problem	Difficulty	Key Concept
133	Clone Graph	🟡 Medium	DFS + HashMap
200	Number of Islands	🟡 Medium	DFS Flood Fill

📚 Stack

#	Problem	Difficulty	Key Concept
20	Valid Parentheses	🟢 Easy	Stack
155	Min Stack	🟡 Medium	Two Stacks

🔍 Two Pointers

#	Problem	Difficulty	Key Concept
15	3Sum	🟡 Medium	Sort + Two Pointers

🪟 Sliding Window

#	Problem	Difficulty	Key Concept
239	Sliding Window Maximum	🔴 Hard	Monotonic Deque

🏔️ Heap

#	Problem	Difficulty	Key Concept
215	Kth Largest Element	🟡 Medium	Min-Heap size k

🔙 Backtracking

#	Problem	Difficulty	Key Concept
46	Permutations	🟡 Medium	Backtracking
78	Subsets	🟡 Medium	Backtracking

---

➕ Adding a New Problem

1. Copy the template:

cp src/main/java/com/dsa/problems/TEMPLATE.java \
   src/main/java/com/dsa/problems/arrays/MyNewProblem.java

2. Update the package and class name.

3. Fill in the problem description, approach, and solution.

4. Create a test file in the matching src/test/java/com/dsa/<category>/ folder.

5. Run your tests:

mvn test -Dtest="MyNewProblemTest"

---

🏗️ Using Shared Data Structures

// ── ListNode ─────────────────────────────────────────────────────────
ListNode head = ListNode.of(1, 2, 3, 4, 5);   // builds: 1→2→3→4→5
System.out.println(head);                       // prints: [1 → 2 → 3 → 4 → 5]

// ── TreeNode ─────────────────────────────────────────────────────────
// LeetCode level-order: [3, 9, 20, null, null, 15, 7]
//        3
//       / \
//      9  20
//         / \
//        15   7
TreeNode root = TreeNode.of(3, 9, 20, null, null, 15, 7);

---

🗺️ Learning Roadmap (Suggested Order)

Week 1 → Arrays + Strings        (Two Sum, Anagram, Palindrome)
Week 2 → Linked Lists + Stack    (Reverse LL, Valid Parens, LRU Cache)
Week 3 → Trees                   (Max Depth, Invert Tree, Validate BST)
Week 4 → Graphs                  (Islands, Clone Graph, BFS/DFS patterns)
Week 5 → Two Pointers + Sliding  (3Sum, Longest Substring, Max Window)
Week 6 → DP                      (Climbing Stairs, Coin Change, LCS)
Week 7 → Heap + Backtracking     (Kth Largest, Subsets, Permutations)

---

🧩 Pattern Cheat Sheet

Pattern	When to Use	Time
Two Pointers	Sorted array, pairs, palindrome	O(n)
Sliding Window	Subarray/substring of fixed or variable size	O(n)
HashMap	O(1) lookup, frequency count	O(n)
Monotonic Stack/Deque	Next greater/smaller, sliding window max	O(n)
DFS/BFS	Tree/graph traversal, flood fill	O(V+E)
Min-Heap size k	Kth largest/smallest	O(n log k)
Backtracking	All combinations/subsets/permutations	O(2^n) or O(n!)
Bottom-Up DP	Optimal substructure + overlapping subproblems	O(n²) or O(n)
Binary Search	Sorted data, search space reduction	O(log n)
Floyd's Cycle	Cycle detection in linked list	O(n)