# Largest Square in a Matrix of NxN - C++ Program Code

Here is the C++ program to solve the problem of finding the largest square in a matrix of a given size NxN. Here i have put two versions of the program one which gives the matrix and other which give a Char* output as asked in TechGig coding challenge.

In the program the input is provided through a char* input array and then converted for manipulations. Please don't completely rely on my program, as i am still learning programming (always will be learning).

Suggestions are welcomed and in case you have a better program, please post it in the comment section.

Note: For Techgig code challenge you need to work on the output a bit as the testcases are not getting passed, even though the default testcase gets passed.

C++ For TechGig Code Challange (Geekathon):

#include string.h
#include stdio.h
#include iostream
#include string
#include sstream

using namespace std;

/* 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;
}

char* biggestSquare(char* input1[])
{
int tROW=0,tCOL=0;
bool gotColumnCount = false;

/*------- Get count of rows and column in a given input ------*/

for (int i=0,COL=0;input1[i]!=NULL;i++){

string inputData(input1[i]);
char* c = &inputData[0];

for (;*c;c++)
{
if(gotColumnCount==false && *c!='#'){
tCOL++;
}
}

gotColumnCount = true;
tROW=i+1;
}

/*------ Allocating memory for matrix array -------*/

int matrixData[50][50];

/*------ Creating matrix array from char* -------*/

for (int i=0;input1[i]!=NULL;i++){

string inputData(input1[i]);
int colCount=0;
char* c = &inputData[0];

for (;*c;c++)
{
if(*c!='#'){

if (*c=='1'){
matrixData[i][colCount] = 1;
}else{
matrixData[i][colCount] = 0;
}

//cout << "Test" << matrixData[i][colCount];
colCount++;
}
}
}

int sumMatrix[50][50];

int max_of_s, max_i, max_j;

/* Get first column */
for(int i = 0; i < tCOL; i++)
sumMatrix[i][0] = matrixData[i][0];

/* Get first row */
for(int j = 0; j < tCOL; j++)
sumMatrix[0][j] = matrixData[0][j];

/* Get other entries */
for(int i = 1; i < tROW; i++)
{
for(int j = 1; j < tCOL; j++)
{
if(matrixData[i][j] == 1)
sumMatrix[i][j] = min(sumMatrix[i][j-1], sumMatrix[i-1][j], sumMatrix[i-1][j-1]) + 1;
else
sumMatrix[i][j] = 0;
}
}

/* Find the maximum entry, and indexes of maximum entry in sumMatrix */
max_of_s = sumMatrix[0][0]; max_i = 0; max_j = 0;

for(int i = 0; i < tROW; i++)
{
for(int j = 0; j < tCOL; j++)
{
if(max_of_s < sumMatrix[i][j])
{
max_of_s = sumMatrix[i][j];
max_i = i;
max_j = j;
}
}
}

//cout << "\n Maximum size sub-matrix is: \n";

string largeSquare;

largeSquare = "{";

cout << max_i  << "  " << max_of_s  << max_j << "\n";

int reduceConst = max_j;

for(int i = max_i; i > max_i - max_of_s; i--)
{
largeSquare = largeSquare + "(";

for(int j = max_j; j > max_j - max_of_s; j--)
{
stringstream ss,ff;

ff << max_j - j;
ss << max_i - reduceConst;

//cout << i << "  " << j << "\n";

if (((i-1)==(max_i - max_of_s))&&((j-1)==( max_j - max_of_s))){
largeSquare = largeSquare + ss.str() + "#" + ff.str() + ")}";
}else{
if (((j-1)==( max_j - max_of_s))){
largeSquare = largeSquare + ss.str() + "#" + ff.str();
}else{
largeSquare = largeSquare + ss.str() + "#" + ff.str() + ",";
}
}

}
reduceConst--;

if ((i-1)!=(max_i - max_of_s))
largeSquare = largeSquare + "),";
}

return &largeSquare[0];
}

C++ programs for Visual Studio 2012:

#include "stdafx.h"

#include cstdio
#include iostream
#include string
#include sstream

using namespace std;

/* 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;
}

char* biggestSquare(char* input[])
{
int tROW=0,tCOL=0;
bool gotColumnCount = false;

/*------- Get count of rows and column in a given input ------*/

for (int i=0,COL=0;input[i]!=NULL;i++){

string inputData(input[i]);

char* c = &inputData[0];

for (;*c;c++)
{
if(gotColumnCount==false && *c!='#'){

tCOL++;
}
}

gotColumnCount = true;

tROW=i+1;

}

/*------ Allocating memory for matrix array -------*/

int **matrixData;

matrixData=new int*[tROW]; //creates a new array of pointers to int objects

for(int i=0; i        matrixData[i]=new int[tCOL];

/*------ Creating matrix array from char* -------*/

for (int i=0;input[i]!=NULL;i++){

string inputData(input[i]);

int colCount=0;

char* c = &inputData[0];

for (;*c;c++)
{
if(*c!='#'){

if (*c=='1'){
matrixData[i][colCount] = 1;
}else{
matrixData[i][colCount] = 0;
}

//cout << "Test" << matrixData[i][colCount];
colCount++;
}
}
}

int **sumMatrix;

sumMatrix=new int*[tROW]; //creates a new array of pointers to int objects

for(int i=0; i        sumMatrix[i]=new int[tCOL];

int max_of_s, max_i, max_j;

/* Set first column of S[][]*/
for(int i = 0; i < tCOL; i++)
sumMatrix[i][0] = matrixData[i][0];

/* Set first row of S[][]*/
for(int j = 0; j < tCOL; j++)
sumMatrix[0][j] = matrixData[0][j];

/* Construct other entries of S[][]*/
for(int i = 1; i < tROW; i++)
{
for(int j = 1; j < tCOL; j++)
{
if(matrixData[i][j] == 1)
sumMatrix[i][j] = min(sumMatrix[i][j-1], sumMatrix[i-1][j], sumMatrix[i-1][j-1]) + 1;
else
sumMatrix[i][j] = 0;
}
}

/* Find the maximum entry, and indexes of maximum entry in S[][] */
max_of_s = sumMatrix[0][0]; max_i = 0; max_j = 0;

for(int i = 0; i < tROW; i++)
{
for(int j = 0; j < tCOL; j++)
{
if(max_of_s < sumMatrix[i][j])
{
max_of_s = sumMatrix[i][j];
max_i = i;
max_j = j;
}
}
}

cout << "\n Maximum size sub-matrix is: \n";

string largeSquare;

largeSquare = "{";

cout << max_i  << "  " << max_of_s  << max_j << "\n";

int reduceConst = max_j;

for(int i = max_i; i > max_i - max_of_s; i--)
{
largeSquare = largeSquare + "(";

for(int j = max_j; j > max_j - max_of_s; j--)
{
stringstream ss,ff;

if (((i-1)==(max_i - max_of_s))&&((j-1)==( max_j - max_of_s))){
ff << max_j - j;
ss << max_i - reduceConst;
largeSquare = largeSquare + ss.str() + "#" + ff.str() + ")}";
}else{
if (((j-1)==( max_j - max_of_s))){
ff << max_j - j;
ss << max_i - reduceConst;
largeSquare = largeSquare + ss.str() + "#" + ff.str();
}else{
ff << max_j - j;
ss << max_i - reduceConst;
largeSquare = largeSquare + ss.str() + "#" + ff.str() + ",";
}
}

}
reduceConst--;

if ((i-1)!=(max_i - max_of_s))
largeSquare = largeSquare + "),";
}

cout << &largeSquare[0];

}

int _tmain(int argc, _TCHAR* argv[])
{

char *input[10] = {"0#1#1#1#0#1#0#1","1#0#1#0#0#0#0#1","0#0#0#1#0#1#0#0","1#1#1#1#1#0#0#1","1#1#1#1#0#1#1#1","1#1#1#1#0#1#1#1","1#1#1#1#1#1#1#1","1#1#0#1#0#0#1#1"};

biggestSquare(input);

system("PAUSE");
return 0;
}