The “surpasser” of an element in an array is defined as the number of elements that are to the “right” and bigger than itself. Write an algorithm to Find the maximum surpasser of the array. Example: Input array: [2, 7, 5, 5, 2, 7, 0, 8, 1] The “surpassers” are [5, 1, 2, 2, 2, … Read more
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 2n elements are {x1, x2, x3, y1, y2, y3} , then result should be {x1, y1, x2, y2, x3, y3} Example: … Read more
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). Example: int [] arrA = {11, 4, 2, 5, 11, 13, 5}; Output: Local Minima is: 2 int []arrA = {1,2,3,4}; … Read more
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. Example: int[] prices = {200, 500, 1000, 700, 30, 400, 900, 400, 50}; Output: Maximum Profit: 870, buy date index: 4, … Read more
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: contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6. Approach: Earlier we have seen how to … Read more
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
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
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
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:
Approach:
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:
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)
Create two dimensional resultCount array to store the number of paths from top left corner.
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:
Approach:
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: