Saurav's DSA Templates 💻 📌

The repository holds the implementation of many basic and advanced Data Structures and Algorithms in Java. Feel free to fork the repo and use it for Problem Solving or Competitive Programming or simply understanding and modifying the implementation.

DSA Contents ❄️

Supported Data Structures 🎉

1. Binary Tree
2. Graph Concepts
3. Binary Heap
4. Disjoint Union Set
5. Tries / Prefix Tree
6. Linked List

Supported Algorithms 🔆

1. Tree

   1. Building a Binary Tree from an Array.
   2. Finding the longest path in a Tree. Related Problem
   3. Depth First Search in a tree to compute on each path from Root too Leaf Nodes. Related Problem

2. Two Pointers

   1. Two Pointer approach for Rain Water Trapping problem

3. Graph Concept

   1. Making a Directed Graph
   2. Building a Weighted Directed Graph
   3. Computing Shortest Path - Dijkstra's with Min Heap (Optimised)
   4. Cycle Detection via single DFS iteration
   5. Water and Jug Problem (BFS) Problem Link
   6. Count number of Battleships on the board (DFS) Problem Link
   7. Returning a range of numbers in Lexicographical Order (DFS) Problem Link

4. Disjoin Union Set

   1. Union by Size
   2. Path Compression
   3. Finding Connected Components

5. Trie / Prefix Tree

   1. Implementation
   2. Insertion, Search and Prefix Search
   3. A Data Structure to Search Words and Patterns (BFS on Tries) Problem Link

6. Binary Heap

   1. Binary Max Heap implementation
   2. Finding K most frequent elements

7. Linked List

   1. Swapping adjacent nodes in a Linked List
   2. LRU Cache

8. Sliding Window

   1. Counting all possible subarrays with every distinct elements: Related Problem

9. Binary Search

   1. Finding peak in a Mountain Array: Problem Link
   2. Binary Search in a 2D Matrix: Problem Link

10. Fast IO for taking inputs in huge amount. Suited for Competitive Programming.

11. Helper Methods:

    1. A method which takes input a list of integers from the user and returns an array of integers.

DSA Problems Solved 🎯

S.No.	Problem Name	Link	Runtime	Tags
1.	House Robber III	View Problem	5 ms	DP, Tree, DFS
2.	Container with most water	View Problem	5 ms	Two Pointers, Array
3.	Course Schedule	View Problem	3 ms	Graphs, DFS, Directed Graphs
4.	Evaluate Division	View Problem	8 ms	Graphs, DFS, Directed Graphs, Weighted Graphs
5.	Number of Provinces	View Problem	2 ms	Disjoint Union Set, Connected Components, Graph
6.	Word Break	View Problem	11 ms	Recursion, Dynamic Programming
7.	Implement Trie	View Problem	45 ms	Trie, Prefix Tree
8.	Top K Frequent Elements	View Problem	17 ms	Binary Max Heap
9.	Network Delay Time	View Problem	76 ms	Graph, Heap, Dijkstras Algorithm, Shortest Path
10.	Swap Nodes in Pairs	View Problem	5 ms	Linked List
11.	Minimum Cost to Reach Destination in Time	View Problem	140 ms	Graph, Dijkstra, Priority Queue, Shortest Path
12.	Minimum Height Trees	View Problem	27 ms	Tree, DFS, Longest Path, Recursion
13.	Find Eventual Safe States	View Problem	164 ms	Graph, DFS, Cycle Detection
14.	Sum Root to Leaf Numbers	View Problem	0 ms	Binary Tree, DFS, Recursion, Number Theory
15.	Most Frequent Subtree Sum	View Problem	6 ms	Binary Tree, DFS, Hash Tables
16.	Edit Distance	View Problem	6 ms	DP, String
17.	Count Complete Subarrays in an Array	View Problem	5 ms	Hashtables, Sliding Window
18.	Repeated DNA Sequences	View Problem	39 ms	Hashtables, Sliding Window
19.	Peak Index in a Mountain Array	View Problem	0 ms	Arrays, Binary Search
20.	Search a 2D Matrix	View Problem	0 ms	2D Array (Matrix), Binary Search
21.	Water and Jug Problem	View Problem	1482 ms	BFS, Graph, Maths
22.	Pacific Atlantic Water Flow	View Problem	4 ms	BFS, Graph, Matrix
23.	Island Perimeter	View Problem	5 ms	Graph, Matrix
24.	Battleships in a Board	View Problem	1 ms	Graph, DFS, Matrix
25.	Design Add and Search Words Data Structure	View Problem	270 ms	Trie, DFS, Design, String
26.	Lexicographical Numbers	View Problem	4 ms	Tree, DFS, Number Theory
27.	LRU Cache	View Problem	52 ms	Linked List, HashMap
28.	Count Submatrices with Top-Left Element and Sum Less Than k	View Problem	5 ms	Dynamic Programming, Prefix Sum, 2d Array (Matrix)
29.	Minimum Operations to Write the Letter Y on a Grid	View Problem	3 ms	Maths, 2d Array (Matrix)

All the DSA Problems' solution implements the Data Structures and Algorithms from this repo to achieve the above mentioned Runtime.