📚Data Structures and Algorithms

Implementation of most common data structures and algorithms in Java.

Data Structures

• 📘 Linked Lists
  • Singly Linked Lists
  • Doubly Linked Lists
• 📘 Stack
  • Using Array
  • Using Linked List
  • Using Queue
• 📘 Queue
  • Using Array
  • Using Linked List
  • Using Stack
• 📘 Deque
  • Using Array
  • Using Linked List
• 📘 Binary Search Tree
• 📘 Hashtable
  • Chaining
  • Open Addressing
• 📘 Union Find
  • Union Find - Merge By Rank
  • Union Find - Merge By Size
• 📘 Heap (Priority Queues)
  • Max Heap
  • Min Heap
• 📘 Self-Balancing BSTs
  • 📘 AVL Tree
  • 📘 Red-Black Tree
• 📘 Trie
• 📘 Segment Tree
  • Range Minimum Query (RMQ)
  • Range Sum Query
  • RMQ - Lazy Propagation
• 📘 Fenwick Tree
• 📘 LRU Cache

Dynamic Programming [Problems]

[Sorted: Easy To Hard]

1. Fibonacci Numbers
2. Ugly Numbers
3. Super Ugly Numbers
4. Tiling 2Xn Floor With 2X1 Tile
5. Tiling NxM Floor With 1xM Tile
6. Gold Mine Problem
7. Max Path Sum
8. Coin Change Problem🔥
9. Friends Pairing Problem
10. Subset Sum Problem
11. Perfect Sum Problem🔥
12. Subset Sum Divisible By M
13. Change Making Problem
14. Rod Cutting Problem
15. Tiling With Dominoes
16. Painting Fence Problem
17. Assembly Line Scheduling
18. Maximum Length Snake Sequence
19. Even Length Binary Sequence
20. Sequences Of Given Length
21. Longest Common Subsequence🔥
22. Longest Repeated Subsequence
23. LCS of 3 Strings
24. Longest Increasing Subsequence🔥
25. Longest Bitonic Subsequence
26. Maximum Sum Increasing Subsequence
27. Maximum Sum Bitonic Subsequence
28. Maximum Product Increasing Subsequence
29. Product Subsequences Count
30. Maximum Sum No Two Adjacent
31. Maximum Sum No Three Adjacent
32. Longest Subseq Adjacent Diff1
33. Max Length Chain Pairs
34. Path With Maximum Average Value
35. Min Cost Path
36. Max Path Sum Triangle
37. Min Path Sum Triangle
38. Maximum Sum Subarray - Kadane’s Algorithm🔥
39. Maximum Size Square Sub Matrix
40. Max Sum 2x1 Grid
41. Max Path Sum With Jumps Under Div
42. Min Jumps To Reach End
43. Edit Distance
44. Longest Common Substring🔥
45. Sum Of All Substrings
46. Count Ways To Build Street
47. Cover Distance
48. Diff Ways To Sum
49. 0-1 Knapsack🔥
50. Temple Offering Problem
51. Egg Dropping Problem
52. Dice Throw Problem
53. Word Break Problem🔥
54. Box Stacking Problem
55. Longest Palindromic Subsequence
56. Count All Palindromic Subsequence
57. Longest Palindromic Substring
58. Count All Palindrome SubStrings
59. Shortest Common Supersequence
60. Longest ZigZag or Alternating Subsequence
61. Maximum Sum ZigZag or Alternating Subsequence
62. Minimum Number of Coins To Make a Change
63. Possible Ways To Construct Buildings
64. Number Different Ways To Reach End
65. Count Number of Binary Strings Without Consecutive 1s
66. Count Number of Paths With At Most k Turns
67. Count Possible Decodings of Digit Sequence
68. Number of Ways To Partition A Set Into k Subsets
69. Count n Digit Numbers With Given Digit Sum
70. Count Strings Formed Using a b c
71. Count Numbers With Even Odd Digit Sum Difference of 1
72. Maximum Profit From Sale of Wines
73. Maximum Size Subset Sum
74. Maximum Sum Subarray Removing At Most One Element
75. K maximum sums of non-overlapping contiguous sub-arrays
76. Maximum Product Subarray
77. Maximum Dot Product of Two Arrays
78. Minimum Initial Points to Reach Destination (Dungeon Game)🔥
79. Minimum Insertions To Form Palindrome
80. Minimum Number of Squares Sum to Given Number
81. Remove Minimum Elements From Either Side
82. Minimum Cells Required To Reach Destination
83. Longest Increasing Circular Subsequence
84. Longest Path In A Matrix With Given Constraints
85. Count Distinct Subsequences
86. Longest Consecutive Path In Matrix
87. Length of longest subsequence of one string which is substring of another string
88. Wildcard Pattern Matching
89. Optimal Strategy For Game
90. Number of Permutations With K Inversions
91. Largest Divisible Pairs Subset
92. Sum Of Digits In Numbers From 1 To N
93. Number of Non Decreasing Numbers
94. Catalan Number 📘
95. Non-crossing lines to connect points in a circle
96. Building Bridges
97. Longest Substring Without Repeating Characters
98. Longest Even Length Substring such that Sum of First and Second Half is same
99. Partition Set To Subset Sum Minimum Diff
100. Matrix Chain Multiplication🔥
101. Minimum and Maximum values of an expression
102. Optimal Binary Search Tree
103. Regular Expression Matching
104. Text Justification
105. Palindrome Partitioning
106. Mobile Numeric Keypad Problem
107. The Painters Partition Problem
108. Boolean Parenthesization Problem
109. Number of Palindromic Paths In A Matrix
110. Maximum Sum Rectangle In a 2D Matrix
111. Largest Rectangular SubMatrix With Zero Sum
112. Largest Rectangular SubMatrix With Equal Number of 1s and 0s
113. Print Maximum Number of A's Using 4 Keys
114. Maximum Profit By Buying And Selling A Share At Most Twice
115. Maximum Profit By Buying And Selling A Share At Most K Times
116. Maximum Size Rectangle Of All 1s
117. Count Number of BSTs - Catalan Number
118. Maximize Expression A[j] - A[i] + A[l] - A[k]
119. Minimum Cost Polygon Triangulation
120. Minimum Possible Size of Array With Given Rules For Removing Elements
121. Longest Arithmetic Progression
122. Probability of Knight to Remain In The Chessboard
123. Number of Subsequences of The Form a^i b^j c^k
124. Check If All People Can Vote On Two Machines
125. Number of Subsequences In A String Divisible By N
126. Highway Billboard Problem
127. Longest Subseq Adjacent Diff01
128. Maximum Weight Transformation of A Given String
129. String Interleaved of Two Other String
130. Weighted Job Scheduling
131. Burst Balloon [Leetcode #312]
132. Range Sum Query 2D - Immutable [Leetcode #304]
133. Maximum Subsquare With Sides As X
134. Maximize Binary Matrix By Filpping Submatrix Once
135. Ways To Arrange Balls Such That Adjacent Balls Are of Different Types
136. Ways of Transforming One String To Another By Removing Characters
137. Maximum Subarray Sum Excluding Certain Elements
138. Maximum Points From Top Left To Bottom Right And Return Back
139. Longest Geometric Progression
140. Count AP (Arithmetic Progression) Subsequences In An Array
141. All Ways To Add Parenthesis For Evaluation
142. Minimum Cost To Sort Strings Using Reversals
143. Largest Minimum Sum Split Subarray

📘 Sorting Algorithms

• Merge Sort - O(nlgn)
• QuickSort - Θ(nlgn)
• Heap Sort - O(nlgn)
• Tim Sort 📘 - O(nlgn)
• Bubble Sort - O(n²)
• Insertion Sort - O(n²)
• Shell Sort - O(n²)
• Counting Sort - O(n + k)
• Bucket Sort - Θ(n + k)
• Radix Sort - O(d*n)

📘 Graph Theory

• Adjacency List Representation, Adjacency List Representation 2
• BFS - O(V+E)
  • Shortest Path In Unweighted Graph - O(V+E)
  • Shortest Path On A Grid - O(V+E)
• DFS - O(V+E)
  • ConnectedComponents - O(V+E)
  • TransitiveClosure - O(V+E)
• Topological Sorting - O(V+E)
• Cycle Detection
  • In Directed Graph - Using DFS - O(V+E)
  • In Undirected Graph - Using DFS - O(V+E)
  • In Undirected Graph - Using Union Find - O(E)
• Connected Components - Using Union Find - O(E)
• Single-Source Shortest Paths Algorithms
  • The Bellman-Ford Algorithm - O(VE)
  • Dijkstra's Algorithm - O((E+V)*lgV)
  • Shortest path in a DAG - O(V+E)
  • Longest path in a DAG - O(V+E)
• All-Pair Shortest Path: Floyd-Warshall Algorithm - O(V³)
• Bridges In Undirected Graph - O(V+E)
• Articulation Points In Undirected Graph - O(V+E)
• Strongly Connected Components
  • Tarjan’s Algorithm - O(V+E)
  • Kosaraju’s Algorithm - O(V+E)
• Travelling Salesman Problem
  • Brute-Force Approach - O(n!)
  • DP Iterative Approach - O(n²2ⁿ)
  • DP Recursive Approach - O(n²2ⁿ)
• Eulerian Path (Directed Graph) - O(V+E)
• Minimum Spanning Trees
  • Kruskal's Algorithm Using Union Find - O(ElgE)
  • Kruskal's Algorithm Using Union Find - Lazy Sorting Using Priority Queue - O(ElgE)
  • Prim's Algorithm For MST - O(ElgE)

Network Flow

• Max flow, Min cut (Ford-Fulkerson using DFS, adjacency list) - O(fE)
• Max flow, Min cut (Ford-Fulkerson using DFS, adjacency matrix) - O(fV²)
• Maximum Cardinality Bipartite Matching (Using Ford-Fulkerson DFS based Max Flow) - O(nE)
• [Problem]: Mice And Owls (Bipartite Matching)
• [Problem]: Elementry Math (Bipartite Matching)
• Bipartite graph verification (adjacency list, DFS) - O(V+E)
• Max flow, Min cut (Edmonds-Karp, adjacency list) - O(VE²)
• Max flow, Min cut (Capacity scaling, adjacency list) - O(E²lgU)
• Max flow, Min cut (Dinic's, adjacency list) - O(EV²), O(E√V) for bipartite graphs