If you are new to coding, Algorithms are the most important things that beginners to learn. They are step-by-step instructions that help solve problems efficiently. Understanding algorithms helps you think logically and improve problem-solving skills. Here are some of the must-know programming algorithms you must learn before your first coding interview.
25 Most Important Algorithms for Beginners
In this list, we will cover basic algorithms like “Bubble Sort” and advance to more complex ones like the “Binary Lifting” algorithm. So, here we go:
1) Bubble Sort
Bubble Sort algorithm represents the simplest method for sorting an array. Within this approach, adjacent numbers are continually swapped if they are in the incorrect order until the array becomes sorted. The time complexity of this sorting method is O(n^2) in the worst-case scenario.
If you are new to programming this might be the first sorting technique you will learn because it is easy to understand, and simple to code.
2) Counting Sort
Counting Sort is not a sorting technique; instead, it is used to count the frequency of each element. After finding the frequency, it will replace each element with its frequency. It takes O(n) time complexity and space complexity equal to the range of the numbers.
3) Merge Sort
The process behind Merge Sort breaks the problem into smaller components and resolves each one individually. It employs recursion, where the function is called for both the left and right halves. This recursive function further divides the segments into two halves. Once both segments are sorted, they are merged, resulting in a sorted array.
4) QuickSort
The QuickSort technique is based on divide and conquer. The concept involves selecting a pivot number and dividing the list into two parts: the left side comprises all numbers smaller than the pivot, while the right side consists of those greater than the pivot. This process is iterated until the list is sorted.
5) Binary Search
Binary search is a search algorithm utilized to find the position of an element in a sorted array.
A classic illustration of binary search is akin to using a dictionary, where words are organized alphabetically. To search for a specific word, the process involves dividing the book in half and subsequently searching to the left or right based on the word’s placement. This iterative process continues until the desired word is located.
6) Insertion Sort
In the process for Insertion Sort, we will examine the first element in the array and compare it with the second element. If the second element is less than the first, we will swap them. We will continue repeating this process until we achieve a sorted array. This process has a time complexity of O(n^2).
Now, let’s move from some basic algos, to something more advanced. These will help you solve many leetcode problems for competitive programming.
7) Sliding Window Algorithm
Sliding Window Algorithm is a wonderful technique for calculating the maximum sum of size k in an array or any modification thereof. The idea is to calculate the sum of the first k elements in the array, and instead of recalculating the next k elements, we add the next element and remove the (i-k) element from the sum. This is how we slide our window.
8) Floyd’s Cycle Detection Algorithm
The method involves the use of two pointers, each advancing at a different speed. The faster of the two is referred to as the fast pointer, while the slower one is known as the slow pointer.
This technique is employed to identify loops within a linked list structure. Should the fast pointer reach a NULL value at any juncture, it indicates the absence of a loop in the linked list.
Conversely, if the rapid and slow pointers converge at any stage, it signifies the presence of a loop within the list.
9) Divide and Conquer Algorithm
In the Divide and Conquer algorithm, we will break down the complex problem into smaller ones, solve these smaller problems, and then use these solutions to address the entirety of the issue. A prime example of the divide and conquer technique is merge sort, where we divide the array into progressively smaller portions.
10) Kadane’s Algorithm
The greedy algorithm utilized for determining the maximum sum of an array is known as the Kadane Algorithm. The brute force method involves traversing through each subarray to identify the maximum sum, resulting in a time complexity of O(n^2).
Conversely, in the Kadane Algorithm, the sum is accumulated in a variable until it becomes negative. Upon reaching a negative value, the variable is reset to 0, and the process of summing integers resumes while continuously updating the maximum sum.
11) Depth-First Search (DFS)
In DFS, we will first visit the root node and traverse all the nodes of a branch until we reach the leaf node of that branch.
Subsequently, we will backtrack along that branch and proceed to the next one. This process is iterated until all nodes are covered. It has a time complexity of O(n) and a space complexity of O(H), where n represents the total number of nodes in the tree and H denotes the height of the tree.
12) Breadth-First Search (BFS)
Breath-first search, or BFS, entails examining each node and its immediate level rather than traversing the graph/tree entirely. Two arrays, namely “visited” and “next,” are employed for this purpose. The “visited” array encompasses nodes already explored, while the “next” array holds the next-level nodes slated for exploration.
13) KMP Algorithm
This KMP algorithm is utilized to determine whether a specific string contains another string or not. The fundamental concept involves traversing the first string until it aligns with the other string. Upon encountering a discrepancy, rather than restarting the entire process, we leverage the already-matched characters to circumvent re-matching them.
14) Lowest Common Ancestor (LCA)
This algorithm to find the Lowest Common Ancestor is used to find the lowest common nodes between two distinct nodes. The basic idea is to store the path of each node in two arrays. Once stored, iterate over the arrays until the first mismatch is encountered. The time complexity for the above code is O(n).
15) Diameter of Binary Tree
The diameter of a binary tree is the longest path between any two leaf nodes of the binary tree, and it is not necessary to traverse through the root node. To determine this, we calculate the leaf node situated at the greatest depth from the root node.
Subsequently, from this node, we ascertain the node farthest away. These two nodes collectively establish the diameter of a binary tree.
16) 0/1 Knapsack
0/1 Knapsack is the basic dynamic programming algorithm, in which we either choose an element or do not choose one until the required condition is met. Among all the possible cases, we select the best one. We utilize an array to store the repeated values so that we do not have to recalculate them.
17) Matrix Chain Multiplication
The matrix chain multiplication problem is also known as partition DP. It partitions the array into two halves and similarly each part into other halves. After obtaining an answer from both halves, we derive the final answer by varying their order.
18) Dijkstra’s Algorithm
This Dijkstra algorithm calculates the shortest distance from one node to every other node in the graph. To accomplish this, we will utilize a priority queue to extract the node with the minimum weight, and a visited array to keep track of nodes already visited.
19) Kruskal’s Algorithm
The Kruskal’s algorithm is used to find the minimum spanning tree. Firstly, we sort all the edges in ascending order. Then, we continually add the edge with the minimum weight, ensuring it does not form a cycle.
20) Topological Sorting
In Topological Sorting, we need to print the nodes or find the order of nodes in their respective n degree. To achieve this, we will use a map to store the frequency of incoming edges for each vertex. After determining the frequency, we will continue iterating over the nodes with a frequency of 0 and decrease their child frequency by one.
21) Bellman-Ford Algorithm
Bellman-Ford algo is used to find the shortest distance from a given vertex to every other vertex.
This algorithm is superior to the Dijkstra algorithm as it can also detect negative cycles. In this , we initially set all the distances to infinity; over time, we continuously relax the edges v-1 times. If the distance is further reduced after v iterations, the graph contains a negative cycle.
22) Prim’s Algorithm
Prim’s algorithm is also used to find the minimum spanning tree. The only difference is that, unlike Kruskal, we select an arbitrary vertex and store all its adjacent nodes along with their weight in ascending order.
We proceed by removing edges one by one and checking if both vertices have already been visited; if they have, we move to the next node. Otherwise, we add this edge to our minimum spanning tree and proceed to its adjacent child. This process continues until all edges are visited.
23) Travelling Salesman Problem
This algorithm has become famous nowadays, with most startup companies posing questions based on it. In the Travelling Salesman problem, you are given a graph in which each vertex represents a house, with a salesman or delivery person stationed at one of these vertices.
You receive a set of inputs specifying the locations where the person needs to deliver items and ultimately return to the starting vertex. Your objective is to determine the minimum possible time required to accomplish this task.
24) Backtracking
Backtracking is the most common and frequently asked pattern in coding interviews. In this pattern, you have to keep visiting a direction until you reach the end of a dead end. After reaching the end/dead end, you have to backtrack to the previous element and proceed in the next direction. Keep visiting the nodes until you have explored all possible cases.
25) Union Find Algorithm
Union Find Algorithm is used to find the graph such that it will not form a loop or it will remove the extra edges to make the graph acyclic. It has 3 basic functions.
- The make function is used to assign a parent node and a size of 1 for that node.
- The find function determines the parent of the node.
- The union function is used to determine the union of two nodes.
Conclusion
These are the most important algorithms in coding for beginners. These range from bubble sort, which has a time complexity of O(n^2) for sorting, to merge sort, which has a time complexity of O(n log(n)). Taking the time to understand each of them will greatly aid in tackling most coding questions effortlessly.
