Wednesday, December 18, 2013

Minimum difference between two sorted arrays

Given two arrays sorted in ascending order, find the absolute minimum difference between any pair of elements |a-b| such that a is from one array and b is from another array.

For example consider the following two arrays.

array1 = [3, 27, 45, 68, 70, 81, 99]
array2 = [9, 16, 25, 35, 73, 84]

The minimum difference is 2 (27-25).

This can be calculated using the following algorithm.
  1. Take two indices i, j which point to the beginning of the two arrays (i.e 0)
  2. Take variable MinDiff and assign it the maximum possible value
  3. If array1[i] and array2[j] are equal return 0 
  4. Otherwise update MinDiff if abs( array1[i] - array2[j] ) is the new minimum.
  5. If array1[i] > array2[j] move second index(j) forward otherwise move first index (i) forward.
  6. Repeat the above procedure until we reach the end of any of the two arrays.
  7. Finally process the remaining part of left-over array to update MinDiff
This algorithm takes linear time - O(n) and constant space O(1). Here is the Java implementation of the above algorithm.

Friday, December 13, 2013

Finding the kth smallest element in the array

Given an array of numbers, how do we efficiently find the Kth smallest number in it?

This problem is also called the selection problem. Widely used in order statistic (Find the smallest, biggest, median, top K elements etc...)

For example in the array [6, 1, 9, 8, 3, 5, 4] the third smallest element is 4.

An obvious approach could be to sort the entire array and return the element array[K-1]. But this approach takes O(n log n) time in the worst case (Sorting time).

Another simple approach could be to perform first K steps in either insertion sort or selection sort which gives us the required element. But this approach takes time proportional to K.

Can we do better than this?

We can use the partition method used in Quick sort to solve this problem. The partition method divides the array into two parts based on a pivot element. The pivot element is in it's correct position. All the elements to the left of it are less than or equal to pivot, and all the elements to the right of it are greater than pivot. Finally it returns the pivot position.

We can compare the pivot with K. If it is equal  we are done!. If pivot is less than K, we need to search the right-side partition otherwise we need to search the left side partition.

Here is the Java implementation of the above algorithm.

Monday, December 9, 2013

Depth first traversal in a graph

Depth First Search (DFS) is graph traversal algorithm. Using this algorithm, given a source vertex (s), we can answer queries such as 
  • What are the all the vertices connected to s?
  • Is there any path from s to v?
  • What is the path from s to v?
For example consider the following undirected graph.
0 is connected to 7 via the path 0 - 2 - 7. But 0 is not connected to 4 or 5 or 6.

The DFS algorithm works by starting at the source vertex, and start exploring the un-visited vertices adjacent to the source vertex. For each of the un-visited vertices, this procedure is recursively applied. So this procedure inherently uses the stack data structure.

We maintain a marked[] array to keep track of the visited vertices. To check if a vertex 'v' is reachable from 's', we just need to examine marked[v]. If it true, 'v' is connected to 's'. Otherwise they not connected.

We also create edgeTo attribute for each vertex which indicates from which vertex, this is being explored. Using this attribute, we can trace the path from a vertex to the source.

In the implementation of this algorithm, we use the adjacency list representation of the graph.

Friday, December 6, 2013

Minimum coin change problem

Given a set of denominations and an amount, how do we minimize the number of coins to make up the given amount?

Let us consider the set of denominations {1,3,4}. Also assume that we have infinite supply of coins for each denomination. To make change for 6, we can have three combinations
The minimum number of coins to make change for 6 is '2'.

This problem can be efficiently solved using dynamic programming approach. Let us formulate the problem in terms of it's sub-problems.

Let the amount be T and the given denominations are {d1,d2,...dn}. Create an array of size (T+1) denoted by MC[].
MC[K] denotes the minimum number coins required for amount K. It can be defined as follows

Min{ MC[K-d1], MC[K-d2],...MC[K-dn] } + 1 
This means that we can find the solution of a problem from it's sub-problems and it has optimal sub-structure property suggesting the dynamic programming solution. 

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

Thursday, December 5, 2013

Finding the edit distance between two strings

Given two strings as input, write a program to find the edit distance between them. 

The edit distance is defined as the minimum number of modifications to do on one string to transform it into the other string. A modification can be inserting a character, deleting a character, or replacing an existing character.

For example, consider the two strings "saturday" and "sunday". The edit distance is 3. There is no way, we can change one string to the other in less than 3 modifications.

The 3 modifications that can be done on "saturday" are
remove 'a' --> sturday
remove 't' --> surday
replace 'r' with 'n' --> sunday

The following is the algorithm based on dynamic programming.

Let us assume string1 is of length N and string2 is of length M. We create a table of size (N+1) X (M+1).

The entry table[i][j] gives the edit distance between prefix of string1 ending with ith character and prefix of string2 ending with jth character.

0 <= i <= N and 0 <= j <= M

We fill this table in a bottom-up manner. This is essentially solving the problem by combining the results of it's sub-problems. (Dynamic programming). The entries are filled using the following formula

table[0][i] = i
table[i][0] = i

Assume that 0th character is empty, the edit distance between an empty string and a string of length 'i' is always 'i' because by deleting all the 'i' characters, it becomes an empty string.

table[i][j] = table[i-1][j-1] if string1[i] = string2[j]

If string1[i] and string2[j] are equal, we don't need any modifications. Hence it is as same as table[i-1][j-1]

table[i][j] = Min(table[i-1][j],table[i][j-1],table[i-1][j-1]) + 1

If string1[i] and string2[j] are not equal, we have three choices.
  • Modify the differing character string1[i] to match string2[j]. This requires a cost of table[i-1][j-1] + 1
  • Delete string1[i] and try to match the remaining with string2. This requires a cost of table[i-1][j] + 1
  • Insert string1[i] into string2. This requires  a cost of table[i][j-1] + 1.
Finally table[N][M] contains the required answer.

The time and space complexity for this algorithm is O(n * m).
Following is the C++ implementation of the above algorithm.

Monday, December 2, 2013

Valera and Plates - Code forces (Round #216) problem

In this post, we discuss a simple implementation problem from the recently concluded Code forces programming round. The problem description is given below.

Valera is a lazy student. He has m clean bowls and k clean plates.
Valera has made an eating plan for the next n days. As Valera is lazy, he will eat exactly one dish per day. At that, in order to eat a dish, he needs exactly one clean plate or bowl. We know that Valera can cook only two types of dishes. He can eat dishes of the first type from bowls and dishes of the second type from either bowls or plates.
When Valera finishes eating, he leaves a dirty plate/bowl behind. His life philosophy doesn't let him eat from dirty kitchenware. So sometimes he needs to wash his plate/bowl before eating. Find the minimum number of times Valera will need to wash a plate/bowl, if he acts optimally.
The first line of the input contains three integers n, m, k (1 ≤ n, m, k ≤ 1000) — the number of the planned days, the number of clean bowls and the number of clean plates.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 2). If ai equals one, then on day i Valera will eat a first type dish. If ai equals two, then on day i Valera will eat a second type dish.
Print a single integer — the minimum number of times Valera will need to wash a plate/bowl.
Sample test(s)
3 1 1
1 2 1
4 3 1
1 1 1 1
3 1 2
2 2 2
8 2 2
1 2 1 2 1 2 1 2
In the first sample Valera will wash a bowl only on the third day, so the answer is one.

In the second sample, Valera will have the first type of the dish during all four days, and since there are only three bowls, he will wash a bowl exactly once.

In the third sample, Valera will have the second type of dish for all three days, and as they can be eaten from either a plate or a bowl, he will never need to wash a plate/bowl.

We first count how many times he makes type-1 dish and type-2 dish. He eats type-1 dishes only in bowls. 

We first calculate how many cleanings to eat first dish. Let us denote cb as the number of clean bowls and cp as the number of clean plates. Let type1 be the number of first dish type2 be the number of second dish in his plan.

If type1 > cb, We need (type1-cb) cleanings and we are left with 0 clean bowls. Otherwise we need no cleanings , we are left with (cb-type1) bowls.

We add the clean bowls from the previous step to number of clean plates. 
cbp = cb + cp.
If type2 > cbp then we need typ2-cbp cleanings otherwise zero.

Here is the implementation in C++.