Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Find the max number in each row and the min num in each column
Now for every position compare with row max and col min and then print if it is.
O(N+N)
for(int i = 0; i < N ; i++)
{
for(int j =0; j < M ; j++)
{
if(row[i] > arr[i][j])
row[i] = arr[i][j];
if(col[j] < arr[i][j])
col[j] = arr[i][j];
}
}
for (int k = 0 ; k < N ; k++)
if(row[k] == col[k])
{
// got position
}
2 3 4 5
4 5 6 7
1 2 3 0
9 8 7 6
row[] = 3, 3, 2, 0
col[] = 2, 2, 2, 2
First, the complexity is O(N^2) not O(N + N)
Second, the function is not quite correct because the largest number in the ith row is not necessarily the smallest number in the ith column. For example, in the following matrix,
1 2 3
4 5 6
7 8 9
the largest number in the first row is not the smallest number in the first column, but the smallest number in the third column.
Third, the two comparisons in the first nested loop is not quite correct. I think the signs should be reversed. i.e., < should be > and > should be <.
Problem statement says: The biggest in its row and also the smallest in ITs column
so if we take below matrix:
1 2 3
4 5 6
7 8 9
then 3 is biggest in its ROW(i.e 1st row) and smallest in its COLUMN(i.e 3rd column)
//C#
static void display(int[,] _arr)
{
int[] smallestOfColumn = new int[_arr.GetLength(1)];
int[] smallestOfColumni = new int[_arr.GetLength(1)];
int[] smallestOfColumnj = new int[_arr.GetLength(1)];
for (int i = 0; i < _arr.GetLength(0); i++)
{
int biggestOfRow = _arr[i, 0];
int biggestOfRowi = i;
int biggestOfRowj = 0;
for (int j = 0; j < _arr.GetLength(1); j++)
{
if (biggestOfRow < _arr[i, j])
{
biggestOfRow = _arr[i, j];
biggestOfRowi = i;
biggestOfRowj = j;
}
if (i == 0)
{
smallestOfColumn[j] = _arr[i, j];
smallestOfColumni[j] = i;
smallestOfColumnj[j] = j;
}
if (smallestOfColumn[j] > _arr[i, j])
{
smallestOfColumn[j] = _arr[i, j];
smallestOfColumni[j] = i;
smallestOfColumnj[j] = j;
}
}
Console.WriteLine("Biggest of row " + (i + 1) + " is " + biggestOfRow + " at row " + (biggestOfRowi + 1) + " and column " + (biggestOfRowj + 1));
}
for (int j = 0; j < _arr.GetLength(1); j++)
{
Console.WriteLine("Smallest of column " + (j + 1) + " is " + smallestOfColumn[j] + " at row " + (smallestOfColumni[j] + 1) + " and column " + (smallestOfColumnj[j] + 1));
}
}
package com.algorithms;
public class MatrixMaxMinRowCol {
public static void main(String[] args){
int[][] a = {
{9,2,3,18},
{4,5,6,23},
{1,8,9,5}
};
int ROWS = 3;
int COLS = 4;
for ( int i = 0; i < ROWS; i++){
int biggest = a[i][0];
int smallest = a[0][i];
int bigPos = 0;
int smallPos = 0;
for ( int j = 0; j < COLS; j++){
if ( a[i][j] > biggest){
biggest = a[i][j];
bigPos = j;
}
if ( j < ROWS ){
if ( a[j][i] < smallest ){
smallest = a[j][i];
smallPos = j;
}
}
}
System.out.println("Biggest in row "+(i+1)+" is :"+biggest+" Pos is : "+bigPos);
System.out.println("Smallest in col "+(i+1)+" is :"+smallest+" Pos is :"+smallPos);
}
for ( int i = ROWS; i < COLS; i++){
int smallest = a[0][i];
int smallPos = 0;
for ( int j = 0; j < ROWS; j++){
if ( a[j][i] < smallest ){
smallest = a[j][i];
smallPos = j;
}
}
System.out.println("Smallest in col "+(i+1)+" is : "+smallest+" Pos is : "+smallPos);
}
}
}
Output:
Biggest in row 1 is :18 Pos is : 3
Smallest in col 1 is :1 Pos is :2
Biggest in row 2 is :23 Pos is : 3
Smallest in col 2 is :2 Pos is :0
Biggest in row 3 is :9 Pos is : 2
Smallest in col 3 is :3 Pos is :0
Smallest in col 4 is : 5 Pos is : 2
it says printing out those numbers who is the largest in its row and at the same time the smallest in its column, not largest ones in each row and smallest ones in each column
C++
void find(int N, vector<vector<int> >& matrix)
{
vector<int> largestEachRow(N);
vector<int> smallestEachColumn(N);
for(int i = 0; i < N; i++) {
smallestEachColumn[i] = numeric_limits<int>::max();
}
for(int i = 0; i < N; i++) {
int largest = 0;
for(int j = 0; j < N; j++) {
if(matrix[i][j] > matrix[j][largest]) {
// records the position of the largest integer in each row
largest = j;
}
if(matrix[i][j] < smallestEachColumn[j]) {
smallestEachColumn[j] = matrix[i][j];
}
}
largestEachRow[i] = largest;
}
cout << "The qualified integers are at: \n";
for(int i = 0; i < N; i++) {
if(matrix[i][largestEachRow[i]] ==
smallestEachColumn[larestEachRow[i]]) {
cout << "row: " << i << " column: " << largestEachRow[i] << endl;
}
}
}
Time complexity O(N^2). Can't do better because integers are not sorted, to find out the largest integer in each row we must inspect every integer in each row.
just realized that we need to output the positions of elements, not their values.
var m = [
[1,4,7],
[2,5,8],
[3,6,9]
];
var rows = m.length;
var cols = m[0].length;
var maxColumnsInRows = []; // index = row num, value: col num
var minRowsInColumns = [];
for(var i=0; i<rows;i++){
maxColumnsInRows[i] = 0;
minRowsInColumns[i] = 0;
}
for(var ri=0;ri<rows;ri++){
for(var ci=0; ci<cols;ci++){
var currentRowMaxColumn = maxColumnsInRows[ri];
var currentColumnMinRow = minRowsInColumns[ci];
var currentValue = m[ri][ci];
if(currentValue > m[ri][currentRowMaxColumn])
maxColumnsInRows[ri] = ci;
if(currentValue < m[currentColumnMinRow][ci])
minRowsInColumns[ci] = ri;
}
}
for(ri=0; ri<rows;ri++){
var maxCol = maxColumnsInRows[ri];
var minRow = minRowsInColumns[maxCol];
if(ri == minRow){
console.log('row: ' + ri +' ,col: ' + maxCol);
}
}
Find max number in a row. Check if it's min in column.
public void printBiggestInRowSmallestInColumn(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
int maxInRow = Integer.MIN_VALUE;
int maxInRowInd = -1;
for (int j = 0; j < arr.length; j++) {
if (maxInRow < arr[i][j]) {
maxInRow = arr[i][j];
maxInRowInd = j;
}
}
int minInCol = Integer.MAX_VALUE;
int minInColInd = -1;
for (int j = 0; j < arr.length; j++) {
if (minInCol > arr[j][maxInRowInd]) {
minInCol = arr[j][maxInRowInd];
minInColInd = j;
}
}
if (minInColInd == i) {
System.out.println("[" + i + "," + maxInRowInd + "]="
+ arr[i][maxInRowInd]);
}
}
}
#define ROW 3
#define COL 4
int main()
{
int arr[][COL]={{9,2,3,18},
{4,5,6,23},
{1,8,9,5}};
int max=0,min=999;
int *row=(int *)malloc(sizeof(int)*ROW);
int *col=(int *)malloc(sizeof(int)*COL);
int row_index=0,col_index=0;
for(int i=0;i<ROW;i++)
{
for(int j=0;j<COL;j++)
{
if(arr[i][j]>max)
{
max=arr[i][j];
row[row_index]=j;
}
}
max=0;
row_index++;
}
for(int i=0;i<COL;i++)
{
for(int j=0;j<ROW;j++)
{
if(arr[j][i]<min)
{
min=arr[j][i];
col[col_index]=j;
}
}
min=999;
col_index++;
}
for(int i=0;i<ROW;i++)
printf("%d ",row[i]);
printf("\n");
for(int i=0;i<COL;i++)
printf("%d ",col[i]);
getchar();
return 0;
}
public void printCyclic(int[][] table, int iMax, int jMax){ //O(m*n)?
int iMin = 0, jMin = 0; //outer scope of min,max
iMax--; jMax--;
while((iMin <= iMax)|| (jMin <= jMax)){ // Terminate Condition
for(int j = iMin; j<=jMax; j++){
System.out.print(table[iMin][j]);
}iMin++;
for(int i = iMin; i<=iMax; i++){
System.out.print(table[i][jMax]);
}jMax--;
for(int j = jMax; j>=jMin; j--){
System.out.print(table[iMax][j]);
}iMax--;
for(int i = iMax; i>=iMin; i--){
System.out.print(table[i][jMin]);
}jMin++;
}
}
public void findRowMaxColMin(int[][] table, int iMax, int jMax){
int[] colMins = new int[jMax];
Map<Integer, Integer> rowMaxs = new HashMap<Integer, Integer>();
for(int i =0; i<iMax; i++){
int rowMax = 0;
for(int j =0; j<jMax; j++){
if(j == 0)rowMax = table[i][0];
else{
if(table[i][j] > rowMax)
rowMax = table[i][j]; // update max
}
if(i == 0) colMins[j] = table[0][j];
else{
if(colMins[j] < table[i][j])
colMins[j] = table[i][j]; //update min
}
}
rowMaxs.put(rowMax, i); //put the rowMax as elements are unique
}
for(int j = 0; j < jMax; j++){
if(null != rowMaxs.get(colMins[j])){
System.out.println("Element: "+colMins[j]+" Row: "+ rowMaxs.get(colMins[j])+ " Col:"+ j );
}
}//O(n*m), extra space = array[col] and map<int, int>(row)
}
void UniqueInt(int **A, int R, int C) { int ROW[2][R], COL[2][C]; for(int i=0; i<R; i++){ for(int j=0; j<C; j++){ if(ROW[0][i] < A[i][j]){ ROW[0][i] = A[i][j]; ROW[1][i] = j; } if(COL[0][j] > A[i][j]){ COL[0][j] = A[i][j]; COL[1][j] = i; } } } if(R<C){ for(int i=0; i<R; i++){ if(ROW[0][i] == COL[0][ROW[1][i]]) cout << A[i][ROW[1][i]]; } } else { for(int i=0; i<C; i++){ if(COL[0][i] == ROW[0][COL[1][i]]) cout << A[COL[1][i]][i]; } }T(N) = Size of MATRIX, i.e. MXN.
- SRB December 27, 2012S(N) = 2*M + 2*N.