The “surpasser” of an element in an array is defined as the number of elements that are to the “right” … Read more
Objective: Given an array of integers of size 2n, write an algorithm to arrange them such that first n elements and … Read more
Objective: Given an array of integers write an algorithm to find the local minima. Local Minima: An element is considered as … Read more
Objective: Given an array represents cost of a stock on each day. You are allowed to buy and sell the stock … 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: … Read more
Objective: Given an array A[], write an algorithm to find Maximum difference between two elements where larger element appears after … 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 … 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 a 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:
NOTE: since it’s not a binary search tree, we cannot use binary search technique to reach to the node. we need to travel all the nodes in order to find the node for which we need to find the inorder successor.
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 the right bottom corner in two-dimensional array.
Input: Two Dimensional array
Output: No of paths.
Approach :
1. Recursive
The 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 that 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:
As we need to explore all the paths from top left corner to bottom right corner, we will either travel down OR travel right. so every time either we increase the row or column.
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:
Once the sorting is done individually on both the half’s, our next task will be merge them. To merge we start with both the arrays at the beginning, pick the smaller one put into array and then compare the next elements and so on.