Posts

Showing posts from April, 2017

Array of 3 Pointers

In today's problem we are given 3 sorted arrays. Let A, B, C be the 3 arrays. We need to find a value such that max(abs(A[i] - B[j]), abs(B[j] - C[k]), abs(C[k] - A[i])) is minimum. Consider the following example for a better understanding.

Input

A : [1, 4, 10]
B : [2, 15, 20]
C : [10, 12]

Output

5

Explanation

We choose 10 from A, 15 from B and 10 from C. Therefore, max(abs(10 - 15), abs(15 - 20), abs(10 - 10)) is 5, which is the minimum value possible.

Solution Approach

We use a 3 pointer approach to solve this problem. The 3 pointers are i, j and k which correspond to the indices of A, B and C arrays.

Initialise a result variable to INT_MAX.Run a loop until the end of one of the array's is reached. Find the maximum of the difference between the 3 elements in each iteration. If the maximum value found is the difference between A[i] and B[j], increment the pointer value of the smaller of the two elements. Update the result value if the difference is smaller than the previous resul…

Finding the sum of N Biggest elements in Binary Search Tree

Image
Trees look kind of complicated when you get started with them. But they are really fun when you are a master of recursion concepts. In today's problem we are given a binary search tree and a number N. We have to find the sum of the N biggest elements in the BST, given N <= number of elements in the BST.

Sample IO



Solution Approach

This problem can be solved using recursion. Binary Search Tree, for those of you who are not aware of, is a tree in which the elements in the right child of every node is always bigger than the node itself and every element in the left child of any node is always smaller than the node itself. So basically while solving this sum we have to just make sure that there is no element to the right of the current node and add it until the number of elements we've added reaches N. The algorithm is given below.

Let,
result be the name of the variable storing the value of the sum
sum be the name of the function
k be the number of elements added already
N be the n…