Divide and Conquer – Rearrange array elements in special order
Objective: Given an array of integers of size 2n, write an algorithm to arrange them such that first n elements and last n elements are set up in alternative manner. Say n = 3 and...
Category: Divide and Conquer
Find the local minima in a given array
Objective: Given an array of integers write an algorithm to find the local minima. Local Minima: An element is considered as local minima if it is less than both of its neighbors (if neighbors exist)....
Stock Single Sell Problem – O(n) Solution
Objective: Given an array represents cost of a stock on each day. You are allowed to buy and sell the stock only once. Write an algorithm to maximize the profit in single buy and sell....
Maximum Subarray OR Largest Sum Contiguous Subarray Problem – Divide and Conquer
Objective: The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. Example: 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
Objective: Given an array A[], write an algorithm to find Maximum difference between two elements where larger element appears after the smaller element or in other words find A[i] and A[j] such that A[j]-A[i]...
Merge Sort in a Linked list
Objective: Given a Linked List, Sort it using merge sort. Example: ->9->3->4->2->5->1 Sorted List: ->1->2->3->4->5->9 Approach: Reference : Merge Sort in array As it Merge sort, we apply the same logic , Divide and...
Find the first repeated element in an array by its index
Objective: Given an array of integers, find out the first repeated element. First repeated element means the element occurs atleast twice and has smallest index. Input: An Array Output: The first repeated element Examples...
Inorder Successor in Binary Tree
Algorithms – Inorder Successor in Binary Tree Objective: Given a Binary tree (Not binary Search Tree ), find the inorder successor of a node. What is Inorder Successor: Inorder successor of a node is...
Sorted Array to Binary Search Tree of Minimal Height
Objective: Given a sorted array with unique elements, Create a binary search tree with minimal height. Why minimal height is important : We can do the linear scan to the array and make the...
Count All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths
Objective: Count all the paths from left top corner to right bottom corner in two dimensional array. Input: Two Dimensional array Output: No of paths. Approach : 1. Recursive Recursive solution to this problem...
Print All Paths from Top left to bottom right in Two Dimensional Array
Objective: Print all the paths from left top corner to right bottom corner in two dimensional array. Input: Two Dimensional array Output: Print all the paths. Note: At the End of the article you...
Merge Sort – Updated – Most Efficient ways to Implement
Objective : Write Merge Sort algorithm to sort elements in an array Input: A unsorted array, arrA[]. Output : A sorted array. Approach: Divide and Conquer: In this approach we divide the main problems...