Named-Algo-Ds

Problem To estimate π using the Monte Carlo method, we’ll utilize the concept of randomly generating points within a square and determining how many fall inside a quarter circle. Monte Carlo Method Lets do the setup: Imagine a square with side length 2 centered at the origin, with coordinates ranging from (-1, -1) to (1, 1). Inside this square, there is a quarter circle of radius 1, also centered at the origin. The area of the square is 4 (since side length is 2), and the area of the quarter circle is (πr^2 / 4 = π/4) (since r=1). i.e. Let B be area of square, and A be area of circle $$ B = 4r^2 $$ ...

Floyd’s Cycle-Finding Algorithm Basic Algo Floyd Cycle Algorithm states that: Traverse linked list using two pointers. Move one pointer(slow_p or tortoise or walker) by one and another pointer(fast_p or hare or runner) by two. If these pointers meet at the same node then there is a loop. If pointers do not meet then linked list doesn’t have a loop. This is also called tortoise and hare approach. ...

Refer the problem statement: Maximum Subarray Sum Let us try to understand how Kadane’s Algorithm work. This solution is similar to sliding window in a way. Pseudocode For at-least 1 non-negative numbers Here’s the pseudocode for Kadane’s algorithm based on your template, designed to handle arrays with non-negative sums: # Start maxGlobal <- 0 maxCurrent <- 0 # Loop over array for i from 0 to n-1 do maxCurrent <- maxCurrent + a[i] # If maxCurrent drops below 0, reset it to 0 if maxCurrent < 0 then maxCurrent <- 0 end if # Update maxGlobal if we've found a new maximum if maxGlobal < maxCurrent then maxGlobal <- maxCurrent end if end for ...

Problem Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Definition Majority Element: If an element appears more than n/2 times in array where n is the size of the array. Examples int [] arrA = {1,3,5,5,5,5,4,1,5}; Output: Element appearing more than n/2 times: 5 int []arrA = {1,2,3,4}; Output: No element appearing more than n/2 times ...

Problem Given an array of integer write an algorithm to find the majority element in it (if exist). Boyer Moore Majority Vote Algorithm We have already seen the problem and some solutions - Majority Element 1 In this article we will see O(n) solution with constant extra space. As per above algorithm we can divide out implementation into two parts First iteration – Find the element which could be a majority element. Second iteration – check the element(found in first iteration) count is greater than n/2 First Iteration – Find the Element Which Could Be a Majority Element Iterate through array and maintain the count of majority_element.(starts with first element in the array.) If next element is same then increment the count If next element is not same then decrement the count. If count becomes zero then majority_element = current element, count =1. After the first iteration majority_element will be the candidate which might have the count > n/2. Second Iteration – Check the Element (found in First iteration) Count is Greater Than n/2 Iterate through array and get the count of element found in first step. If count is >n/2 then print it. If count is less than n/2 then ignore it, array does not have majority element. Complexity ⏰ Time complexity: O(n) 🧺 Space complexity: O(1) Code Java public int majorityElement(int[] arrA) { int size = arrA.length; if (size == 0) return; int majorityElement = arrA[0]; int count = 1; for (int i = 1; i<size; i++) { if (majorityElement == arrA[i]) { count++; } else if (count == 0) { majorityElement = arrA[i]; count = 1; } else { count--; } } //check if majorityElement is appearing more than n/2 times count = 0; for (int i = 0; i<size; i++) { if (arrA[i] == majorityElement) { count++; } } if (count > size / 2) return majorityElement; else return -1; } ...

Introduction The Floyd-Warshall algorithm is a classic algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. It’s especially useful for dense graphs and can handle both positive and negative edge weights (though not negative cycles). Algorithm Initialization: Create a distance matrix dist where dist[i][j] is the initial weight of the edge from vertex i to vertex j, or infinity if no edge exists. Set dist[i][i] = 0 for all vertices i. Dynamic Programming Update: For each intermediate vertex k, update the distance matrix to consider paths that pass through vertex k. For each pair of vertices (i, j), compute if a shorter path exists by going through k: if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } Result: After processing all vertices, dist[i][j] will contain the shortest path distance from vertex i to vertex j. Pseudocode function floydWarshall(graph): dist = matrix of size VxV, initially filled with graph weights (or infinity if no edge exists) for each vertex v: dist[v][v] = 0 for each intermediate vertex k: for each source vertex i: for each destination vertex j: if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist ...

Problem Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string We have already seen simple O(n^2) solution here - Longest Palindromic Substring Problem, but now lets look at Manacher’s Algorithm, which help us find the solution in linear time. Manacher’s Algorithm #TODO complete this

Can we perform inorder traversal on a binary tree without using recursion or a stack, while also keeping the space complexity constant? This is where Morris traversal comes in. We have seen inorder traversal of binary tree here - Binary Tree Traversal - Inorder. The iterative version involves stack. Now lets see Morris Traversal. The idea of Morris Traversal is based on Threaded Binary Tree. This approach achieves inorder traversal by establishing temporary links within the tree itself. The data is then printed by following these links, and finally, the tree structure is restored to its original state. ...

The difference between the two is that they do different things: Algorithm Input Output Time Space FISHER-YATES SHUFFLE n elements A list containing all n elements in a random order O(n) O(n) RESERVOIR SAMPLING n elements and integer k A set containing k of the n elements, selected randomly O(n) O(k) Fisher Yates| n elements | a list containint all n elements in random order| O(n) | O(n) ...

Algorithm to find kth largest element from an unsorted array in linear time. Algorithm If the number of elements in an array is large .Divide the array into arrays each with 5 elements ⇨ n/5 arrays. Compute Median of all arrays of 5 elements. This can be done by sorting each group and taking middle element. This results in time complexity of n/5 * 5log5. (Sorting each group takes 5log5, and we have n/5 arrays) All the computed medians from each sub-array are then collected into a new, smaller array. Now, compute median of this array Use this Median as Pivot in QuickSelect Median > half of these n/5 group medians. So median > n/10 medians. ...