divide and conquer

Min and Max element in array

In this article, we have explained how to use a Divide and Conquer approach to find the Minimum and Maximum element in array using the theoretically minimum number of comparisons.

divide and conquer

Skyline Problem

In this article, we have explained an efficient approach to solve the Skyline Problem using a Divide and Conquer algorithm.

Algorithms

In this article, we will discuss what is Divide and Conquer technique and how is it helpful. We will see various examples which uses the Divide and Conquer approach in their algorithms.

Algorithms

Majority element in sorted array

In this article, we will be learning how to find the majority element in a sorted array. This involve using Linear Search, Binary Search and a constant time algorithm.

divide and conquer

Find floor in sorted array

In this article, we are going to see various methods of finding the floor of a given number from a given sorted array. To solve this efficiently, the concept of Divide and Conquer / Binary Search is required.

Algorithms

Closest Pair of Points

In this article, we have explored different algorithms using which we can find the Closest Pair of Points in a given set of N points efficiently in O(N logN) time. This involves the idea of Divide and Conquer.

Algorithms

Median of Medians Algorithm

In this post, we explained the median of medians heuristic, its applications and usefulness as well as its limitations. Median of Medians Algorithm is a Divide and Conquer algorithm.

Algorithms

Find Peak Element in an Array

We have explained the problem of finding Peak Element in an Array along with different approaches to solve it efficiently.

Algorithms

Finding 2 elements with difference k in a sorted array

This article discusses how to check the existence of and find 2 elements with difference k in sorted array. We have explored 3 approaches and solved it in linear time O(N).

Algorithms

Find k-th smallest element using QuickSelect algorithm

Quickselect is an approach where we use divide and conquer and find the k th smallest element in an average O(N) time.

Algorithms

Multi Dimensional Divide and Conquer

In this article we will be discussing a research paper published in 1980 by Jon Louis Bentley. Generally we see algorithms that solve a single specific purpose, but in this paper we discuss multidimensional divide-and-conquer.

Algorithms

Number of paths with k edges using Dynamic programming and Divide and Conquer

Given a directed graph, we need to find the number of paths with exactly k edges from source u to the destination v. A brute force approach has time complexity which we improve to O(V^3 * k) using dynamic programming which we improved further to O(V^3 * log k) using a divide and conquer technique.

Algorithms

Find Maximum Subarray Sum using divide and conquer

We are interested in to find maximum subarray sum (contiguous) of given 1-D array. Array may contain negative and positive numbers which makes this a difficult problem. Brute force will take O(N^2) time while a divide and conquer approach will take O(N log N) time.

Algorithms

Centroid Decomposition of Tree

Centroid Decomposition is a divide and conquer technique which is used on trees. Given a tree with N nodes, a centroid is a node whose removal splits the given tree into a forest of trees, where each of the resulting tree contains no more than N/2 nodes.

Algorithms

Fibonacci Search

Fibonacci search is an efficient search algorithm based on divide and conquer principle using Fibonacci series that can find an element in the given sorted in O(log N) time complexity. It is better than Binary search as it is more cache friendly and uses only addition and subtraction operations.

convex hull

Divide and Conquer algorithm to find Convex Hull

Divide and Conquer algorithm to find Convex Hull. The key idea is that is we have two convex hull then, they can be merged in linear time to get a convex hull of a larger set of points. It requires to find upper and lower tangent to the right and left convex hulls C1 and C2

convex hull

Quick Hull Algorithm to find Convex Hull

Quickhull is a method of computing the convex hull of a finite set of points in the plane. It uses a divide and conquer approach. It was published by C. Barber and D. Dobkin in 1995. average case complexity is considered to be Θ(n * log(n))

Algorithms

Karatsuba Algorithm (for fast integer multiplication)

Karatsuba algorithm is a fast multiplication algorithm that uses a divide and conquer approach to multiply two numbers.