×
Home Discussions Write at Opengenus IQ
×
  • About
  • Track your progress
  • Deep Learning Projects
  • Python Projects
  • Join our Internship 🎓
  • RANDOM
  • 100+ Graph Algorithms
  • 100+ DP Problems
  • 50+ Linked List Problems
  • 50+ Array Problems
  • One Liner
  • 50+ Binary Tree problems
  • Home
  • Rust Projects

divide and conquer

A collection of 18 posts

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.

Purvak Baliyan
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.

Gifty Treesa Iju Gifty Treesa Iju
Algorithms

Divide and Conquer

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.

Harshul Nanda Harshul Nanda
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.

Gifty Treesa Iju Gifty Treesa Iju
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.

Rahul Kumar Yadav
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.

Joe Gorst Joe Gorst
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.

Erick Lumunge
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.

Fahd Agodzo Mohammed Fahd Agodzo Mohammed
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).

Varul Srivastava
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.

Rohit Topi
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.

K. Sai Drishya K. Sai Drishya
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.

Sadanand Vishwas Sadanand Vishwas
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.

Akshay Gopani Akshay Gopani
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.

Sadanand Vishwas Sadanand Vishwas
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.

Harshita Sahai Harshita Sahai
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

Pankaj Sharma Pankaj Sharma
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))

Pankaj Sharma Pankaj Sharma
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.

Olawale Dosunmu Olawale Dosunmu
OpenGenus IQ © 2023 All rights reserved â„¢ [email: team@opengenus.org]
Top Posts LinkedIn Twitter