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

Thursday, November 28, 2013

Maximum numbers in a sliding window

Given an array of N values and a value K, Write a program to print the maximum of all the sliding windows (sub-array) of size K.

For example let us consider the following array as input 

[4, 5, 3, 2, 6, 1, 2, 3, 8, 4]

Let as take the sliding window of size 3. The output will be as follows

Sliding Window           Maximum
[4, 5, 3]                  5
[5, 3, 2]                  5
[3, 2, 6]                  6
[2, 6, 1]                  6
[6, 1, 2]                  6
[1, 2, 3]                  3
[2, 3, 8]                  8
[3, 8, 4]                  8

The brute force solution can be to find the maximum of each sliding window when we move forward by one element. In an array of size n, there will be (n-k+1) sliding windows of size k. For each window, it takes O(k) time to find the maximum. So, it's time complexity is O( (n-k+1)* k ) ~= O(n*k).

Can we do better than this?

Yes! this problem can be efficiently solved using the dequeue data structure. Dequeue data structure supports inserting and deleting the elements at both ends of the queue via push_back(), pop_back(), push_front() and pop_front(). Here is how the algorithm works. 

We maintain the indices of elements of the current window in a dequeue. We also make sure that the maximum element always appear in the front of the queue. The new element is added at the back of the queue by deleting all the smaller elements before it. We will also delete the element just went out of scope (previous window element). In each iteration we print the front of the queue which is maximum.

Here is the C++ implementation of this algorithm.

Friday, November 22, 2013

Inserting an element into sorted linked list

Given a sorted linked list write a program to insert data into it's correct position. 
For example consider the following linked list

1 -> 3 -> 4 -> 5 

Inserting 2 should change the list to

1 -> 2 -> 3 -> 4 -> 5

Inserting 0 should change it to

0 -> 1 -> 2 -> 3 -> 4 ->5

Inserting 6 should change it to

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6. 

The three examples indicate three different cases to be considered while inserting into a sorted linked list.

Case 1: List can be empty or new element is added as the first element
Case 2: New element can be inserted anywhere in the middle of the linked list
Case 3: New element is added as the last element.

The following diagram illustrates the insert process.

In the following C++ program case 1 is handled in one block and case 2 and 3 are handled in the last block.

Thursday, November 21, 2013

Finding K-size sub array with minimum sum

Given an array of size N and a number K. We have to find the sub-array of size K such that the sum of it's elements is minimum among all K-size sub arrays.

For example Let us consider the following array of size 10. 

{1, 2, 1, 3, 1, 1, 1, 4, 2, 3}

The smallest sub-array of size 3 is {1, 1, 1} which starts at the index 4 (0-based index).

We can use the following algorithm.

We calculate the sum of first K numbers initially and assume that this is the minimum sum and the index is 0. We maintain a variable to track the running sum of K values.

When we move the sliding window by one element, we subtract the previous element add the current element to the running sum. Then we update the minimum sum if the latest sum is less than minimum sum.

This procedure is repeated till the sliding window reaches the end of the array.

Here is the C++ implementation.

Wednesday, November 20, 2013

Finding two numbers occuring once

Given an array containing all elements twice except two numbers. Write a program to find those two numbers.
For example let us consider the following array
{2, 3, 2, 1, 4, 1, 4, 5} 
The answer is {3,5} because they appear only once and all remaining elements appear twice.
This question is somewhat similar to earlier post. This gives us a hint to use XOR operation to solve this problem. Let us see how we can utilize XOR operation.

We first find the XOR of all the elements in the array. This gives a bit pattern which is an XOR of required two values because all other elements occurs twice they get zeroed out.

For the above example the xor value is 0110 = 0011 ^ 0101

Let the two unique numbers are x, y. The next problem is how to find x,y from this xor value. Let us denote ith bit is the first set bit in the xor result. We divide all the numbers in the array into two parts. One part containing all the numbers with bit i = 1, and the other part containing all the numbers with bit i = 0;

This partition segregates the numbers such that all the pairs with ith bit 1 goes to one partition and all pairs with ith bit 0. But x and y fall into two different buckets their bit patterns will be different.

Now finding the XOR value of these partitions separately gives us the required result.

In the above example. The XOR value has 1st bit as 1.
{2,2,3} forms one partition and {1,1,4,4,5} forms another partition.

Parition-1    Partion-2
0010          0001
0011          0100
0010          0001
 0011(3)     0101(5)
 So 3,5 are the answers

Here is the Java code to do this.

Tuesday, November 19, 2013

Number of bits to change from one number to other

Given two numbers, calculate the number of bits required to change from one number to the other.

For example 12 in binary can be represented as 1100. 15 is represented as 1111. We need to change two bits to convert one number from the other as the last two bits are different.

We can find out the difference bits as follows. We first find out the XOR of two numbers. This gives us a bit pattern in which there is a set bit, if two bits differ. Then we can calculate the number of set bits in the XOR which gives the required answer.

Here is C++ code for this.

Monday, November 18, 2013

Pair swapping in a linked list

Given a singly linked list, we have to swap the adjacent nodes in it.

For example some input/output samples are given below

Input                              output
1->2->3->4->X                      2->1->4->3->X
1->2->3->4->5->X                   2->1->4->3->5->X
1->X                               1->X

The algorithm is very simple. We have to move pair by pair and swap the data part of each pair. 

Here is the C++ code for this.

Friday, November 15, 2013

Printing the prime factorization of a given number

How do we write a program to find the prime factorization of a given number?

For example prime factorization for 18 can written as 2 * 3 * 3 or 2 * 3 ^ 2.
For any number there is only one possible prime factorization. 

An efficient algorithm can be given as follows. we run a loop with i ranging from 2 to sqrt(n). In each iteration, we try to reduce the number by dividing it with i as many times as possible. As we examined in the last post, we can find all the factors of a number by checking the divisibility of it from 1 to square root of n itself.

Here is the C++ code to do this.

Thursday, November 14, 2013

Finding all the factors of a given number

Given a number, how do we write a program to find all of it's factors or divisors.
For example, for the number 18, the factors are {1, 2, 3, 6, 9, 18}.

An immediate algorithm that comes to our mind is to run a loop from 1 to n. In each iteration check if the counter divides the number n. If it divides print it.
for( i = 1; i <= n; i++ )
    if( n % i == 0 )
        cout << i << " ";
But this approach runs for n iterations. we can do better than this. One possible improvement can be to start with 1 and n as factors and run the loop from 2 to n/2. This is based on the observation that after n/2 there will not be any factors of n until n. So it is safer to stop at n/2 itself.
for( i = 2; i <= n/2; i++ )
    if( n % i == 0 )
This is clearly an improvement over the previous method because it runs only for n/2 iterations. Can we still improve this?  

Yes it is possible! This is based on the observation that the factors always appear in pairs. If a is a factor of n, then there should be some k such that a * k = n. so k must also be a factor of n. This approach runs only for sqrt(n) iterations and performs better than the previous two algorithms.
for( i = 2; i <= sqrt(n); i++ )
    if( n % i == 0 )
       if( i != sqrt(n) )

Wednesday, November 13, 2013

constant pointers and pointer to constant

In this post we talk a little bit about the constant pointers and pointer to a constant and the difference between them.

In C programming, pointer is a crucial concept and it is always good to have a clear understanding of the fundamentals.

Constant pointers:
Constant pointer as the name indicates is a pointer whose value can not be changed. In another way, once a pointer is initialized with an address of a variable, it can not point to any other variable further. We can also say it is a read-only pointer. For example, take a look the following code snippet.
int var1 = 1, var2 = 2;
int * const pVar = &var1; //constant pointer to an integer
pVar = &var2; //Incorrect, gives a compilation error
We have declared two variables var1, and var2. A constant pointer pVar is initialized to point to var1. In the next statement we are trying to point pVar to var2 which is incorrect and gives a compilation error as follows.
[Error] assignment of read-only variable 'pVar1'
A constant pointer is useless if we don't initialize it with any address. The compiler gives no error in this case, but that pointer is useless because it can not point to any object further.
int count = 10;
int * const pCount;//Valid code;no compiler error
pCount = &count; //Invalid; compiler error
Pointer to constant:
A pointer to a constant object. This means that we can not modify the object addressed by this pointer. But we can always read the object via this pointer and also we can make this pointer to address another object. To understand this, let us look at the following code snippet.
int var = 1, other = 2;
const int *pVar =&var; //pointer to a constant
*pVar = 10;//error:assignment of read-only location'*pVar1'
printf("%d", *pVar); // Valid; we can always read the value
pVar = &other; //valid
We can also create a constant pointer to a constant with the following code. Through this pointer we can not change the value, and we can not make it point to any other object. 
int var = 100, other = 200;
const int * const pVar = &var;//constant pointer to a constant
*pVar = 10;//Error:assignment of read-only location'*pVar1'
pVar = &other; //Invalid; compiler error
other = var / 10; //valid; we can read the value

Tuesday, November 12, 2013

Reverse a single linked list

Given a singly linked list, how do we reverse it by re-arranging the links?

For example if the given linked list is  1 -> 2 -> 3 -> NULL. The output of reverse method should be 3 -> 2 -> 1 -> NULL.

The following diagram shows the simple steps to perform the reversal.

And here is the C++ code which includes both recursive and iterative versions of reversal method.

Monday, November 11, 2013

Printing the matrix in a spiral order

Given a two dimensional array or a matrix, how do we write a program to print the elements in a spiral order.

For example the spiral order for the following matrix is
1  2  3  4  8  12  16  15  14  13  9  5  6  7  11  10

1   2   3   4
5   6   7   8
9  10  11  12
13 14  15  16 

The algorithm for this problem involves four steps. 
  • Print the elements of the top row from left to right and increment top.
  • Print the elements of right column from top to bottom and decrement right.
  • Print the elements of bottom tow from right to left and decrement bottom.
  • Print the elements of left column from bottom to top and increment left.
Repeat the above steps until there are no more elements left. 
As the algorithm indicates, we need four variables to keep track of the top and bottom rows, left and right columns. We also use an extra variable for the direction. It can have four values indicating four possible directions.

Here is the Java implementation of the above algorithm.

Saturday, November 9, 2013

Reversing a doubly linked list

Given a doubly linked list, how do we reverse it by just re-arranging the pointers?

Here is an example of input/output.

The following picture depicts how we re-arrange the pointers.

Here is the Java implementation.

Wednesday, November 6, 2013

Checking if any anagram of a given string is palindrome or not

Given a string, how do we check if any anagram of it can be a palindrome?

For example let us consider the string "AAC". An anagram of it is "ACA" which is a palindrome. We have to write a method which takes a string and outputs true if we can form a palindrome from any anagram of the given string. Otherwise outputs false.

We can immediately think of a solution where we can generate all anagrams of the given string and check if there is any palindrome exists. But this approach is very lengthy and has exponential time complexity (O(n!)).

The key to solve this problem efficiently is to understand how a palindrome is formed. We all know that a palindrome reads the same when you read from left to right or right to left. 

A palindrome can be broken into two halves. where in the first half is the reverse of second half. In case of odd length of strings, we have to ignore the middle character.

So for every character in the first half, there is a corresponding matching character in the second half. This indicates that all the characters in a string must occur even number of times except for one which appears in the middle of the string.

Hence if we check if there is at most one character with odd occurrences in the string we can say that we can form a palindrome from any anagram.
Here is the Java code which implements this algorithm. For simplicity, I assumed that the input string contains only lowercase English alphabets.

Tuesday, November 5, 2013

Merge two sorted linked lists

Given two sorted linked lists, how do we merge them without using any extra space. That means we have to re-arrange the links to form a single sorted linked list.

For example let us consider the following two sorted lists as input.
1 -> 3 -> 5 -> 7
2 -> 4 -> 6 -> 8
The output should be
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

The algorithm is simple. We take the smaller node between the two lists in each iteration, and add it to the result list. We do this until we process any of the list to completion. If there is any remaining portion of the other list, we join it with the result list.

Here is the C++ code do this.

Monday, November 4, 2013

Merging k sorted lists

Given K sorted lists, how to merge them into a single sorted list?

Let total number of elements in K sorted lists is N. We have to form a single sorted list of length N.

For example let us consider the following input lists
{4, 19, 27}
{1, 6, 50, 73}
{9, 45, 59, 67}

The output should be {1, 4, 6, 9, 19, 27, 45, 50, 59, 67, 73}.

In this post, we discuss an efficient approach by using priority queues (heaps). This problem is one of the nice examples of using priority queues.

Here is how the algorithm works.
  1. Add the first elements from all the lists into a priority queue along with their list indices.
  2. Until the priority queue is empty, do the following
    1. Remove the minimum element from the priority queue and add it to the result list. Let this minimum element belongs to min_list.
    2. Add the next element from min_list to the priority queue if there exists at least one element.
Here is the Java implementation of the above algorithm.

Time complexity of this algorithm is O(N log K) as we have N elements in total, and insert and remove-min operation of the priority queue takes O(log k) time.

Saturday, November 2, 2013

Level order traversal of a binary tree

Given a binary tree, we have to print the data level wise. 
For example level order traversal of the following tree produces the sequence 5,3,8,2,4,6,1,7.
The hint to solve this problem is to use a Queue data structure. We start by inserting the root node into the queue. Until the queue is empty, we remove the first element from the queue and insert it's left and right children at the last.

This will give us the level order traversal of the binary tree. For example look at the queue state at each iteration.
Here is the C++ program which contains the level order traversal function.

Friday, November 1, 2013

Finding the minimum and maximum elements in a binary seach tree

Given a binary search tree, how do we find the maximum and minimum elements in it?

For example in the given tree, the maximum element is 8 and the minimum element is 1.
This algorithm is based on the following simple observation.
In a Binary search tree, the minimum element always lies on the left most node and the maximum element always lies on the right most node.
Here is the simple implementation of this algorithm in C++.

Thursday, October 31, 2013

Traversals of a binary tree

Traversal algorithms of non-linear data structures like trees are designed to visit/print all the elements in that structure.

There are three main traversals of the binary tree. Namely
  • In-order traversal
  • Post-order traversal
  • Pre-order traversal
In addition to these, there are inverses of the above algorithms, and there is a level order traversal.

In this post we will see the three main traversal algorithms mentioned above. All of these are defined as recursive algorithms.
In In-order traversal, we first visit the left sub-tree, then root, and then the right sub-tree.
In Post-order traversal, we first visit the left sub-tree, then the right sub-tree, and then the root.
In Pre-order traversal, We first visit the root, then visit the left sub-tree and then visit the right sub-tree.
For example consider the simple  3 node binary tree
In-order traversal: B  A  C
Post-order traversal: B  C  A
Pre-order traversal: A  B  C

To consider a bigger example, take the following binary search tree and it's traversal sequences for the three algorithms.
In-order: 1  2  3  4  5  6  7  8
Post-order: 1  2  4  3  7  6  8  5
Pre-order: 5  3  2  1  4  8  6  7 
The in-order traversal of the binary search tree always produces the sorted order of it's elements.
Here is the C++ code for all the traversals.

Wednesday, October 30, 2013

Finding the height of the binary tree

Given a binary tree how to find the height of the tree. 
It is defined as the number of nodes in the longest path from root to any leaf.
 We can assume that the height of empty tree is 0 and the height of a tree with just root node as 1. For example the below tree has a height of 4.

We can calculate the height of the tree using recursive method very easily. It is based on the observation that height of a binary tree is 
1 + Max( height(left-sub-tree), height(right-sub-tree) )

Here is the C++ code which implements this simple algorithm.

Tuesday, October 29, 2013

Subset sum problem

Given a set of numbers and a target value, we have to find if there is any subset whose sum is equal to the target value.

For example let the array be {10, 34, 19, 27, 58, 45} and the target sum is 56, we have a subset {10,19,27} with the given sum. We don't have any subset with sum 100.

A simple recursive solution can be given as follows. We pass the array, the starting index, and target sum to the function. 
At each index we have two choices:
  • Include the current element and search for {sum - current_num} in the remaining set of elements.
  • Exclude the current element and search for sum in the remaining set of elements.
public static boolean hasSum(int [] array, int start, int sum)
        if( sum == 0 ) //found the sum?
            return true;
        if( start > array.length-1 )//reached end of the array?
            return false;
        return hasSum(array, start+1, sum) || hasSum(array, start+1, sum-array[start]);

But this algorithm has an exponential time complexity which is not efficient. 
Let us look at more efficient approach based on Dynamic programming.

We take a boolean matrix of size (sum+1) x (N+1) where sum is the target sum and N is the size of the given set.

matrix[i][j] = true; indicates that there is a subset of array[0..j-1] which contains the sum i.

We initialize the following entries as base values.
  • matrix[0][j] = true; where 1 <= j <= N since in any set there will be empty subset with sum 0;
  • matrix[i][0] = false; where 1 <= i <= sum since we can't find a sum > 0 in an empty array.
We calculate the remaining entries as follows.
matrix[i][j] = matrix[i][j-1];
If there exists a subset of array[0..j-2] with the sum i; then there should be a subset of array[0..j-1]also with the sum i.

If i >= array[j-1]; we check to see if matrix[i - array[j-1]][j-1] is true. This means check if there is any subset of array[0..j-2] with sum i-array[j-1].
If there is, then we assign true to this entry.

Finally we return the value at matrix[sum][N] which indicates true if there is a subset of array[0..N-1] with the given sum. Otherwise false.

Here is the Java code which implements this.