WAP to print 2D array matrix in Spiral Order

Question: Given a 2D array / matrix of integers. Write a program to print the elements in spiral order. Consider a matrix as show in the diagram to the right. The desired output of the program should be as: 1,2,3,4,8,12,16,20,19,18,17,13,9,5,6, 7,11,15,14,10.




Solution: There are several ways to solve this problem, but I am mentioning a method that is intuitive to understand and easy to implement. The idea is to consider the matrix similar to onion which can be peeled layer after layer. We can use the same approach to print the outer layer of the matrix and keep doing it recursively on a smaller matrix (with 1 less row and 1 less column).

Refer to the image below for a visual explanation. We start by printing the top-right layer of the matrix by calling the print_layer_top_right. It will print 1,2,3,4,8,12,16,20. The print_layer_top_right method then calls the print_layer_bottom_left method which will print 19,18,17,13,9,5. If you observe the size of the target matrix is reducing after each call. Each method basically calls the other method and passes the matrix indexes for the reduced matrix. Both methods take 4 index parameters which represent the target matrix. When the target matrix size is such that there is only one layer left the recursion terminates and by this time the code has printed all the numbers in the full matrix.




Code (C language):

<script type="syntaxhighlighter" class="brush: html"><![CDATA[

#include
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2);
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2);

int main(void)
{
int a[5][4] = {
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16},
{17,18,19,20}
};

print_layer_top_right(a,0,0,3,4);
}

//
// prints the top and right shells of the matrix
//
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;

// print the row
for(i = x1; i<=x2; i++)
{
printf("%d,", a[y1][i]);
}

//print the column
for(j = y1 + 1; j <= y2; j++)
{
printf("%d,", a[j][x2]);
}

// see if we have more cells left
if(x2-x1 > 0)
{
// 'recursively' call the function to print the bottom-left layer
print_layer_bottom_left(a, x1, y1 + 1, x2-1, y2);
}
}

//
// prints the bottom and left shells of the matrix
//
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;

//print the row of the matrix in reverse
for(i = x2; i>=x1; i--)
{
printf("%d,", a[y2][i]);
}

// print the last column of the matrix in reverse
for(j = y2 - 1; j >= y1; j--)
{
printf("%d,", a[j][x1]);
}

if(x2-x1 > 0)
{
// 'recursively' call the function to print the top-right layer
print_layer_top_right(a, x1+1, y1, x2, y2-1);
}
}

]]></script>

Run Here https://ideone.com/ut0Hx

WAP to Write Find MaximumSize Sub-Matrix From Given Matrxi having Size of R*C

Maximum size square sub-matrix with all 1s
April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For example, consider the below binary matrix.

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

The maximum square sub-matrix with all set bits is

1 1 1
1 1 1
1 1 1

Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.

1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]

For the given M[R][C] in above example, constructed S[R][C] would be:

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 2 2 0
1 2 2 3 1
0 0 0 0 0

The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.


C program

#include
#define bool int
#define R 6
#define C 5

/* UTILITY FUNCTIONS */
/* Function to get minimum of three values */

int min(int a, int b, int c)
{
int m = a;
if (m > b)
m = b;
if (m > c)
m = c;
return m;
}

void printMaxSubSquare(bool M[R][C])
{
int i,j;
int S[R][C];
int max_of_s, max_i, max_j;

/* Set first column of S[][]*/
for(i = 0; i < R; i++)
S[i][0] = M[i][0];

/* Set first row of S[][]*/
for(j = 0; j < C; j++)
S[0][j] = M[0][j];

/* Construct other entries of S[][]*/
for(i = 1; i < R; i++)
{
for(j = 1; j < C; j++)
{
if(M[i][j] == 1)
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
else
S[i][j] = 0;
}
}

/* Find the maximum entry, and indexes of maximum entry
in S[][] */
max_of_s = S[0][0]; max_i = 0; max_j = 0;
for(i = 0; i < R; i++)
{
for(j = 0; j < C; j++)
{
if(max_of_s < S[i][j])
{
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}

printf("\n Maximum size sub-matrix is: \n");
for(i = max_i; i > max_i - max_of_s; i--)
{
for(j = max_j; j > max_j - max_of_s; j--)
{
printf("%d ", M[i][j]);
}
printf("\n");
}
}



/* Driver function to test above functions */
int main()
{
bool M[R][C] = {{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0}};

printMaxSubSquare(M);
getchar();
}

Run Here https://ideone.com/oFXO6

Design A DS That Support Insert, delete, Get Operation in O(1) e.g Consant Time

Design a Data Structure with following operations
1.Insert(X) -> insert X if X not present
2.Delete(X) -> delete X if X present
3.Get() -> return any element if it is present

all operations in O(1).
No memory constraint.

Init:

k=0

Insert X:

k = k+1 mod m;
A[X] = k;
B[k] = X;

Search X:

return (A[X] < m) and (B[A[X]] == X)

Delete X:

A[X] = 0;
B[k] = 0;
k = k-1;

WAP to Genrate All Possible Subset of Set S..Thats The Power Set

Algorithm:

Powerset: A recursive algorithm

If S = (a, b, c) then the powerset(S) is the set of all subsets

powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}

The first "trick" is to try to define recursively.

What would be a stop state?
S = () has what powerset(S)?

How get to it?
Reduce set by one element

Consider taking an element out - in the above example, take out {c}

S = (a,b) then powerset(S) = {(), (a), (b), (a,b), }

What is missing?
powerset(S) = { (c), (a,c), (b,c), (a,b,c)}

hmmm
Notice any similarities? Look again...
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}

take any element out

powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} IS

powerset(S - {c}) = {(), (a), (b), (a,b)} unioned with
{c} U powerset(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}

powerset(S) = powerset(S - {e_i}) U ({e_i} U powerset(S - {e_i}))

where e_i is an element of S (a singleton)

Pseudo-algorithm

1. Is the set passed empty? Done
2. If not, take an element out
   • recursively call method on the remainder of the set
   • return the set composed of the Union of
     (1) the powerset of the set without the element (from the recursive call)
     (2) this same set (i.e., (1)) but with each element therein unioned with the element initially taken out

Go backwards:
powerset(S) when S = {()} is {()}
powerset(S) when S = {(a)} is {(), (a)}
powerset(S) when S = {(a,b)} is {(), (a), (b), (a,b)}
etc...


Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.

If S has n elements in it then P(s) will have 2^n elements



1st using Recursion

public class PowerSet {


private void printPowerSet(String inputString, String prefixString, int startIndex){
if(inputString == null){
return;
}
for(int i=startIndex;iString str = "";
str = prefixString + inputString.charAt(i);
System.out.println("{" + str + "}\n");
printPowerSet(inputString, str, i+1);
}

}




public static void main(String args[]){
String inputStr ="123";
System.out.println("{ }\n");
for(int i=0; iPowerSet powerSet = new PowerSet();

System.out.println("{" + inputStr.charAt(i) + "}\n");
powerSet.printPowerSet(inputStr, Character.toString(inputStr.charAt(i)), i+1);

}
}


}

TC O(n^2)
Sc O(n)

Run here https://ideone.com/8RuF1


2nd Iterative Method

Algorithm:

Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
2 Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) If ith bit in counter is set
Print ith element from set for this subset
(b) Print seperator for subsets i.e., newline

Example:

Set = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111

Value of Counter Subset
000 -> Empty set
001 -> a
011 -> ab
100 -> c
101 -> ac
110 -> bc
111 -> abc


#include
#include

void printPowerSet(char *set, int set_size)
{
/*set_size of power set of a set with set_size
n is (2**n -1)*/
unsigned int pow_set_size = pow(2, set_size);
int counter, j;

/*Run from counter 000..0 to 111..1*/
for(counter = 0; counter < pow_set_size; counter++)
{
for(j = 0; j < set_size; j++)
{
/* Check if jth bit in the counter is set
If set then pront jth element from set */
if(counter & (1< printf("%c", set[j]);
}
printf("\n");
}
}

/*Driver program to test printPowerSet*/
int main()
{
char set[] = {'a','b','c','d'};
printPowerSet(set, 4);

getchar();
return 0;
}

TC O(n*2^n)
SC O(1)
Rune Here https://ideone.com/z5tHG


Java program for Doing The Same

class PowerSet {

int arr[]={1,2,3};
int number=0;
void powerSet(){
for(int i=0;iint k=i;
int counter=0;
while(k>0){
if((k & 1) == 1){
System.out.print(arr[counter]);

}
counter++;
k=k>>1;
}
System.out.println();
number++;
}

}
public static void main(String[] args) {
PowerSet p=new PowerSet();
p.powerSet();
System.out.println("Total number of subsets are"+p.number);

}

}

Run Here https://ideone.com/LtjsT


More  http://en.wikipedia.org/wiki/Power_set
http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch1/solutions/recursionSol.html
http://stackoverflow.com/questions/1670862/obtaining-powerset-of-a-set-in-java
http://rosettacode.org/wiki/Power_set
http://ruslanspivak.com/2011/06/09/power-set-generation-a-joy-of-python/
http://www.roseindia.net/tutorial/java/core/powerset.html
http://shriphani.com/blog/2008/03/31/one-step-forward-two-steps-back/
http://planetmath.org/?op=getobj&from=objects&id=136

WAP to Generate Unique Combination from Given Set ot String

What is combination and how is it different from a permutation?

The mathematics' gurus would know this by heart, but I am going to refer to the Wikipedia for a proper definition.

"A combination is an un-ordered collection of unique sizes. (An ordered collection is called a permutation.)" from the Wikipedia article.

For example,

For a given String "ABCD",
a combination of un-ordered collection of unique sizes will be
[ABCD, BCD, ABD, ABC, ACD, AC, AD, AB, BC, BD, CD, D, A, B, C]

From my quick Google search, I also found out

"Number of ways of selecting zero or more things from ‘n’ different things is given by:- ( 2 ^ n - 1 ) "(from this article).

If we apply this formula in the above example, String "ABCD" with length of 4 should have ( 2 * 2 * 2 * 2 ) - 1 = 15 combinations.

This is exaclty what we are going to acheive in our code - Finding all possible combinations of characters from a given String. Note that for simplicity, we are going to assume that the input String (whose different combinations are going to be found) would not have any repetitive characters in it.
What is recursive programming?

Lets get a formal definition from Wikipedia:

"Creating a recursive procedure essentially requires defining a "base case", and then defining rules to break down more complex cases into the base case. Key to a recursive procedure is that with each recursive call, the problem domain must be reduced in such a way that eventually the base case is arrived at."

In very simple terms, a method calling itself again and again until a particular condition is met is called recursive programming.
Implementation:

The algorithm discussed below to solve this problem is chosen for its simplicity and ease of understanding. It may not be the most effective algorithm but it definitely solves this particular problem and is extremely simple.

Some points to note about this problem.

1. The given String itself is one of the combinations. For example, one of the combinations of the String "ABCD" is "ABCD" itself.

2. Every character in the String will be a combination. For example, for the String "ABCD" -- > "A", "B", "C", "D" will be some of the combinations.
Algorithm

To find the combinations of a String:

Step 1: Add the String to the combination results.
Step 2: If the String has just one character in it,
then stop the current line of execution.
Step 3: Create new sub-words from the String by removing one letter at a time.
If the String is "ABCD", form sub-words like "BCD", "ACD", "ABD", "ABC"
Step 4: For each of the sub-word, go to Step 1


import java.io.IOException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

class StringCombinations
{
private Set combinations = new HashSet();

public StringCombinations(String sInputString)
{
generate(sInputString);
System.out.println("*** Generated " + combinations .size() + " combinations ***");
System.out.println(combinations);

}

public void generate(String word)
{
// Add this word to our combination results set
// System.out.println(word);
combinations.add(word);

// If the word has only one character we break the
// recursion
if (word.length() == 1)
{
combinations.add(word);
return;
}

// Go through every position of the word
for (int i = 0; i < word.length(); i++)
{
// Remove the character at the current position
// all call this method with that String (Recursion!)
generate(word.substring(0,i) + word.substring(i+1));
}
}

public static String readCommandLineInput(String inputMessage)
{

String inputLine ="abcd";
return inputLine;
}

public static void main(String args[])
{
// Request and read user input
String sInstruction = "Enter a String: \n";
String sInputString = readCommandLineInput(sInstruction);
new StringCombinations(sInputString);
}

}// End of StringCombinations

Run Here https://ideone.com/EPV9i

Another Informative Link http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117

Dominator of an array ...Majority Element In Different Way

Majority Element Different Possible Solutions


Solution 1: A basic solution is to scan entire array for checking for every element in the array. If any element occurs more than n/2 time, prints it and break the loop. This will be of O(n^2) complexity.

Solution 2: Sort the entire array in O(nlogn) and then in one pass keep counting the elements. This will be of O(nlogn) + O() = O(nlogn) complexity. #try it

Solution 3 Using BitCount Array

#include
int findmaj(int arr[], int n)
{
int bitcount[32];
int i, j, x;

for(i = 0; i < 32; i++)
bitcount[i] = 0;
for (i = 0; i < n; i++)
for (j = 0; j < 32; j++)
if (arr[i] & (1 << j)) // if bit j is on
bitcount[j]++;
else
bitcount[j]--;

x = 0;
for (i = 0; i < 32; i++)
if (bitcount[i] > 0)
x = x | (1 << i);
return x;
}

int main()
{
int i;
int arr[5] = {1, 3 ,1, 1, 3};

printf(" %d ", findmaj(arr, 5));

getchar();
return 0;
}

We keep a count of frequency of each of the bits. Since majority element will dominate the frequency count, hence we can get its value.

The solution is constant space and linear time : O(n)

Method 4 (Using Binary Search Tree)

Node of the Binary Search Tree (used in this approach) will be as follows. ?
struct tree
{
int element;
int count;
}BST;

Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.
The method works well for the cases where n/2+1 occurrences of the majority element is present in the starting of the array, for example {1, 1, 1, 1, 1, 2, 3, 4}.

Time Complexity: If a binary search tree is used then time complexity will be O(n^2). If a self-balancing-binary-search tree is used then O(nlogn)
Auxiliary Space: O(n)

METHOD 5 (Using Moore’s Voting Algorithm)

This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.

1. Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.

findCandidate(a[], size)
1. Initialize index and count of majority element
maj_index = 0, count = 1
2. Loop for i = 1 to size – 1
(a)If a[maj_index] == a[i]
count++
(b)Else
count--;
(c)If count == 0
maj_index = i;
count = 1
3. Return a[maj_index]

Above algorithm loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1.
First Phase algorithm gives us a candidate element. In second phase we need to check if the candidate is really a majority element. Second phase is simple and can be easily done in O(n). We just need to check if count of the candidate element is greater than n/2.

Example:
A[] = 2, 2, 3, 5, 2, 2, 6
Initialize:
maj_index = 0, count = 1 –> candidate ‘2?
2, 2, 3, 5, 2, 2, 6

Same as a[maj_index] => count = 2
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 1
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 0
Since count = 0, change candidate for majority element to 5 => maj_index = 3, count = 1
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 0
Since count = 0, change candidate for majority element to 2 => maj_index = 4
2, 2, 3, 5, 2, 2, 6

Same as a[maj_index] => count = 2
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 1

Finally candidate for majority element is 2.

First step uses Moore’s Voting Algorithm to get a candidate for majority element.

2. Check if the element obtained in step 1 is majority

printMajority (a[], size)
1. Find the candidate for majority
2. If candidate is majority. i.e., appears more than n/2 times.
Print the candidate
3. Else
Print "NONE"

# include<stdio.h>
# define bool int

int findCandidate(int *, int);
bool isMajority(int *, int, int);

void printMajority(int a[], int size)
{
int cand = findCandidate(a, size);

if(isMajority(a, size, cand))
printf(" %d ", cand);
else
printf("NO Majority Element");
}

int findCandidate(int a[], int size)
{
int maj_index = 0, count = 1;
int i;
for(i = 1; i < size; i++)
{
if(a[maj_index] == a[i])
count++;
else
count--;
if(count == 0)
{
maj_index = i;
count = 1;
}
}
return a[maj_index];
}

bool isMajority(int a[], int size, int cand)
{
int i, count = 0;
for (i = 0; i < size; i++)
if(a[i] == cand)
count++;
if (count > size/2)
return 1;
else
return 0;
}

int main()
{
int a[] = {1, 3, 3, 1,1,1,2,3,1,2,1,1};
printMajority(a, 12);
getchar();
return 0;
}

Time Complexity: O(n)
Auxiliary Space : O(1)
Run Here http://ideone.com/ALf5fY

WAP to Remove The Node From Binary Search Tree

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Give a binary search tree and a number,
inserts a new node with the given number in
the correct place in the tree. Returns the new
root pointer which the caller should then use
(the standard trick to avoid using reference
parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);

/* return the (unchanged) node pointer */
return node;
}
}

struct node* search(struct node* tmp, struct node** parent,struct node* item)
{
struct node* root;
root=tmp;

if(!root)
{
//*parent=NULL;
return NULL;
}
if(root->data==item->data)
{
return root;
}

*parent=root;

if(item->data<=root->data)
{
return search(root->left,parent,item);
}
else
{

return search(root->right,parent,item);
}

}

void deletes(struct node* root,struct node* srch)
{
struct node* parent;
struct node* succ=NULL;

if(!root)
return;

parent=NULL;

struct node* x=search(root,&parent,srch);

/* if the node to be deleted has no child */
if(x->left==NULL && x->right==NULL)
{

if(parent->left==x)
parent->left=NULL;
else
parent->right=NULL;

free(x);
return;
}


/* if the node to be deleted has only rightchild */
if (x->left == NULL && x->right!= NULL )
{
if ( parent->left == x )
parent->left = x->right ;
else
parent->right= x->right;

free ( x ) ;
return ;
}

/* if the node to be deleted has only left child */
if (x->left != NULL && x->right== NULL )
{
if ( parent->left == x )
parent->left= x->left ;
else
parent->right = x->left ;

free ( x ) ;
return ;
}


/* if the node to be deleted has two children */

if(x->left!=NULL && x->right!=NULL)
{
parent=x;
succ=x->right;

while(succ->left!=NULL)
{
parent=succ;
succ=succ->left;
}

x->data=succ->data;
x=succ;
free(x);//free(succ).....problem Might be here I dont Know why
}
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;

/* first recur on left child */
printInorder(node->left);

/* then print the data of node */
printf("%d ", node->data);

/* now recur on right child */
printInorder(node->right);
}


/* Driver program to test sameTree function*/
int main()
{
struct node* root = NULL;
root = insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 6);
insert(root, 5);

struct node* parent= NULL;

root=search(root,&parent,root->left->right);
printf(" %d %d ", root->data, parent->data);

deletes(root,root->left->right);

printInorder(root);

getchar();
return 0;
}