File: README.md
The Algorithms - Java
You can run and edit the algorithms, or contribute to them using Gitpod.io (a free online development environment) with a single click.
All algorithms are implemented in Java (for educational purposes)
These implementations are intended for learning purposes. As such, they may be less efficient than the Java standard library.
Contribution Guidelines
Please read our Contribution Guidelines before you contribute to this project.
Algorithms
Our directory has the full list of applications.
File: src/main/java/com/thealgorithms/strings/zigZagPattern/README.md
About
convert string into a zig-zagged string
for example :
string = "123456789" , numRows = 3
ans = "159246837"
explanation
1 5 9
2 4 6 8
3 7
string = "HelloWorldKotlin" , k = 4
ans = "HoteWrollolKildn"
explanation
H o t
e W r o l
l o l K i
l d nworking
if string size is smaller than numRows or numRows is smaller than 2
than we can return string because it will make no changes to string.
If not than
we initiate three variable depth which is equalvalent to numRows ,
height which starts with 1 and start with starting index of string.
than we generate spaces to skip using formula 2 + (( n - 1 ) * 2 )
for both height and depth
with each iteration we decrement depth and increate height and start
by one also we keep contantating character on to new string with first
depth spaces and later height spaces that we generated using formula
if not zerobeats 80% of submission on leetcode
File: src/main/java/com/thealgorithms/datastructures/lists/README.md
Linked List
Description
LinkedList is a data structure in which data is stored in a linear manner. It usually contains a data field and a link to the memory location of the next node.
Structure
class LinkedList<E>{
E value;
LinkedList next;
}The next variable points to the next node in the data structure and value stores the data. Any number of nodes can be linked in this manner. The structure will be:
Properties
- Linked list does not provide indexing like an array. For accessing a node at position
p, θ(p) nodes need to be accessed. - Main advantage of linked list is addition and removal of nodes near the end and beginning of lists. It can be done just by updating the link (O(1) time)
- Unlike an array, its size is not predefined. So any number of nodes can be appended.
File descriptions:
CircleLinkedList.java: A circular linked list where next pointer of last node points to first node of linked list.SinglyLinkedList.java: The classic case of single links.CountSinglyLinkedListRecursion.java: Recursively counts the size of a list.CreateAndDetectLoop.java: Create and detect a loop in a linked list.DoublyLinkedList.java: A modification of singly linked list which has aprevpointer to point to the previous node.MergeKSortedLinkedlist.java: Merges K sorted linked list with mergesort (mergesort is also the most efficient sorting algorithm for linked list).RandomNode.java: Selects a random node from given linked list and displays it.SkipList.java: Data Structure used for storing a sorted list of elements with help of a Linked list hierarchy that connects to subsequences of elements.TortoiseHareAlgo.java: Finds the middle element of a linked list using the fast and slow pointer (Tortoise-Hare) algorithm.
File: src/main/java/com/thealgorithms/datastructures/heaps/Readme.md
HEAP DATA STRUCTURE
A Heap is a special Tree-based data structure in which the tree is a complete binary tree.
Complete Binary Tree
A complete binary tree is a binary tree
in which all the levels except the last level, i.e., leaf node should be completely filled, and all the nodes should be left-justified.
10
/ \
20 30
/ \
40 50
COMPLETE BINARY TREETypes of Heap
Generally, Heaps can be of two types:
Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
10
/ \
20 30
/ \ / \
40 50 60 70
MIN HEAP70
/ \
50 60
/ \ / \
40 30 10 20
MAX HEAPMin Heap Construction Algorithm
Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is more than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.Add 15
10 10 10
/ \ / \ / \
20 30 ------> 20 30 ------> 20 15
/ \ / \ / / \ /
40 50 40 50 15 40 50 30Min Heap Deletion Algorithm
Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is more than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.Delete 10
10 50 20 20
/ \ / \ / \ / \
20 30 ------> 20 30 ------> 50 30 ------> 40 30
/ \ / / /
40 50 40 40 50Time Complexity (Min Heap)
| Operations | Sorted Array | UnSorted Array | Heap |
|---|---|---|---|
| Add | O(N) | O(1) | O(logN) |
| Delete Minimum | O(N) | O(N) | O(logN) |
| Get Minimum | O(1) | O(N) | O(1) |
Applications of Heap Data Structure
Heapsort: Heapsort algorithm has limited uses because Quicksort is better in practice. Nevertheless, the Heap data structure itself is enormously used.
Priority Queues: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time. Binomoial Heap and Fibonacci Heap are variations of Binary Heap. These variations perform union also in O(logn) time which is a O(n) operation in Binary Heap. Heap Implemented priority queues are used in Graph algorithms like Prim’s Algorithm and Dijkstra’s algorithm.
Order statistics: The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array.
File: src/main/java/com/thealgorithms/datastructures/hashmap/Readme.md
HASHMAP DATA STRUCTURE
A hash map organizes data so you can quickly look up values for a given key.
Note: The term “hash map” refers to the data structure concept, while
HashMaprefers specifically to Java’s implementation.
Strengths:
- Fast lookups: Lookups take O(1) time on average.
- Flexible keys: Most data types can be used for keys, as long as they're hashable.
Weaknesses:
- Slow worst-case: Lookups take O(n) time in the worst case.
- Unordered: Keys aren't stored in a special order. If you're looking for the smallest key, the largest key, or all the keys in a range, you'll need to look through every key to find it.
- Single-directional lookups: While you can look up the value for a given key in O(1) time, looking up the keys for a given value requires looping through the whole dataset—O(n) time.
- Not cache-friendly: Many hash table implementations use linked lists, which don't put data next to each other in memory.
Time Complexity
| AVERAGE | WORST | |
|---|---|---|
| Space | O(n) | O(n) |
| Insert | O(1) | O(n) |
| Lookup | O(1) | O(n) |
| Delete | O(1) | O(n) |
Internal Structure of HashMap
Internally HashMap contains an array of Node and a node is represented as a class that contains 4 fields:
- int hash
- K key
- V value
- Node next
It can be seen that the node contains a reference to its object. So it’s a linked list.
Performance of HashMap
The performance of HashMap depends on 2 parameters which are named as follows:
- Initial Capacity
- Load Factor
Initial Capacity: It is the capacity of HashMap at the time of its creation (It is the number of buckets a HashMap can hold when the HashMap is instantiated). In Java, it is 2^4=16 initially, meaning it can hold 16 key-value pairs.
Load Factor: It is the percent value of the capacity after which the capacity of Hashmap is to be increased (It is the percentage fill of buckets after which Rehashing takes place). In Java, it is 0.75f by default, meaning the rehashing takes place after filling 75% of the capacity.
Threshold: It is the product of Load Factor and Initial Capacity. In Java, by default, it is (16 * 0.75 = 12). That is, Rehashing takes place after inserting 12 key-value pairs into the HashMap.
Rehashing : It is the process of doubling the capacity of the HashMap after it reaches its Threshold. In Java, HashMap continues to rehash(by default) in the following sequence – 2^4, 2^5, 2^6, 2^7, …. so on.
If the initial capacity is kept higher then rehashing will never be done. But keeping it higher increases the time complexity of iteration. So it should be chosen very cleverly to increase performance. The expected number of values should be taken into account to set the initial capacity. The most generally preferred load factor value is 0.75 which provides a good deal between time and space costs. The load factor’s value varies between 0 and 1.
Note: From Java 8 onward, Java has started using Self Balancing BST instead of a linked list for chaining.
The advantage of self-balancing bst is, that we get the worst case (when every key maps to the same slot) search time is O(Log n).Java has two hash table classes: HashTable and HashMap. In general, you should use a HashMap.
While both classes use keys to look up values, there are some important differences, including:
- A HashTable doesn't allow null keys or values; a HashMap does.
- A HashTable is synchronized to prevent multiple threads from accessing it at once; a HashMap isn't.
When Hash Map operations cost O(n) time?
Hash collisions: If all our keys caused hash collisions, we'd be at risk of having to walk through all of our values for a single lookup (in the example above, we'd have one big linked list). This is unlikely, but it could happen. That's the worst case.
Dynamic array resizing: Suppose we keep adding more items to our hash map. As the number of keys and values in our hash map exceeds the number of indices in the underlying array, hash collisions become inevitable. To mitigate this, we could expand our underlying array whenever things start to get crowded. That requires allocating a larger array and rehashing all of our existing keys to figure out their new position—O(n) time.
File: src/main/java/com/thealgorithms/datastructures/graphs/README.md
Graphs
Graph is a useful data structure for representing most of the real-world problems involving a set of users/candidates/nodes and their relations. A graph consists of two parameters:
V = a set of vertices
E = a set of edgesEach edge in E connects any two vertices from V. Based on the type of edge, graphs can be of two types:
Directed: The edges are directed in nature, which means that when there is an edge from node
AtoB, it does not imply that there is an edge fromBtoA. An example of a directed edge graph is the follow feature of social media. If you follow a celebrity, it doesn't imply that they follow you.Undirected: The edges don't have any direction. So if
AandBare connected, we can assume that there is an edge from bothAtoBandBtoA. For example, in a social media graph, if two persons are friends, it implies that both are friends with each other.
Components of a Graph
Vertices: Vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertex or nodes. Every node/vertex can be labeled or unlabelled.
Edges: Edges are used to connect two nodes of the graph. They can be an ordered pair of nodes in a directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be labeled/unlabeled.
Graphs are used to solve many real-life problems. Graphs are used to represent networks. The networks may include paths in a city, telephone network, or circuit network. Graphs are also used in social networks like LinkedIn, Facebook. For example, on Facebook, each person is represented with a vertex (or node). Each node is a structure and contains information like person id, name, gender, locale, etc.
Graph Representation
Graph can be represented in the following ways:
Set Representation: Set representation of a graph involves two sets: Set of vertices V = {V1, V2, V3, V4} and set of edges E = {{V1, V2}, {V2, V3}, {V3, V4}, {V4, V1}}. This representation is efficient for memory but does not allow parallel edges.
Sequential Representation: This representation of a graph can be represented by means of matrices: Adjacency Matrix, Incidence matrix, and Path matrix.
Adjacency Matrix: This matrix includes information about the adjacent nodes. Here, aij = 1 if there is an edge from Vi to Vj; otherwise, it's 0. It is a matrix of order V×V.
Incidence Matrix: This matrix includes information about the incidence of edges on the nodes. Here, aij = 1 if the jth edge Ej is incident on the ith vertex Vi; otherwise, it's 0. It is a matrix of order V×E.
Path Matrix: This matrix includes information about the simple path between two vertices. Here, Pij = 1 if there is a path from Vi to Vj; otherwise, it's 0. It is also called the reachability matrix of graph G.
Linked Representation: This representation gives information about the nodes to which a specific node is connected, i.e., adjacency lists. This representation gives the adjacency lists of the vertices with the help of arrays and linked lists. In the adjacency lists, the vertices connected to the specific vertex are arranged in the form of lists that are connected to that vertex.
Real-Time Applications of Graph
Graphs are used to represent the flow of control in computers.
Graphs are used in social networking sites where users act as nodes, and connections between them act as edges.
In an operating system, graphs are used as resource allocation graphs.
Graphs are used in Google Maps to find the shortest route.
Graphs are also used in the airline system for effective route optimization.
In state transition diagrams, the graph is used to represent states and their transitions.
In transportation, graphs are used to find the shortest path.
In circuits, graphs can be used to represent circuit points as nodes and wires as edges.
Graphs are used in solving puzzles with only one solution, such as mazes.
Graphs are used in computer networks for Peer to Peer (P2P) applications.
Graphs, basically in the form of DAG (Directed Acyclic Graph), are used as an alternative to blockchain for cryptocurrency. For example, cryptocurrencies like IOTA and Nano are mainly based on DAG.
Advantages of Graph
Using graphs, we can easily find the shortest path, neighbors of the nodes, and many more.
Graphs are used to implement algorithms like DFS and BFS.
They are used to find minimum spanning trees, which have many practical applications.
Graphs help in organizing data.
Because of their non-linear structure, graphs help in understanding complex problems and their visualization.
Disadvantages of Graph
Graphs use lots of pointers, which can be complex to handle.
They can have large memory complexity.
If the graph is represented with an adjacency matrix, then it does not allow parallel edges, and multiplication of the graph is also difficult.
Representation
- Adjacency Lists: Each node is represented as an entry, and all the edges are represented as a list emerging from the corresponding node. So, if vertex 1 has edges to 2, 3, and 6, the list corresponding to 1 will have 2, 3, and 6 as entries. Consider the following graph:
0: 1-->2-->3
1: 0-->2
2: 0-->1
3: 0-->4
4: 3It means there are edges from 0 to 1, 2, and 3; from 1 to 0 and 2, and so on.
- Adjacency Matrix: The graph is represented as a matrix of size |V| x |V|, and an entry 1 in cell (i, j) implies that there is an edge from i to j. 0 represents no edge. The matrix for the above graph:
0 1 2 3 4
0 0 1 1 1 0
1 1 0 1 0 0
2 1 1 0 0 0
3 1 0 0 0 1
4 0 0 0 1 0
###Graph Terminologies
Degree of a vertex: Number of edges that are incident at a vertex.
Weighted graph: A graph that has weights assigned for each of the edges (used in cases such as shortest path problems).
Connected components: A set of vertices that can reach others from it but not to those outside this connected component.
Cycle: A path that begins and ends at the same vertex.
Bipartite Graph: A graph whose vertices can be partitioned into two disjoint sets, with every edge connecting a vertex in one set to a vertex in the other set.
###Graph Algorithms
Breadth-First Search: It explores neighbors in layer after layer and applies on shortest path problems for unweighted graphs.
Depth-First Search (DFS): It continues moving up as far along each branch as possible before backtracking. DFS is typically used for traversing all nodes and testing connectivity.
Dijkstra's Algorithm: This algorithm finds the shortest path from a single starting vertex to all other vertices in a weighted graph.
Prim's and Kruskal's Algorithm: To find the minimum spanning tree.
Bellman-Ford Algorithm: This algorithm solves shortest path problems even when there are negative weights.
Graph Types
Multigraphs: Graphs with more edges between the same set of vertices.
Complete Graphs: A graph in which there is a unique edge between each pair of vertices.
Planar Graphs: A graph that can be drawn in a plane such that no two edges cross.
###Graph Algorithm Applications
Google Maps (Dijkstra's Algorithm): How maps apps find shortest routes.
Job Scheduling: Topological Sort A real application of DAG (Directed Acyclic Graph) to manage the dependency of jobs between tasks.
Web Crawling: How to use BFS for web crawlers to index pages in search engines.
Big-O Complexity of Graph Operations
Adjacency List vs Adjacency Matrix : Provide comparison tables of time complexity for operations such as addition of an edge, checking if an edge exists, etc.
BFS and DFS Complexity : Describe their computational cost
###Common Graph Problems
Graph Coloring
Finding Bridges and Articulation Points
Finding Strongly Connected Components
Maximum Flow (Ford-Fulkerson algorithm)
---
## File: src/main/java/com/thealgorithms/datastructures/queues/README.md
# Queue
- The Queue interface is present in the `java.util` package.
- It is an ordered list of objects that follows the **FIFO** (First-In-First-Out) principle.
## Characteristics of a Queue
- The Queue is used to insert elements at the end of the queue and removes elements from the beginning of the queue.
- It supports all methods of Collection interface including insertion, deletion etc.
- LinkedList, ArrayBlockingQueue and PriorityQueue are the most commonly used implementations.
## Types Of Queue:-
- **FIFO Queue (First-In-First-Out):** This is the most common type of queue where the first item added is the first one to be removed. It follows a strict order of insertion and removal.
- **Priority Queue:** Elements in this queue are assigned priorities, and the item with the highest priority is dequeued first. It doesn't strictly follow the FIFO order.
- **Double-ended Queue (Deque):** A queue that allows elements to be added and removed from both ends. It can function as both a FIFO queue and a LIFO stack.
- **Circular Queue:** In this type, the last element is connected to the first element, forming a circular structure. It's often used for tasks like managing memory buffers.
- **Blocking Queue:** Designed for multithreaded applications, it provides thread-safety and blocking operations. Threads can wait until an element is available or space is free.
- **Priority Blocking Queue:** Similar to a priority queue but thread-safe, it allows multiple threads to access and modify the queue concurrently while maintaining priority.
- **Delay Queue:** Used for scheduling tasks to run after a specific delay or at a certain time. Elements are removed from the queue when their delay expires.
## Declaration
`Queue<Obj> queue = new PriorityQueue<Obj>();`
## Important operations
| Operations | Description |Time Complexity
| ----------- | ----------- |-----------
|Enqueue|Adds an item to the queue|O(1)
|Dequeue|Removes an item from the queue|O(1)
|Front|Gets the front item from the queue|O(1)
|Rear|Gets the last item from the queue|O(n)
## Enqueue
It adds an item to the rear of the queue.
For example: If we have `1, 2, 3, 4, 5` in queue, and if we call Enqueue(8),
`8` will be added to last index of queue -> `1, 2, 3, 4, 5, 8`.
## Dequeue
It removes an item to the front of the queue.
For example: If we have `1, 2, 3, 4, 5` in queue, and we call Dequeue(),
`1` will be removed from front of queue and returned -> `2, 3, 4, 5`.
## Front
It returns an item to the front of the queue.
For example: If we have `1, 2, 3, 5` in queue, and we call Front(),
`1` will be returned (without removing it from the queue).
## Rear
It returns an item to the rear of the queue.
For example: If we have `1, 2, 3, 5` in queue, and we call Rear(),
`5` will be returned (without removing it from the queue).
# Real Life Applications
`Task Scheduling in Operating Systems:`
Processes in a multitasking system are often scheduled using queues. For example, the ready queue contains processes ready to be executed.
`Multi-threaded Programming:`
Queues are often used to facilitate communication and synchronization between different threads.
`Breadth-First Search (BFS) in Graphs:`
Queues are used in algorithms like BFS to explore a graph level by level.
---
## File: src/main/java/com/thealgorithms/datastructures/stacks/README.md
# STACK
- Stack is an ADT (abstract data type) that is a collection of elements where items are added and removed from the end, known as the "top" of the stack.
- Stack works on the principle of _LIFO_ (Last In First Out), it means that the last item added to the stack will be the first item to be removed.
## Declaration
`Stack<Obj> stack=new Stack<Obj>();`
# Functionalities
Stack is based on two functions (methods)-
## push(element)
It adds "element" to the top of the stack.
For example: If we have `1, 3, 5` in stack, and we call push(9),
`9` will be added to last index of stack -> `1, 3, 5 , 9`.
## peek() or top()
It returns element at the top of the stack.
For example: If we have `1, 3, 5` in stack, and we call peek(),
`5` will be returned (without removing it from the stack).
## pop()
It removes the last element (i.e. top of stack) from stack.
For example: If we have `1, 3, 5 , 9` in stack, and we call pop(),
the function will return `9` and the stack will change to `1, 3, 5`.
# Real Life Applications
- `Undo mechanisms:`
Many software applications use stacks to implement an "undo" feature.
- `Browser history:`
The "back" button in a web browser is implemented using a stack, allowing users to navigate through previously visited pages.
- `Function calls and recursion:`
The computer's call stack keeps track of function calls, allowing programs to remember where to return after a function finishes execution.
---
## File: src/main/java/com/thealgorithms/datastructures/trees/README.md
## Tree
### Description
Tree is a data structure where the data is organized in a hierarchial structure. There should be one root node (which does not have any parent) and all subsequent nodes are represented as children of the root node and its children. If a node has at least one child, it is called `internal` node and nodes with no children are called `leaf` nodes.
### Basic Structureclass Tree
E value;
Tree left;
Tree right;
}
This basic structure is for a binary tree where each internal tree has at least one and at most two children. `left` and `right` represent the two children and `value` is the placeholder for data.
### Properties
1. Tree data structure gives the facility to organize data in a hierarchial structure
2. Tree nodes can be inserted in a sorted order which can be used for searching and inserting data in O(logN) time where N is the number of nodes.
### Types of Trees
1. **Binary Search Tree:** A binary tree where the elements are inserted in asorted order. Here the searching can be done in O(logN) time in (depending on the structure)
2. **AVL Tree and Red-Black Tree:** Binary search trees where the height is balanced. Here, searching is guaranteed to be in O(logN) time.
3. **Traversal algorithms:**
a. **BFS:** Breadth-first-search where all the children at each level are traversed at once.
b. **DFS:** Depth-first-search where the first discovered child is traversed first.
4. **MultiWay Search Tree:** Tree in sorted order, but more than two children in each internal node.
5. **Trie:** A character based multiway search tree where words can be retrieved based on their prefix. Useful for implementing prefix based search algorithm.