Divide and Conquer – Rearrange array elements in special order

Objec­tive:  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 2n elements are {x1, x2, x3, y1, y2, y3} , then result should be {x1, y1, x2, y2, x3, y3} Example: … Read more Divide and Conquer – Rearrange array elements in special order

Find the local minima in a given array

Objec­tive:  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). Example: int [] arrA = {11, 4, 2, 5, 11, 13, 5}; Output: Local Minima is: 2 int []arrA = {1,2,3,4}; … Read more Find the local minima in a given array

Stock Single Sell Problem – O(n) Solution

Objec­tive:  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. Exam­ple: int[] prices = {200, 500, 1000, 700, 30, 400, 900, 400, 50}; Output: Maximum Profit: 870, buy date index: 4, … Read more Stock Single Sell Problem – O(n) Solution

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: contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6. Approach: Ear­lier we have seen how to … Read more Maximum Subarray OR Largest Sum Contiguous Subarray Problem – Divide and Conquer

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] is maximum where j > i. Example: int [] A = { 2, 5, 1, 7, 3, 9, 5}; Maximum Difference … Read more Maximum difference between two elements where larger element appears after the smaller element

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 Conquer. Find the length of the link list, say it is L. mid will be L/2. Now we need to divide … Read more Merge Sort in a Linked list

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 :

Array {1,1,3,4,6,7,9} first repeated Number : 1
Array {7,2,2,3,7} first repeated Number : 7
Array {5,3,3,3,3,3,3,3,4,4,4,5,3} first repeated Number : 5

Read moreFind the first repeated element in an array by its index

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 the next node in the inorder traversal of the tree. For the last node in a tree, inorder successor will be NULL

Similar Problems :
Inorder Successor in Binary Search Tree with parent link
Inorder Successor in Binary Search Tree without parent link

Input: A binary tree, a node x

Output: Inorder successor of node x.

Example:

InOrder Successor in binary tree example
InOrder Successor in binary tree example

Approach:

Read moreInorder Successor in Binary Tree

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 first element as root and insert all other elements into the tree but in that case tree will be skewed , which means all the nodes of the tree will be on the one side of the root so the height of the tree will be equal to the number of elements in the array. So here our objective is to keep the tree balanced as much as possible.

What is balanced Tree: A balanced tree is a tree in which difference between heights of sub-trees of any node in the tree is not greater than one. To read more about balanced tree, click here

Input: A one dimensional array

Output: Binary Search Tree of Minimal Height

Example:

Read moreSorted Array to Binary Search Tree of Minimal Height

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 is similar to Print All Paths from Top left to bottom right in Two Dimensional Array

But the Time complexity will be exponential because there will be many sub problems which will be solved again and again to get the final solution. read this : “Dynamic programming vs Recursion

2. Dynamic Programming (Better Solution)

Read moreCount All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths

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 will know what needs to be included if you want to print the diagonal paths as well.

Example:

Print All Paths - Example

Approach:

Read morePrint All Paths from Top left to bottom right in Two Dimensional Array

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 into smaller problems, solve them and merge the results to get the final result.

How Divide and conquer works in Merge Sort:

We divide the elements into two half’s by middle of the array. We solve the left half and right half recursively and merge the results.

Merging:

Read moreMerge Sort – Updated – Most Efficient ways to Implement