πData Structures and Algorithms
Implementation of most common data structures and algorithms in Java.
- π Linked Lists
- π Stack
- π Queue
- π Deque
- π Binary Search Tree
- π Hashtable
- π Union Find
- π Heap (Priority Queues)
- π Self-Balancing BSTs
- π Trie
- π Segment Tree
- π Fenwick Tree
- π LRU Cache
[Sorted: Easy To Hard]
- Fibonacci Numbers
- Ugly Numbers
- Super Ugly Numbers
- Tiling 2Xn Floor With 2X1 Tile
- Tiling NxM Floor With 1xM Tile
- Gold Mine Problem
- Max Path Sum
- Coin Change Problemπ₯
- Friends Pairing Problem
- Subset Sum Problem
- Perfect Sum Problemπ₯
- Subset Sum Divisible By M
- Change Making Problem
- Rod Cutting Problem
- Tiling With Dominoes
- Painting Fence Problem
- Assembly Line Scheduling
- Maximum Length Snake Sequence
- Even Length Binary Sequence
- Sequences Of Given Length
- Longest Common Subsequenceπ₯
- Longest Repeated Subsequence
- LCS of 3 Strings
- Longest Increasing Subsequenceπ₯
- Longest Bitonic Subsequence
- Maximum Sum Increasing Subsequence
- Maximum Sum Bitonic Subsequence
- Maximum Product Increasing Subsequence
- Product Subsequences Count
- Maximum Sum No Two Adjacent
- Maximum Sum No Three Adjacent
- Longest Subseq Adjacent Diff1
- Max Length Chain Pairs
- Path With Maximum Average Value
- Min Cost Path
- Max Path Sum Triangle
- Min Path Sum Triangle
- Maximum Sum Subarray - Kadaneβs Algorithmπ₯
- Maximum Size Square Sub Matrix
- Max Sum 2x1 Grid
- Max Path Sum With Jumps Under Div
- Min Jumps To Reach End
- Edit Distance
- Longest Common Substringπ₯
- Sum Of All Substrings
- Count Ways To Build Street
- Cover Distance
- Diff Ways To Sum
- 0-1 Knapsackπ₯
- Temple Offering Problem
- Egg Dropping Problem
- Dice Throw Problem
- Word Break Problemπ₯
- Box Stacking Problem
- Longest Palindromic Subsequence
- Count All Palindromic Subsequence
- Longest Palindromic Substring
- Count All Palindrome SubStrings
- Shortest Common Supersequence
- Longest ZigZag or Alternating Subsequence
- Maximum Sum ZigZag or Alternating Subsequence
- Minimum Number of Coins To Make a Change
- Possible Ways To Construct Buildings
- Number Different Ways To Reach End
- Count Number of Binary Strings Without Consecutive 1s
- Count Number of Paths With At Most k Turns
- Count Possible Decodings of Digit Sequence
- Number of Ways To Partition A Set Into k Subsets
- Count n Digit Numbers With Given Digit Sum
- Count Strings Formed Using a b c
- Count Numbers With Even Odd Digit Sum Difference of 1
- Maximum Profit From Sale of Wines
- Maximum Size Subset Sum
- Maximum Sum Subarray Removing At Most One Element
- K maximum sums of non-overlapping contiguous sub-arrays
- Maximum Product Subarray
- Maximum Dot Product of Two Arrays
- Minimum Initial Points to Reach Destination (Dungeon Game)π₯
- Minimum Insertions To Form Palindrome
- Minimum Number of Squares Sum to Given Number
- Remove Minimum Elements From Either Side
- Minimum Cells Required To Reach Destination
- Longest Increasing Circular Subsequence
- Longest Path In A Matrix With Given Constraints
- Count Distinct Subsequences
- Longest Consecutive Path In Matrix
- Length of longest subsequence of one string which is substring of another string
- Wildcard Pattern Matching
- Optimal Strategy For Game
- Number of Permutations With K Inversions
- Largest Divisible Pairs Subset
- Sum Of Digits In Numbers From 1 To N
- Number of Non Decreasing Numbers
- Catalan Number π
- Non-crossing lines to connect points in a circle
- Building Bridges
- Longest Substring Without Repeating Characters
- Longest Even Length Substring such that Sum of First and Second Half is same
- Partition Set To Subset Sum Minimum Diff
- Matrix Chain Multiplicationπ₯
- Minimum and Maximum values of an expression
- Optimal Binary Search Tree
- Regular Expression Matching
- Text Justification
- Palindrome Partitioning
- Mobile Numeric Keypad Problem
- The Painters Partition Problem
- Boolean Parenthesization Problem
- Number of Palindromic Paths In A Matrix
- Maximum Sum Rectangle In a 2D Matrix
- Largest Rectangular SubMatrix With Zero Sum
- Largest Rectangular SubMatrix With Equal Number of 1s and 0s
- Print Maximum Number of A's Using 4 Keys
- Maximum Profit By Buying And Selling A Share At Most Twice
- Maximum Profit By Buying And Selling A Share At Most K Times
- Maximum Size Rectangle Of All 1s
- Count Number of BSTs - Catalan Number
- Maximize Expression A[j] - A[i] + A[l] - A[k]
- Minimum Cost Polygon Triangulation
- Minimum Possible Size of Array With Given Rules For Removing Elements
- Longest Arithmetic Progression
- Probability of Knight to Remain In The Chessboard
- Number of Subsequences of The Form a^i b^j c^k
- Check If All People Can Vote On Two Machines
- Number of Subsequences In A String Divisible By N
- Highway Billboard Problem
- Longest Subseq Adjacent Diff01
- Maximum Weight Transformation of A Given String
- String Interleaved of Two Other String
- Weighted Job Scheduling
- Burst Balloon [Leetcode #312]
- Range Sum Query 2D - Immutable [Leetcode #304]
- Maximum Subsquare With Sides As X
- Maximize Binary Matrix By Filpping Submatrix Once
- Ways To Arrange Balls Such That Adjacent Balls Are of Different Types
- Ways of Transforming One String To Another By Removing Characters
- Maximum Subarray Sum Excluding Certain Elements
- Maximum Points From Top Left To Bottom Right And Return Back
- Longest Geometric Progression
- Count AP (Arithmetic Progression) Subsequences In An Array
- All Ways To Add Parenthesis For Evaluation
- Minimum Cost To Sort Strings Using Reversals
- Largest Minimum Sum Split Subarray
π Sorting Algorithms
- Merge Sort - O(nlgn)
- QuickSort - Ξ(nlgn)
- Heap Sort - O(nlgn)
- Tim Sort π - O(nlgn)
- Bubble Sort - O(n2)
- Insertion Sort - O(n2)
- Shell Sort - O(n2)
- 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(V3)
- 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(n22n)
- DP Recursive Approach - O(n22n)
- Eulerian Path (Directed Graph) - O(V+E)
- Minimum Spanning Trees
- Max flow, Min cut (Ford-Fulkerson using DFS, adjacency list) - O(fE)
- Max flow, Min cut (Ford-Fulkerson using DFS, adjacency matrix) - O(fV2)
- 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(VE2)
- Max flow, Min cut (Capacity scaling, adjacency list) - O(E2lgU)
- Max flow, Min cut (Dinic's, adjacency list) - O(EV2), O(EβV) for bipartite graphs