Minimum Spanning Tree (MST) used in prims algorithm
Goal: To connect all vertices in a graph with the minimum possible total edge weight, without forming any cycles.
Output: A tree that spans all vertices of the graph with the minimum sum of edge weights.
Shortest path
Goal: To find the shortest path between a specific pair of vertices in a graph, minimizing the sum of the edge weights along that path.
Output: A path (which may include some or all vertices) with the minimum possible total weight between two specific vertices.
Dijkstra Algorithm
Purpose: Finds the shortest path from a single source to all other vertices in a graph.
Applicability: Works only with graphs that have non-negative edge weights.
Woking:
Uses a greedy approach.
Iteratively selects the vertex with the smallest known distance, explores its neighbors, and updates their distances.
Once a vertex is processed, its shortest path is finalised.
Dijkstra’s algorithm is like breadth-first search (BFS), except we use a priority queue instead of a normal first-in-first-out queue. Each item’s priority is the cost of reaching it.
Note-Implementation is similar to Prim’s algorithm for minimum spanning tree.
Purpose: Also finds the shortest path from a single source to all other vertices, but can handle graphs with negative edge weights.
Applicability: Works with graphs that may have negative edge weights, and can also detect negative weight cycles (where a cycle’s total weight is negative).
Woking:
Uses a dynamic programming approach.
Iteratively relaxes all edges, meaning it updates the shortest path estimate for each edge based on its current known distance.
After V−1V-1V−1 iterations, it ensures that the shortest paths are found. If an additional relaxation improves any distance, it indicates a negative weight cycle.
Floyd-Warshall Algorithm
Purpose: Finds the shortest paths between all pairs of vertices in a graph.
Applicability: Works with both directed and undirected graphs, including those with negative edge weights.
Wokings:
Uses a dynamic programming approach.
Iteratively updates a distance matrix where each entry dist[i][j] represents the shortest path from vertex i to vertex j.
Considers each vertex as an intermediate point in the path and updates the matrix accordingly.
Prim’s Algorithm
Purpose: Finds the Minimum Spanning Tree (MST) of a connected, undirected graph. The MST is a subset of the edges that connects all vertices together, without any cycles, and with the minimum possible total edge weight.
Applicability: Works with weighted, undirected graphs. It requires that the graph be connected, meaning there must be a path between every pair of vertices.
A majority element is one that appears more than nums.length / 2 times.
Algorithm Proceeding-
First, choose a candidate from the given set of elements
if it is the same as the candidate element, increase the votes. Otherwise,
decrease the votes if votes become 0, select another new element as the new candidate.
public static int findMajorityElement(int[] nums) {
int majorityElement = 0;
int count = 0;
for (int num : nums) {
if (count == 0) {
majorityElement = num;
count = 1;
} else if (num == majorityElement) {
count++;
} else {
count--;
}
}
}
Kadane’s Algo
Kadane’s algorithm a popular dynamic programming algorithm, it is used for finding the maximum sum of a contiguous subarray in an array. it efficiently handles both positive and negative numbers.
Conditions/Cases to remember
does it handle empty array?[NA]
does it handle all -ve element, i.e what will be the ans in this case, since sum of 2 -ve is grater -ve number. [YES]
should we consider using 0 or arr[i] as substitution in code – Any works ,but corresponding initiation & iteration required.
It works by maintaining two variables:maxSoFar & maxEndingHere
maxSoFar stores the maximum sum of any contiguous subarray seen so far, and
maxEndingHere stores the maximum sum of any contiguous subarray ending at the current index.
public static int maxSubArraySum(int[] nums) {
int maxSoFar=Integer.MIN_VALUE;//final result initiated to min not 0, for cases where elements with -ve numbers would result in max being 0 -which is incorrect.
int maxEndingHere=0;
for(int i=0;i<nums.length;i++){
maxEndingHere=Math.max(nums[i]+maxEndingHere,nums[i]);
maxSoFar=Math.max(maxSoFar,maxEndingHere);
}
return maxSoFar;
}
Selection Sort is best when memory write operations are costly since it makes the minimum possible number of swaps compared to other two.
Insertion Sort is preferable for small or nearly sorted data.
Bubble Sort is typically used for educational purposes to demonstrate sorting techniques but is rarely used in practical applications due to its inefficiency.
Selection Sorting
Algorithm :
Iterate through the array to find the smallest (or largest) element.
Swap the found minimum (or maximum) element with the first element.
Move the boundary of the unsorted subarray by one element.
Repeat the process for the remaining unsorted portion of the array.
private static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
//optimisation used : outer loop used for swapping - internal for index tracking
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
Time Complexity: O(n²)
Space Complexity: O(1) (In-place sorting)
Bubble Sort
Algorithm :
Compare adjacent elements in the array.
Swap them if they are in the wrong order.
Continue doing this for each pair of adjacent elements until the array is fully sorted
.After each pass, the next largest element is in its correct position.
Repeat the process until no swaps are needed (the array is sorted).
private static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1; j++) {
if(arr[j]>arr[j+1]){
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}
Time Complexity: O(n²)
Space Complexity: O(1) (In-place sorting)
Insertion Sort
Algorithm :
Start from the second element, assume that the first element is already sorted.
Pick the next element and compare it with the elements in the sorted part.
Shift all elements in the sorted part that are greater than the current element to the right.
Insert the current element into its correct position.
Repeat the process until the entire array is sorted.
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1] that are greater than key to one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
Time Complexity: O(n²)
Space Complexity: O(1) (In-place sorting)
Quick Sort
Algorithm :
Choose a “pivot” element from the array.
Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
Recursively apply the same steps to the sub-arrays.
Combine the sub-arrays to get the sorted array.
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Recursively sort elements before partition
quickSort(arr, pi + 1, high); // Recursively sort elements after partition
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1); // Index of smaller element
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
Time Complexity:
Best Case: O(n log n)
Worst Case: O(n²) (occurs when the smallest or largest element is always chosen as the pivot)
Space Complexity: O(log n) (in-place sorting, though recursion stack takes
Merge Sort
Algorithm :
Divide the array into two halves.
Recursively sort each half.
Merge the two halves to create a sorted array.
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
// Sort first and second halves
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
// Merge the sorted halves
merge(arr, left, middle, right);
}
}
private static void merge(int[] arr, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
// Temporary arrays
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data to temp arrays
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[middle + 1 + j];
// Merge the temp arrays
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements of L[]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[]
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
// Call mergeSort with the full range of the array
mergeSort(arr, 0, arr.length - 1);
// Print the sorted array
System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
Search a sorted array by repeatedly dividing the search interval (Divide and conquer )in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.
Algorithm – We basically ignore half of the elements just after one comparison.
Compare x(element to be searched for) with the middle element.
If x matches with the middle element, we return the mid index.
Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half.
Else (x is smaller) recur for the left half.
Two approaches-
Iterative – tip – for simplicity of understanding go with this
Recursive (ignored as slightly complex to understand and implement )
Iterative approach –
int binarySearch(int arr[], int x)
{
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
Techglot 