Categories
Algorithms

Strongly Connected Component using Tarjan’s Algorithm

Kosaraju’s vs Tarjan’s Kosaraju’s algorithm finds the Topological Sorting of the original directed graph. For this, it uses DFS. Next it reverses the graph and runs DFS on the topologically sorted vertices. So it takes two DFS though the time complexity is O(|V|+|E|). Tarjan’s algorithm, on the other hand, only uses one DFS but uses […]

Categories
System

Spring Boot and Angular JS Application Development

Installing Environment Setup PostgreSQL Database Server We are going to show how to install PostgreSQL database on a Debian Linux system. $ sudo apt-get install postgresql Check status $ /etc/init.d/postgresql status Add password for the postgress account $ sudo -u postgres psql postgres psql (9.5.10) Type “help” for help. postgres=# \password postgres Enter new password: […]

Categories
Algorithms

LeetCode#75: Sort Color using Three-way Partitioning

The Sort Color problem expects to sort the array with values {0, 1, 2}. This can be done in a typical sorting algorithm in O(nlogn) time. A better approach is to use three-way partitioning of the array. Generic three-way partitioning Below the threeWayPartitionSort() method splits the given an array, [3,2,0,2,1,1,0,-1], into three parts, where values […]

Categories
Algorithms

LeetCode: Find Peak Element Solution

The Find Peak Element problem can be solved using a linear search in O(n) time and O(1) space. but it can be even better to solve it by binary search in O(log n) time complexity. But there can be two cases for binary search solution, the recursive solution creates stacks for each call and thus […]

Categories
Algorithms

Understanding Quick Sort and QuickSelect using Hoare Partition

This class implements a QuickSort algorithm using Hoare Paritioning scheme. This partitionining scheme is slightly harder to implement but is more efficient than the Lamuto partitioning scheme as it does three times fewer swaps on average [Wikipedia]. Avg Time-Complexity: O(nlogn) Worst Time-Complexity: O(n^2) Space complexity: O(1) Understanding Hoare Partition Intuitively After spending quite some on […]

Categories
Uncategorized

Merge Sort (Draft)