# Category: Divide and Conquer

## Find the local minima in a given array

Objec­tive:  Given an array of inte­ger write an algo­rithm to find the local min­ima. Local Min­ima: An ele­ment is con­sid­ered as local min­ima if it is less than both of its neigh­bors (if neigh­bors exist). Example:…

## Stock Single Sell Problem — O(n) Solution

Objec­tive:  Given an array rep­re­sents cost of a stock on each day. You are allowed to buy and sell the stock only once. Write an algo­rithm to max­i­mize the profit in sin­gle buy and sell. Example:…

## OR Largest Sum Contiguous Subarray Problem – Divide and Conquer">Maximum Subarray OR Largest Sum Contiguous Subarray Problem – Divide and Conquer

Objec­tive:  The max­i­mum sub­ar­ray prob­lem is the task of find­ing the con­tigu­ous sub­ar­ray within a one-dimensional array of num­bers which has the largest sum. Exam­ple: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5, 4}; Output:…

## Maximum difference between two elements where larger element appears after the smaller element

Objec­tive: Given an array A[], write an algo­rithm to find Max­i­mum dif­fer­ence between two ele­ments where larger ele­ment appears after the smaller ele­ment or in other words find A[i] and A[j] such that A[j]-A[i]…

## Merge Sort in a Linked list

Objec­tive: Given a Linked List, Sort it using merge sort. Exam­ple: ->9->3->4->2->5->1 Sorted List: ->1->2->3->4->5->9 Approach: Ref­er­ence : Merge Sort in array

## Find the first repeated element in an array by its index

Objec­tive: Given an array of inte­gers, find out the first repeated ele­ment. First repeated ele­ment means the ele­ment occurs atleast twice and has small­est index. Input: An Array Out­put: The first repeated ele­ment Exam­ples : Array…

## Inorder Successor in Binary Tree

Algo­rithms — Inorder Suc­ces­sor in Binary Tree Objec­tive: Given a Binary tree (Not binary Search Tree ), find the inorder suc­ces­sor of a node. What is Inorder Suc­ces­sor: Inorder suc­ces­sor of a node is the…

## Sorted Array to Binary Search Tree of Minimal Height

Objec­tive: Given a sorted array with unique ele­ments, Cre­ate a binary search tree with min­i­mal height. Why min­i­mal height is impor­tant : We can do the lin­ear scan to the array and make the…

## Count All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths

Objec­tive: Count all the paths from left top cor­ner to right bot­tom cor­ner in two dimen­sional array. Input: Two Dimen­sional array Out­put: No of paths. Approach : 1. Recur­sive Recur­sive solu­tion to this prob­lem is…

## Print All Paths from Top left to bottom right in Two Dimensional Array

Objec­tive: Print all the paths from left top cor­ner to right bot­tom cor­ner in two dimen­sional array. Input: Two Dimen­sional array Out­put: Print all the paths. Note: At the End of the arti­cle you will…

## Merge Sort — Updated — Most Efficient ways to Implement

Objec­tive : Write Merge Sort algo­rithm to sort ele­ments in an array Input: A unsorted array, arrA[]. Out­put : A sorted array. Approach: Divide and Con­quer: In this approach we divide the main prob­lems into…