# Finding the kth element in Binary search tree

Given a binary search tree, how do we find a kth smallest or kth largest element?
For example, given the following binary search tree.
Third largest element is 6
Second smallest element is 2
Fifth largest element is 5 and so on…

Solution:

We can solve this problem by modifying the the in-order traversal method of a binary tree. In addition to the root node, we can pass two more parameters one is K, and current count of the nodes visited as a reference parameter. When the current count reaches K we found the kth order element.

To find out the kth smallest element, we need to visit left sub-tree, then root and then the right sub-tree as usual. To find the kth largest element we need to do reverse in-order traversal i.e First visit right sub-tree, then root and then the left sub-tree.

Here is the C++ implementation. This includes the recursive and iteration versions of finding kth smallest and kth largest elements. The iterative version is simply the manual implementation of a recursion using a stack.

# Longest sub array with zero sum

Given an array of integers (positive and negative), how do we find a longest sub-array with zero sum?

For example, consider the example [5, 0, -1, 3, -2, 4], the longest sub array with zero sum contains 4 elements.

The straight forward approach is to check the sum of all possible arrays and find out the maximum length sub array. This will run in O(n3) time.

Can we do better than this?

Yes, by using dynamic programming we can do that. Take an array which is of same size. We can find this in n iterations.

In the first iteration, we find the length of longest sub sequence with zero sum beginning with the first element.

In the second iteration, we find the length of longest sub sequence with zero sum beginning with second element and so on.

Let us calculate this array for the above example

Iteration 1:
Cumulative Sum = 5 5 4 7 5 9
Max Length     = 0 0 0 0 0 0

Iteration 2:
Cumulative Sum = _ 0 -1 2 0 4
Max Length     = 0 1  0 0 4 0

Iteration 3:
Cumulative Sum = _ _ -1 2 0 4
Max Length     = 0 1  0 0 4 0

and so on.

At the end of all this, maximum of this array contains the result.

Here is the C++ code.

# Programming puzzle – calculating product array

Given an array of numbers A[1:N], we have to generate a product array P[1:N] such that P[i] contains the product A[1]*…A[i-1]*A[i+1]…A[N]

That means each entry in the product array should contain product off all the elements except the one at that particular index.

For example let us consider the array [4, 2, 10, 5], the output should be {100, 200, 40, 80}.

The restriction here is that we have to device an algorithm without using division operation. Had it been allowed, we would have simply calculated the product of all the elements and fill the product array by dividing this with the current element.

Here is the solution approach.

We do this using two iterations one forward and the other backward.

• In the forward iteration, we fill the product array by filling each entry with product of all the elements before it.
• In the backward iteration, we multiply each element with product of all the elements to the right of it.

Here is the C++ implementation for this. The time complexity is O(n).

# Searching for an element in array with successive elements atmost 1 distance apart

Given an array of integers where each element has a difference of atmost 1 with it’s neighbors, we need to find the given element.

For example, consider the array [1, 2, 2, 1, 2, 3, 2, 1], and the element to be searched is 3, we need to return the index 5.

This is just an implementation problem with a trick. Here is the approach.

• Start with first element, check if the current element matches, if so return it.
• Otherwise increment the index by the absolute difference between current element and target element.
• Repeat the above step until we find the element or reach the end of the array.
This algorithm runs in O(1) in best case. Example of the base cases
Searching for 10 in [1,2,3,4,5,6,7,8,9,10] or
Searching for 1 in [10,9,8,7,6,5,4,3,2,1]

Within One jump we reach the target element.

However this takes O(n) time in the worst case like the following
Searching for 2 in [1,1,1,1,1,1,1,1,2]

Here is the C++ implementation.

# Searching for a word in a grid

Given a two dimensional table of letters, and a word to be searched, design an algorithm to check if it is present in the grid.
The word can be formed in any of the 8 possible directions as shown below.

Here is how I solved this problem.

Write a function which takes the string to be searched, the starting coordinates, and the direction number (as shown above) as parameters.

bool search_grid(const char *word, int x, int y, int direction)

If the current letter matches, depends on the direction, we recursively invoke the same method for the next character in the string with modified coordinates.
If the current letter does not match, the word cannot be found in the given direction starting from the initial coordinates.

Here is the C++ program which implements the basic algorithm for the word match. This is not  a complete program. You may try writing a wrapper which finds the initial coordinates to start the word search (Find the the coordinates where the first letter of the word appears) and do some checks for base cases like empty string etc.

# Minimum number after removing K digits

Given a number N, and a number K, find the minimum number that can be formed by deleting K digits. The order of the digits should not be changed.

For example consider N = 234987, K = 2, we can remove 9,8 and the resulting number is 2347.

The solution is based on the following observation, consider the above case.

Let us delete a digit from 234987
Deleted Digit – Result
—————————
2             – 34987
3             – 24987
4             – 23987
9             – 23487
8             – 23497
7             – 23498
If we remove 9 we will get the minimum number. Observe that in the given number, 9 is the first digit which is greater than the next digit.

What if all the digits are in ascending order?

Let us walk through an example.
N = 12345, K = 3. If we remove 4,5 we will get the minimum number. The observation is that we need to keep on removing right-most digits in this case.

[This is a re-post after correcting my incorrect approach. Thanks to Jeff Senecal for pointing out the mistake.]

Here is the C++ implementation of the above approach.

# Maximum number of 1s in any row of a boolean matrix

Given a matrix consisting of only 0,1s, with each of it’s row sorted (i.e all 0s appear before 1s). The problem is to efficiently find the maximum number of 1s present in any row.

For example consider the following matrix.

0 0 1 1
0 0 0 1
0 1 1 1
0 0 0 0

The maximum number of 1s in any row is three which appear in the third row.

The general approach is to find the number of 1s in each row and update the maximum.

There are two ways to find the number of 1s.
• One simple approach is to linearly search for first 1 and find the count of 1s. This will take O(n) time in worst case. So the overall time complexity would be O(n2).
• Another faster method is to search for first 1 using binary search since each row is sorted. This will take only O(log n) time and the overall complexity would be O(n log n).

Even more efficient approach can be as follows.

• Start with the right most element in the first row, keep counting the number of 1s until we reach zero.
• Move to the next row and start checking the elements from previous column
• If the element is zero, just move on to the next row
• Otherwise count the ones until we reach zero or the first column
• Repeat the above step for all the rows. At the end, we get the maximum number 1s.

This approach just runs in O(n+m) where n, m are the number of rows and columns respectively.

Here is the C++ implementation of the above. I have used the lower_bound() method from the standard library to find the left most occurrence of a 1. Look at my previous post to understand how this method works.

# Type casting in C++ – Part 1

Type casting frequently arises in real life programming. This post concentrates on type conversion of fundamental data types. Type casting is the process of converting from one data type to another. In C++, type casting is automatic in some situations. These are called implicit conversions.

For example
char c = ‘A’;
int ch_code = c;
short s_val = 1024;
int i_val = s_val;
Here the value of “c” is automatically promoted to an int as we are assigning a smaller type into a bigger type. The second case is also similar. This is also called a promotion. There is no truncation in these cases. Other examples of this type include int to float/double, float to double, boolean to int etc…
Implicit type conversion also happen when a bigger type is assigned to smaller type. This might result in truncation/data loss if the source data which cannot fit in the destination type. Some compilers gives a warning when we are using such a conversion. This can be avoided by explicit conversion.
int ch_code = 97;
char ch = ch_code; // no data loss as 97 is within the range of char type; represents the character ‘a’
float pi = 3.14159;
int i_pi = (int)pi; //decimal part is truncated; explicit type conversion
If the truncated integer value is bigger than the integer type, the behavior is undefined.

If a negative integer type is converted to a unsigned type, the resulting value would be 2’s compliment bit representation interpreted as a positive integer.

For example the following code
short x = -32768;
unsigned short y = x;
Assigns a value of 32768 to y. The least value has become the greatest value in this case.

If you are converting an integer to boolean type, all non-zero value will be converted to 1 including negative and positive values which are considered true. 0 is considered false.
int x = -10;
bool b = x; // b is assigned 1, i.e true
x = 10;
b = x; //b is 1 here also
x = 0;
b = x; //b is 0,i.e false

In the later posts, we will look at type conversions between non fundamental data types like pointers and classes.

# Right view of the binary tree

Given a binary tree, how do we print the right view of it?

For example, consider the simple binary tree below

1
/
2   3

The right view of this is 1, 3. Similarly consider one more example

1
/
2    5
/
3   4

Right view for this tree contains 1, 5, 4.

This is similar to my last post which asks for the left view of the binary tree. We just need to make the following changes to the algorithms discussed in the earlier post.

In case of iterative solution, we need to add the right child first to the queue before adding the left child.

In the recursive approach, we need to first recurse on the right child. Below is the modified code.

# Alternate arrangement of two linked lists

Given two linked lists, we have to merge them into a single list by alternatively taking one node from each list.We should do this by re-arranging the links and should not create duplicate nodes while merging.

For example consider the two lists

1 -> 2 -> NULL
3 -> 4 -> NULL

The result should look like the following.

1 -> 3 -> 2 -> 4 -> NULL.

There is no logic required for this problem except arranging the links carefully.

Just take two pointers to the two lists, keep adding the first node followed by the second node by advancing both the pointers at a time.

Come out from the loop when we reach the end of any list.

Lastly copy the remaining nodes from the longer list to the result list.

Below is the C++ implementation of the same. The program can be run through the following test cases.

1. Two empty lists
2. One empty list and the other non-empty list
3. Two lists are of equal length
4. Two lists are of unequal length