Java Algorithm Implementation

Solved coding problems in Java from different learning platforms and implementation of standard Algorithms and Data Structures.

Different Packages

Name of Package	Description
com.arrays	Problem based on Arrays Data Structure
com.concurrency	Problems for concurrency and multithreading
com.design	Standard implementation of requirement using OOPs and library function implementation
com.disjoint_set	Problem based on Union Find
com.dp	Most frequent used pattern of Dynamic Programming
com.graph	Implementation of well-known graph algorithms and DFS, BFS

Topic Wise Problems

Arrays

No	Problem	Solution	Sub Topic	Time	Space
1	Two Sum	Solution	Hashing	O(n)	O(n)
2	Contains Duplicate	Solution	Hashing	O(n)	O(n)
3	Product of Array Except Self	Solution	Prefix Sum	O(n)	O(1)
4	Valid Sudoku	Solution	Grid	O(n^2)	O(n)
5	Range Sum Query 2D - Immutable	Solution	Prefix Sum, Grid	O(mn + q)	O(mn)

Backtracking

No	Problem	Solution	Sub Topic	Time	Space
1	Subsets	Solution	Arrays	O(n * 2 ^ n)	O(n)
2	Combination Sum	Solution	Math	O(2 ^ mn)	O(mn)
3	Permutations	Solution	Math	O(n * n!)	O(n)
4	Letter Combinations of a Phone Number	Solution	Math	O(n * 4^n)	O(n)
5	Generate Parentheses	Solution	String	O(4^n / sqrt(n))	O(4^n / sqrt(n))
6	Permutations II	Solution	Math, HashTable	O(n.n!)	O(n)
7	Subsets II	Solution	String	O(n.2^n)	O(n)
8	Combination Sum II	Solution	Array	O(2^n)	O(n)
9	N-Queens	Solution	Array	~ O(N!)	O(n)
10	N-Queens II	Solution	Array	~ O(N!)	O(n)
11	Word Search	Solution	Grid	O(mn4^s)	O(m + n)

Binary Search

No	Problem	Solution	Sub Topic	Time	Space
1	Longest Increasing Subsequence	Solution	Greedy, DP	O(nlogn)	O(n)
2	Search in Rotated Sorted Array	Solution	Arrays	O(logn)	O(1)
3	Find Minimum in Rotated Sorted Array	Solution	Arrays	O(logn)	O(1)

Bit Manipulation

No	Problem	Solution	Sub Topic	Time	Space
1	Number of 1 Bits	Solution	Number	O(1)	O(1)
2	Number of Steps to Reduce a Number to Zero	Solution	Number	O(logn)	O(1)
3	Missing Number	Solution	Math	O(n)	O(1)
4	Maximum Product of Word Lengths	Solution	BitMask	O(n * (n + N))	O(n)
5	Check String Contains All Binary Codes Of Size K	Solution	Rolling Hash	O(n)	O(2^k)
6	Divide Two Integers	Solution	Bit Shifting	O(logn)	O(1)

Concurrency

No	Problem	Solution	Sub Topic	Time	Space
1	Print In Order	Solution	Semaphores	O(1)	O(1)

Dynamic Programming

No	Problem	Solution	Sub Topic	Time	Space
1	Best Time to Buy and Sell Stock with Cooldown	Solution	Arrays	O(n)	O(n)
2	Longest Common Subsequence	Solution	String, Arrays	O(mn)	O(max(m, n))
3	Coin Change	Solution	Arrays	O(m * n)	O(m)
4	Coin Change 2	Solution	Arrays	O(m * n)	O(m)
5	Target Sum	Solution	2D Arrays	O(m * n)	O(m * n)
6	Partition Equal Subset Sum	Solution	Subset Sum	O(n * m)	O(m)-Optimized
7	Interleaving String	Solution	String	O(n * m)	O(m * n)
8	Count Sorted Vowel Strings	Solution	String	O(n * 5)	O(n * 5)
9	Distinct Subsequences	Solution	String	O(n * m)	O(n * m)
10	Edit Distance	Solution	String	O(n * m)	O(m)-Optimized
11	Ones and Zeroes	Solution	String	O(n * m * k)	O(n * m)-Optimized
12	Delete Operation for Two Strings	Solution	String	O(n * m)	O(m)-Optimized

Graph

No	Problem	Solution	Sub Topic	Time	Space
1	Min Cost to Connect All Points	Solution	MST, Prim's Algo	O(n^2.logn)	O(n^2)
2	Path With Minimum Effort	Solution	Binary Search	O(log(min - max) * m * n)	O(m * n)
3	Evaluate Division	Solution	DFS, BFS	O(V + E)	O(V)
4	Rotting Oranges	Solution	BFS	O(m * n)	O(m * n)
5	Walls and Gates	Solution	BFS	O(m * n)	O(m * n)
6	Course Schedule	Solution	DFS, Cycle Detection	O(V + E)	O(V + E)
7	Course Schedule II	Solution	DFS, BFS, Top Sort	O(V + E)	O(V + E)
8	Redundant Connection	Solution	DFS, Union Find	O(n)	O(n)
9	Longest Increasing Path in a Matrix	Solution	DFS, DP, Top-Sort	O(m * n)	O(m * n)
10	Network Delay Time	Solution	Shortest Path	O(N + ElogN)	O(E)
11	Clone Graph	Solution	Hashing	O(V + E)	O(V)
12	Critical Connections in a Network	Solution	SCC, Tarjan's Algo	O(V + E)	O(V + E)

Greedy Algorithms

No	Problem	Solution	Sub Topic	Time	Space
1	Gas Station	Solution	Arrays	O(n)	O(1)
2	Hand of Straights	Solution	HashTable	O(nlogn)	O(n)
3	Merge Triplets to Form Target Triplet	Solution	Arrays	O(n)	O(1)

Hashing/Hash Table

No	Problem	Solution	Sub Topic	Time	Space
1	Max Number of K-Sum Pairs	Solution	Hash Table	O(n)	O(n)
2	Longest Consecutive Sequence	Solution	Union	O(n)	O(n)

Heap

No	Problem	Solution	Sub Topic	Time	Space
1	K Closest Points to Origin	Solution	Sorting	O(n.logk)	O(k)

Intervals

No	Problem	Solution	Sub Topic	Time	Space
1	Merge Intervals	Solution	Sorting	O(n.logn)	O(n)
2	Non-overlapping Intervals	Solution	Sorting	O(n.logn)	O(n)

Linked-List

No	Problem	Solution	Sub Topic	Time	Space
1	Reorder List	Solution	Two Pointers	O(n)	O(1)
2	Remove Nth Node From End of List	Solution	Two Pointers	O(n)	O(1)
3	Copy List with Random Pointer	Solution	HashMap	O(n)	O(1)-Optimized
4	Add Two Numbers	Solution	Traversal	O(n)	O(1)
5	Intersection of Two Linked Lists	Solution	Two pointers	O(m + n)	O(1)

Math

No	Problem	Solution	Sub Topic	Time	Space
1	Rotate Image	Solution	Matrix, Rotation	O(n * n)	O(1)
2	Minimum Moves to Equal Array Elements II	Solution	Sorting	O(nlogn)	O(n)

Sliding Window

No	Problem	Solution	Sub Topic	Time	Space
1	Longest Substring Without Repeating Characters	Solution	Hash Table	O(n)	O(n)
2	Longest Repeating Character Replacement	Solution	String	O(n)	O(1)
3	Minimum Operations to Reduce X to Zero	Solution	Greedy, Hashing	O(n)	O(1)
4	Maximum Erasure Value	Solution	Hashing	O(n)	O(set(n))

Sorting

No	Problem	Solution	Sub Topic	Time	Space
1	Merge k Sorted Lists	Solution	PQ, Merge Sort	O(nlogk)	O(logk)
2	Kth Largest Element in an Array	Solution	PQ, QuickSelect	Avg.-O(n)	O(1)

Stack

No	Problem	Solution	Sub Topic	Time	Space
1	Shortest Unsorted Continuous Subarray	Solution	Sorting, 2 Pointers	O(n)	O(n)
2	Implement Stack using Queues	Solution	Design	O(n) O(1) O(1)	O(1)
3	Remove All Adjacent Duplicates in String II	Solution	String	O(n)	O(n)
4	132 Pattern	Solution	Monotonic Stack	O(n)	O(n)
5	Remove Duplicate Letters	Solution	Monotonic Stack	O(n)	O(n)
6	Remove K Digits	Solution	Monotonic Stack	O(n)	O(n)
7	Daily Temperatures	Solution	Monotonic Stack	O(n)	O(1)-Optimized
8	Evaluate Reverse Polish Notation	Solution	Stack	O(n)	O(n)
9	Car Fleet	Solution	Monotonic Stack, Sorting	O(nlogn)	O(n)

Tree

No	Problem	Solution	Sub Topic	Time	Space
1	Count Good Nodes in Binary Tree	Solution	Tree PreOrder	O(n)	O(height)
2	Validate Binary Search Tree	Solution	BST	O(n)	O(height)
3	Maximum Binary Tree / Cartesian Tree	Solution	BST	O(n^2)	O(height)
4	Populating Next Right Pointers in Each Node II	Solution	LinkedList, BFS	O(n)	O(1)
5	Deepest Leaves Sum	Solution	DFS, BFS	O(n)	O(n)
6	Tree from Preorder and Inorder	Solution	Hashing	O(n)	O(n)
7	Binary Tree Maximum Path Sum	Solution	DFS	O(n)	O(n)
8	Binary Tree Level Order Traversal	Solution	BFS, DFS	O(n)	O(n)

Two Pointers

No	Problem	Solution	Sub Topic	Time	Space
1	Backspace String Compare	Solution	Stack	O(n + m)	O(1)
2	3Sum	Solution	Sorting	O(n * n)	O(n)
3	Merge Sorted Array	Solution	Sorting	O(n)	O(1)
4	Remove Palindromic Subsequences	Solution	String	O(n)	O(1)
5	Two Sum II - Input Array Is Sorted	Solution	Binary Search	O(n)	O(1)