CareerCup

you cant reduce the time complexity further than O(n2) becoz... u have to visit each element at least once , ofcourse, so, tc > O(n2).
further dont use hashing to check for rach rows and columns as it will take space complexity of O(n).
instead,
assign each character from a to z a unique prime number.
find the multiplication of these 26 prime numbers, say m
now find the multiplication of 26 characters present in each rows and columns
if each rows and each columns multiplication match to m.
so return true
else return false..

furthermore, dont think abt to reduce time complexity further.. u cant
u have to go through each element at least for once

take a[52][26] as extra space
now take first element in b[26][26] (given array) say index i=0,j=0 (consider the value inside this array as 0-25 instead of a-z) for example if b[0][0]='c';(here c considered as 'c'-'a'-1=2)
now assign a[0][2]=1 and a[26][2]=1 do like this for entire given array while filling in array a[][] if already it is 1 then the value is repeating if not the given array is perfectly valid.
give your suggestions

void check()
{
String scol = "" ; String srow="";
for(int i = 0 ; i < 26 ;i++)
{
scol = " ";
srow= " ";
for(int j = 0; j<26 ; j++)
{
scol = scol + a[i][j];
srow = srow + a[j][i];
// call method to compare scol and srow for presence of all alphabets . Continue till end of row

}

O(n2)

Here I am using Set variable to check . For every row data will be inserted to this set variable , if after traversing a row size of set is not 26 then return false ;// condition is not satisfied , otherwise go for checking next row .

public boolean checkArray(char array[][])
	{
		int rowLimit=array.length;
		int colLimit=array[0].length;
		int i,j;
		HashSet<Character> set=new HashSet<Character>();
		
		for(i=0;i<rowLimit;i++)
		{
			for(j=0;j<colLimit;j++)
			{
				set.add(array[i][j]);
			}// End of inner for loop
			
			if(set.size()!=26)
			{
				return false; // each row is not having char from a-z
			}
			else
			{
				set.clear();
			}
		}// End of outer for loop
		return true; // each row satisfy required condition
	}

all codes having time complexity O(n^2) anyone with efficient approach
...

public static final int OR= 0x3ffffff;

    public static boolean isValid(char[][] array, int pos, int[] orRow, int[] orCol)
    {
        if(pos==array.length-1)
            return (orCol[pos]|array[pos][pos])==OR&&(orRow[pos]|array[pos][pos])==OR;
        
        int cumRow= orCol[pos], cumCol= orRow[pos];
        
        for(int i=pos; i<array.length; i++)
        {
            cumRow|=0x1<<((int)((int)array[pos][i]-(int)'a'));
            cumCol|=0x1<<((int)((int)array[i][pos]-(int)'a'));
            
            orRow[i]|=0x1<<((int)((int)array[pos][i]-(int)'a'));
            orCol[i]|=0x1<<((int)((int)array[i][pos]-(int)'a'));
        }
        
        return (cumRow==OR&&cumCol==OR)?isValid(array, pos+1, orRow, orCol):false;
    }

Here is solution. It is O(n*n) and additional 8 bytes for storing bits. (does not count local variables). Written on C#. It is possible to eliminate "prev" variable by using "|=" operator, but it will be hard to read.

static int getCharIndex(char c)
    {
      return c - 'a';
    }
    static bool checkArray(char[,] a)
    {
      const int maxChars = 26;
      if (a == null || a.Rank != 2)
        return false;
      int N = a.GetUpperBound(0) + 1;
      if (N > maxChars || a.GetUpperBound(1) + 1 != N)
        return false;
      for (var i = 0; i < N; i++)
      {
        uint row = 0;
        uint col = 0;
        for (var j = 0; j < N; j++)
        {
          int iRow = getCharIndex(a[i, j]);
          if (iRow < 0 || iRow >= N)
            return false;
          uint prev = row;
          row = row | (1u << iRow);
          if (prev >= row)
            return false;
          int iCol = getCharIndex(a[j, i]);
          if (iCol < 0 || iCol >= N)
            return false;
          prev = col;
          col = col | (1u << iCol);
          if (prev >= col)
            return false;
        }
      }
      return true;
    }

I think by using bit mapping it can be solved in o(n*n)
we can have one number.
int l=0;
then
for all i and j
int bit=(a[i][j]/97)*(a[i][j]%97)
if(l&pow(2,bit)!=0)
return false;
l=l | pow(2,bit)
end for

Hey!! I am missing something here, can't we just sum up all the elements for each row and each column to check if all sums are the same unique value. ?

i think if we want to have different alphabet in rows and column the string should be rotated while entering in each row..
abc
bca
cab

i think if we want to have different alphabet in rows and column the string should be rotated while entering in each row..
abc
bca
cab

Each element is accessed once


#include <stdio.h>
void main()
{
char arr[26][26];
int i,j,k=0;
for(i=0;i<26;i++)
{
k = i;
for(j=0;j<26;j++)
{
arr[j][k] = i + 97;
k--;
if(k==-1)
k=25;
}

}
for(i=0;i<26;i++){
for(j=0;j<26;j++)
{
printf("%c ",arr[i][j]);
}
printf("\n");
}
}


Complexity: O(n^2)

const int N = 26;

static inline unsigned long get_character_mark(const char a)
{
	return (1UL << a - 'a');
}

bool judge_matrix(char arr[N][N])
{
	unsigned long sum_arr[2][N];
	memset(sum_arr, 0, sizeof(sum_arr));

	for(int i = 0; i < N; ++i)
	{
		for(int j = 0; j < N; ++j)
		{
			const unsigned long mask = get_character_mark(sum_arr[i][j]);
			if((sum_arr[0][i] & mask) || (sum_arr[1][j] & mask))
			{
				return false;
			}
			else
			{
				sum_arr[0][i] |= mask;
				sum_arr[1][j] |= mask;
			}
		} // for
	} // for

	return true;
} // judge_matrix

My approach:

Compute an XOR of a to z (a^b^c...z).
XOR this value with each row and column. If the row/column contains the set(a-z), this XOR will return 0.

The time complexity in this case will still be O(n*n), but we have at least removed the space complexity.