/DSA-Templates_patterns

My Data Structures and Algorithms templates

Primary LanguageJava

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

  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

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