Wednesday, September 16, 2015

Migrating to new domain

Dear Users,

Thanks for your patronage.
I am migrating this blog to my new domain www.letuscode.in
So Problem solving with programming is now "Letuscode.in" .
I will post the latest updates on this new blog from now on. 

I am also planning to migrate all the posts from my old blog to this new blog.
All the posts from this blog are migrated to the new blog.

Monday, August 24, 2015

How to check if sequence is a sub sequence of another

Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence.

For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]
where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]

The algorithm here is simple. 
  • Let us assume two indices i, j point to the beginning of sub-sequence and sequence respectively.
  • Do the following until we reach the end of any sequence.
  • If both the elements are same, increment both indices.
  • Otherwise increment j only.
At the end of this iteration, if we have seen all the elements of sub-sequence in the given sequence, we are done! otherwise we have not found!

Here is the code in C++ which implements the above approach. This runs in O(n) time and O(1) space. For Python code click here. For Java code click here.


Thursday, August 20, 2015

Finding the pivot element

Given an array of numbers ( minimum length 3), find an index such that all the elements to the left of it are less than or equal, and all the elements to the right of it are greater than it.

For example in the array [1, 2, 3], the pivot element is 2, as all the elements to the left of it are less than 2, and all the elements to the right of it are greater than 2.

The array [6, 9, 1, 2, 4] does not contain any pivot element.

Simple brute force solution:

For each element, check if all the left elements are smaller, and all the right elements are bigger. If there exists any such element we return it's index, otherwise we return -1.
But this solution takes O(n2) time.

Is there any better approach? Can we do it in O(n) time probably using extra space?

Yes, it can be done using two extra arrays.
  • One array stores the maximum element seen so far from the left.
  • Second array stores minimum element seen so far from the right
For example for the array [6, 9, 1, 2, 4]
Prefix maximum: [6, 9, 9, 9, 9]
Suffix minimum: [1, 1, 1, 2, 4] 

We first calculate the above two arrays. In the next iteration, For each element in the array, we check if the maximum element in the left is lesser, and the minimum element in the right is greater than it. If this condition is satisfied we are done. Since checking for maximum element in the left and minimum element in the right takes constant time (O(1)), the overall time complexity of this solution is O(n) and space complexity is O(1).

Below is the C++ implementation of the above. 

Wednesday, August 12, 2015

Minimum number of squares formed from a rectangle

Given a rectangle of some length and width, How do you divide them into minimum number of equal sized squares? This is a problem from Codechef.

For example give a rectangle of size 2 x 4, we can make them into two squares of 2 x 2.
Similarly a rectangle of size 3 x 7, can only be divided into 21 squares each of size 1 x 1.

So what is the logic behind this?
The length and width should be divided in same equal parts, and that part should as greater as possible. So we have to find the GCD(Greatest Common Divisor) of the length and width of the rectangle. Then the minimum number of squares can be calculated by
l/g * w/g. where l = length, w = width, g = GCD(l,w)

Here is the C++ code which implements this.

Monday, August 10, 2015

Ambiguous permutations

Given a permutation of numbers from 1 to N, We can represent it in two ways.

For example, let us consider a permutation from 1 to 5
P = [2 4 1 5 3]
This representation directly indicates the position of each number. i.e 2 is first, 4 is second and so on.

Alternatively, this can also be represented in inverse permutation form.
A = [3 1 5 2 4]
Assuming 1-based index, each number at the index 'i' indicates that the number 'i' is positioned at A[i] in the actual permutation. So this means that 1 appears at index 3, 2 appears at index 1, and so on.

There are some cases when the actual permutation and the inverse permutation are same. We call it as an ambiguous permutation. Now the problem is how do we check if the give permutation is an ambiguous permutation?

The solution is simple. We have to create an inverse permutation in another array, and check if it is same as the original permutation. Calculating the inverse permutation is discussed in my previous post.

Following is the C++ code. It runs in O(n) time and O(n) space.


Friday, August 7, 2015

Duplicate elements in array at given distance

Given an array of numbers A, which might contain duplicate elements, 

How do we find if there are two elements A[i], A[j] such that i, j are distinct and the difference between them is at most k?

Look at the following examples.
1. A = [9, 5, 6, 9, 3, 0, 1], K =3
The answer is "Yes" because 9 is present at index 0, and 3

2. A = [10, 0, 10, 20, 30], K = 1
The answer is "No" because there are no duplicate elements at a distance less than or equal to 1

A simple and straight forward algorithm is to have two loops, the outer loop fixing one element, and the inner loop checks if that element exists within a distance of K. This algorithm runs in O(n2) in worst case.

Let us look at an efficient algorithm using the map data structure. The map stores the element as the key and it's most recent index as it's value. Here are the steps.
  • For each element in the array
    • Store the element and it's index in the map if does not exist already.
    • If already exists, 
      • Check if the difference between the recent index and current index is less than K. 
      • If so return true.
      • Otherwise update the map with recent index
This algorithm runs in O(n log n) time, and take O(n) extra space for the map. Here is the C++ code given below. For the Python implementation checkout this link. For Java implementation check this link.

Monday, August 3, 2015

Mirror image of a binary tree

Given a binary tree, how to convert it to it's mirror image?
For example consider the following binary tree and it's mirror image.
Here simply, the left and right sub trees of each node are inverted. So we have to simply invert the given binary tree. It is a simple implementation problem. Using recursion we can solve it by following the below steps
  1. If root is NULL, simply return
  2. Invert the left sub tree
  3. Invert the right sub tree
  4. Swap left and right sub trees.
Here is the C++ code which implements the above algorithm. It runs in O(n) time.


Monday, July 20, 2015

XOR of all sub arrays

Given an array of elements, how do we find the XOR of each sub-array and XOR of those results?

For example let us consider the array [1, 2, 3], all possible sub-arrays are

XOR[1] = 1
XOR[1, 2] = 1 ^ 2 = 3
XOR[1, 2, 3] = 1 ^ 2 ^ 3 = 0
XOR[2] = 2
XOR[2, 3] = 2 ^ 3 = 1
XOR[3] = 3

And the result XOR[1, 3, 0, 2, 1, 3] = 2.

Brute force solution:
From the above example, you can see that an array of 3 elements has 6 sub-arrays. Similarly you can verify the count by listing the sub-arrays for N= 4 and N= 5. In general, for an array of N elements there will be N*(N+1)/2 sub-arrays. We have to calculate the XOR of each of these sub arrays. So an outline of algorithm can be as follows.

for i in range(1,N)
   for j in range(i,N)
      for k in range(i,j)
         x = XOR(x,A[k])

This is clearly not en efficient solution and take O(n3) time. We can also use dynamic programming to pre-calculate the XOR values so that time can be reduced to O(n2). But is there any better method?

Efficient Solution:
Observe how many times, each element appear in all the sub arrays. In the above example
1 - 3 times
2 - 4 times
3 - 3 times

Consider 0-index, in general A[i] appears (N-i)*(i+1) times. 

We also know that if an element is XOR'ed with itself even number of times, it is zeroed out. and if it is odd number of times, it remains the same. For example

V ^ V ^ V ^ V = 0
V ^ V ^ V = V

Consider the two cases when the number of elements N is Even or Odd
N is even, each element appear even number of times:

N= 2, 
A[0] - 2 times
A[1] - 2 times
N = 4,
A[0] - 4 times
A[1] - 6 times
A[2] - 6 times
A[3] - 4 times

This is because either (N-i) or (i+1) is always even for all values of i.
Hence, for an array of even length, the XOR of all sub-array becomes Zero.

N is odd, the elements at even index will only prevail in the final result.

The following C++ program implements the above approach. The time complexity of this algorithm is O(n).

Thursday, July 16, 2015

Character to be removed to become a palindrome

Given a string, We have to find out by removing which character, it becomes a palindrome.

For example consider the string "racercar", the character 'r' at index 4 should be removed to become a palindrome.

The approach here is simple.

Start from both ends of the string and compare both characters. If they are equal, we increment the front index and decrement the back index. If they are not equal, one of the characters needs to be removed. We can check this by verifying if a palindrome can be formed by removing the front character or the back character. Repeat the above procedure until both indices meet each other.

We are printing the index of the character to be removed. If the string is already a palindrome, we print -1.

This solution has O(n) time complexity.

Here are the implementations in C++ and Python.

Tuesday, June 23, 2015

Generating all possible parenthesis expressions

Given a number N, how do we generate all possible valid expressions with N pairs of brackets?

For example for N = 2, there are 2 such expressions
()()
(())
For N = 3, there are 5 expressions
((()))
(()())
(())()
()(())
()()()

We have a simple solution to this problem by using recursion. We design this method as follows.

It takes two parameters left count, right count, buffer and an index. At each index we can either fill a left bracket or a right bracket.

As long as we have left brackets, we try to fill them and recursively call the method with one less left brace.

Then we check if we have more right braces than left braces, then fill it up with right brace. Recursively call the method with one less right brace.

When we don't have any left or right braces remaining, we can print the contents of the buffer.

Here is the Java implementation.

Wednesday, May 13, 2015

How does a radix sort work?

Radix sort is an integer sorting algorithm. As it's name indicates, it sorts a list of numbers based on the digits of the numbers. 

It's a linear time sorting algorithm which is different from the comparison based sorting algorithms like quick sort or heap sort. Counting sort is also a linear time sorting algorithm which is explained in my previous post.

Let us understand this algorithm using an example. 
Consider the array [235, 10, 784, 69, 51]

We first sort the numbers based on the least significant digit, i.e the digit at 1's place. It becomes [10, 51, 784, 235, 69]. Observe that the these numbers are now sorted according to it's last digit ([0,1,4,5,9]).

Next we consider the digits at 10's place and sort them. It transforms to
[10, 235, 51, 69, 784]. These are sorted according to the last but one digits ([1,3,5,6,8])

Similarly in the next step it becomes [10, 51, 69, 235, 784]

Now the entire array is sorted! We no longer need to sort array because we have at most 3 digits in any number.

Implementation details:
Suppose there are at most D digits in any number, we call the counting sort D times for each place.

Let us briefly know how counting sort works. For more details, you can check my previous post.

It first groups the numbers into buckets. The result of this is a count array of size 10 (assuming the numbers are in the range 0-9). 

Calculate the prefix array of this, we get the sorted positions of given numbers.

Then we use a temporary array to arrange the numbers in sorted order.

An alternative implementation could be to maintain a list of numbers for each bucket, and merging them to a sorted array. But this approach takes extra memory for the list of buckets.

The following code shows  the implementation of the above algorithm.
Exercise: Try to solve this SPOJ problem using radix sort.

Saturday, May 9, 2015

Check if a binary tree is the mirror image of itself

Given a binary tree, how do we write a program to check if it is the mirror image of itself. This binary tree is also called a symmetric tree. 

A binary tree is called a symmetric tree if it's left and right sub-trees are mirror images of each other.

For example Let us consider the following examples of some symmetric and asymmetric trees.

    1
   / \ Symmetric
  2   2  
    1
   / \ Asymmetric
  2   3 
      1
     / \
    2   2  Symmetric
   /     \
  3       3

We can design a recursive algorithm like the following.
  1. An empty tree is a symmetric tree.
  2. At each node we check the following
    1. If the left value and right value are same
    2. If the left sub-tree of left node and right sub-tree of the right node are mirror images
    3. If the right sub-tree of left node and left sub-tree of the right node are mirror images
  3. If all the above conditions are satisfied then the tree is symmetric.
Here is the C++ implementation of this.

Friday, May 1, 2015

Level order traversal of the binary tree from the bottom

Given a binary tree, how do we print the nodes in level order starting from the bottom.

For example for the following tree, the output should be 2 3 1

    1
  /  \
 2    3

An obvious solution is to first find the maximum levels of the tree. we can print the nodes from maximum level to minimum level. This is not so efficient, because to print each level we need to traverse all the nodes.

Another solution is that we can modify the level order traversal. We need an additional stack to store the nodes. Instead of printing the values of the nodes as soon as they are deleted from the queue, we can add them to stack. Later, we can pop the elements from the stack and print them. This will print the elements in reverse level order.

Here is the C++ code for the second approach.

Thursday, April 30, 2015

Creating a balanced binary search tree from sorted array

Given a sorted array, how do we create binary search which height balanced.

For example the array [1,2,3,4,5] must be transformed to the following binary tree

                           3
                /  \
               2    4
              /      \ 
             1        5


We can use the divide and conquer approach to solve this problem. To create a balanced tree, the number of nodes on the left sub-tree should be almost equal to that of right sub-tree.

How do we do it?
 
The create method is provided the lower and higher index parameters in addition to the actual array. We create the root node with the middle element and create the left and right sub trees with the left and right portions of the array.

Here is the C++ code.

Wednesday, April 29, 2015

Checking if a binary tree is balanced

Given a binary tree, how do we check if it is balanced or not?
We say that a binary tree is balanced if height difference of left  and the right sub-trees is at most 1 at  any node.

Consider the following examples

  1          1               1             1
 / \          \             /               \
2   3          2           2                 2
                                           /
                                          3
Balanced    Balanced     Balanced       Unbalanced

Solution:

We can simply implement a recursive solution based on the above definition of balance. At each node we check the height of the left sub tree and the right sub-tree and call the same function for it's left child and right child recursively. But this is inefficient because we calculate the height repeatedly. This solution is O(n2).

Because we are calculating the height at each node, we can reuse the height of sub-tree to check the balance at the root node. Here is how we can do it. 

We write a method called balance. This method returns the actual height of the tree if it is balanced. Otherwise it returns -1. So at any point if the balance of left or right sub-tree is -1 or their difference is greater than 1, we can simply return false.

Here is the C++ implementation of this algorithm. It runs in O(n) time.

Tuesday, April 28, 2015

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.

Monday, April 27, 2015

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.

Sunday, April 26, 2015

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).

Monday, April 13, 2015

Infinite house of pancakes - Google Codejam 2015 Qualification round problem 2

Here is the link to the original problem. Let us try to simplify the problem statement a little bit.

There is a dinner house of infinite number of guests but finite number of pancakes. Each of them hold a plate which is either empty or has some pancakes in them. Every minute, one of the following actions can happen.
  1. Each guest eats one pancake per minute.
  2. The server will declare it as a special minute during which all guests stop eating, and the server will choose a guest with non-zero pancakes and transfer some cakes from that guest to the another guest.
The problem is to optimize the number of special minutes so that the total time to finish all the cakes is minimum.

We are given the number of pancakes on each plate initially.

Let us walk through a small example.
[1, 2, 4] - If we don't declare any special minutes, all the cakes will be finished in 4 minutes which is the maximum cakes.

What is we declare a special minute and take out 2 cakes from the 3rd guest and keep it in an empty plate?

[1,2,2,2] - Now we can finish all the cakes in 2 minutes + 1 special minute. So we can finish all the cakes in 3 minutes itself.

Note that we can not reduce the time any further because if we do so, we have to declare 3 special minutes (for moving one cake from each of the plate with 2 cakes) which outweigh the actual eating time which is 2 minutes.

Without the loss of generality we assume that we can minimize the number of pancakes to be eaten by moving them from the maximum plate to a zero plate.

A simple brute force algorithm would suffice because the restriction on the input is small (1000).
  • Let us calculate the frequency of pancakes in each plate.
  • For each of the sizes between 1 and 1000
    • Move the excess cakes (p[i] - size) in each plate to an empty plate and sum up the number of moves required.
    • Add the size to the number of moves, you will get the time required to finish.
    • Update the minimum time.
Let us trace the algorithm for the above example.
[1,2,4]
  • Divide them into size 1 chunks - [1,1,1,1,1,1,1] - 4 moves+ 1 = 5 minutes.
  • Divide them into size 2 chunks - [1,2,2] - 1 move + 2 = 3 minutes
  • Divide them into size 3 chunks - [1,2,3,1] - 1 move + 3 = 4 minutes
The minimum among them is 3 minutes. For simplicity I have not shown the division for size greater than 3. Even if we calculate they return the same output of 4.

The maximum time it takes for any combination is the maximum number of cakes in any plate.

Here is the C++ implementation of the same. 

Note: I did not solve this problem in the competition. But I got inspired by the solutions (user: kyc) who successfully solved the problem. I only composed the solution analysis. If somebody has a better solution, please feel free to post it in a comment.



Standing Ovation: Google codejam 2015 Qualification round problem

Every year Google conducts a competition called Codejam for programming enthusiasts. The qualification round for the year 2015 got finished yesterday. In this post, I am going to explain the solution approach for the first problem.

You can read the problem from this link. I will try to give the abridged problem statement below.

There are a group of N people in a stadium with their shyness levels represented by a String S of digits(0-9). The digit at each index represents the number of persons with shyness level equal to the index.

For example S[0] represents the number persons with shyness '0'.
S[1] represent the number of persons with shyness '1' and so on.

Persons with shyness level 'L' will not standup and clap until 'L' other people standup and clap before them. For example, in order for a person with shyness level 3 to standup and clap, 3 other people must do that before him. 

Now the problem is to find whether the all the people in the given group gives a standing ovation on its own? or What is the minimum number of people to add to the group to ensure that they give a standing ovation.

Let us consider a couple of simple examples.
  1. [1, 1, 2]: There is one person with shyness level 0 who will clap first. After seeing him, the second person with shyness 1 will also clap. Then the last two people with shyness 2 will also clap. So there is no need to add any people to give a standing ovation.
  2. [1, 0, 1]: In this case, we need one person with shyness 0 or 1 to be added to the group because the last person will not standup until 2 other people clap.
A simple greedy approach will solve the problem. Here is the algorithm.

Start at the first person and count the number of people stood up before him. If this count is not enough for the current person to standup, count the difference needed.  Accordingly increment the people currently standing.

Here is the C++ implementation of the above approach. This runs in O(n) time.

Friday, April 3, 2015

Generating next bigger palindrome of a number

Given a number, how do we generate a smallest number which is greater than the given number and is a palindrome?

Consider the following examples

Input    Output
3         4
9         11
13        22
767       777
594       595
898       909
999       1001

Here is the solution approach. This problem has multiple cases to be considered.

Case 1: 
If all the digits in the number are '9', the output is simply 1 followed by (d-1) 0's followed by 1, where d is the number of digits in the original number.

Example: 9999, d = 4, so the output is 10001

Case 2:
How do we get a palindrome from a given number with least number of changes?
If the given number itself is a palindrome, obviously we need not make any changes.
Otherwise there are two ways to do that. Replicate the right half with left or replicate the left half with right.

Consider the number 230847, the two possibilities are 230032 and 748847
for 6195824, the two possibilities are 6195916 and 4285824.

Observe that if we replicate left half with right half, we are getting the numbers far from the given number. This is because as we move from right to left, the place value of the digit increases. But we want the number which is just greater than the given number with least difference.

So we have to replicate the right half with left half.

Are we done if we just replace the right half with left half? No.

Let us see the same example of 230847, if we replicate as said above, the result is 230032.
What is the problem with this number? It is a palindrome; but it is smaller than the given number. We wanted a number which is just greater.

So how to make this number just bigger?

Increment the middle digit(s) and propagate the carry if any towards the left and the right.

If the number has even number of digits, there will be two middle digits; otherwise it has just one middle digit.

230032 becomes 231132 and that is the required answer.

Let us consider one more example with carry propagation, 849948. After incrementing middle digits, it becomes 850058.

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

Tuesday, March 31, 2015

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.

Monday, March 30, 2015

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.


Friday, March 20, 2015

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.

Thursday, March 19, 2015

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.

Tuesday, March 17, 2015

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.

Friday, March 13, 2015

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.
 

Thursday, March 12, 2015

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

Wednesday, March 11, 2015

Left view of a binary tree

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

For example, consider the simple binary tree below

   1
 / \
2   3


The left view of this is 1, 2. Similarly consider one more example

            1
          /  \
         2    3
             / \
            4   5

Left view for this tree contains 1, 2, 4.

If the tree is completely left skewed or right skewed, the left view contains all the nodes like the following. For example

1                1
 \              /
  2            2
   \          /
    3        3


The left view for both of the above trees is 1, 2, 3.

We can solve this problem in two ways, one iterative and the other using recursion.

Recursive method:
In this approach to the traversal function, we send two additional parameters along with root node, one is the current level and another is maximum level. maximum level is a reference parameter which remembers it's value between the function calls. 
We compare the current and maximum level values, if the max level is less than current level we print the data at root node and update the maximum level. Recursively call the same function for the left and right sub-trees by incrementing the current level.

Iterative method:

We use the level order traversal method to print the first node in each level. While storing the nodes in the queue, we store a separator (NULL) node to distinguish between the levels.

Here is the C++ code which implements the above approaches.Both run in O(n) time complexity.

Tuesday, March 3, 2015

Maximum nesting depth of a paranthesis expression

Given a parenthesis expression, We have to find the maximum nesting depth.

For example: the expression ()((()))(()) has a maximum nesting depth of 3.
The expression ((()())) has a maximum nesting depth of 3.
Let us output -1 for an unbalanced expressions such as (())) or ()(

This is a simple problem that can be asked in different forms. One such example can be
Given a sequence of jobs executed by a machine. What is the maximum number of parallel jobs executed at any point of time. 
One more variation of this problem can be
Given a maximum capacity of a computer center, and a sequence of people arrived, how many people have to wait for their turn.
Check this question for details.  
Here is the simple O(n) solution for the original problem. 
  1. Take two variables depth and max_depth initialize them to zero.
  2. Increment depth if we see an open bracket and update the max_depth
  3. Decrement depth if we see a closed bracket and check if it is going negative.If it goes negative, the expression is unbalanced.
  4. Check if depth is zero. If it is not zero, then it is not a balanced expression.
  5. Return max_depth
With minor modifications to this algorithm, we can design an algorithm for the second variation also.

Here is the Python implementation.The time complexity for this O(n) and space complexity is O(1).