## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
2
of 2 vote

Algo:
1. start scanning from right most end of first row and find first occurrence of 0.
suppose it is some value x.
then max_numer of 1 till now is col-x-1.
2. then go to next row but start from x. if you found 1 at that place then scan this row and find new x as in first step and replace max_number by new value of col-x-1.
3. repeat it till last row mean while if you get x=-1 then return the length of col.

if anyone want code i can provide.

Comment hidden because of low score. Click to expand.
0

What's the time complexity? Is it less than O(nlogn)? I think it would be O(nlogn) if you used binary search in each row to find the first occurrence of 1.

Comment hidden because of low score. Click to expand.
0

complexity should be O(max(m, n)). each row at least we need scan once, and for each column, at most we scan once.

Comment hidden because of low score. Click to expand.
0

sorry, should be O(m+n), consider it is a line from top-right to bottom-left.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

Here is the code in java:

``````public int maxOnesInMatrix(int[][]A, int row, int col){
int count =0;
if(A[0][0]==1){
count = col;
}
else{
for(int i=0; i< row; i++){
if(count==col-1){
break;
}
int oldCount =count;
for(int j= col-oldCount-1; j >=0; j--){
if(A[i][j]==0){
break;
}
count++;
}
}
}

return count;
}``````

Comment hidden because of low score. Click to expand.
0

correct in scanning the columns but for the rows, just go for binary search

Comment hidden because of low score. Click to expand.
0

Off by 1 inside for loop,

{{
if(count==col){
break;
}
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Scan each row from top to bottom. We count the number of 1s for each row. At the end of a each row scan we update the row index that has more number of 1s. This may be a brute force solution with O(n2). I am sure there exists a better approach.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Binary search on each row until finding i s.t a[i] = 1 and a[i-1] = 0
return row which has smallest i.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Say a[i][j]is given - Start scanning a[0][0..n]
int result = 0;
int pos = 0;
for(i=0;i<m;++i) {
for(j=0;j<n;++j) {
if(a[i][j] == 1 && j == 0 ) {
result = i + 1; break;
}
if(a[i][j] == 1 && j < pos ) {
result = i + 1;
pos = j;
}
}
}

print result;

Comment hidden because of low score. Click to expand.
0
of 0 vote

1.) Get index of 1st 1 of 1st row with binary search, keep as minindex.
2.) Now loop from second row.
If row[minindex] is 1
Get minindex by step 1 for this row;
Else
Continue;

3.) Row on which minindex found is the row contains maximum 1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be solved by applying binary search.
Here is the solution code..

#include<iostream>

#include<conio.h>

using namespace std;
int arr[5][5]={{1,1,1,1,1},{0,0,0,1,1},{0,1,1,1,1},{0,1,1,1,1},{1,1,1,1,1}};
int scanlist(int arr[][5],int result[],int mid,int count)
{
int curcount=0;
for(int i=0;i<count;i++)
{
if(arr[result[i]][mid]==1)
{
result[curcount]=result[i];
curcount++;

}

}
return curcount;
}

int find(int arr[][5],int n)
{
int start=0,end=n-1;
int result[5]={0,1,2,3,4};
int count=5;
while(start<=end)
{
int mid=(start+end)/2;

count=scanlist(arr,result,mid,count);
if(count==0)
{
start=mid+1;
}
else if(count==1)
{
cout<<"Row is "<<result[0]<<endl;
return result[0];
}
else{
end=mid-1;
}
}
int i=0;
while(i<count){
cout<<"Row is "<<result[i]<<endl;
i++;
}

return result[0];
}

int main()
{
find(arr,5);
getch();
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I wrote the next solution in google doc. It uses binary serach so the time complexity is O(m * lg n)

``````public class Main{
private int leftmostBinSearch(int [] arr, int v, int l, int r){
if(l > r) return -1;
int mid = l + (r - l) / 2;
if(arr[mid] == v){
int leftmost = leftmostBinSearch(arr, v, l, mid - 1);
if(leftmost > -1)
return leftmost;
return mid;
}
if(arr[mid] < v)
leftmostBinSearch(arr, v, mid + 1, r);
if(arr[mid] > v)
leftmostBinSearch(arr, v, l, mid - 1);
return -1;
}
public int findRow(int [][] arr){
if(arr == NULL) return -1;
int rows = arr[0].length;
int maxIndex = -1;
int maxQuantity = -1;
for(int i = 0; i < rows; i++){
int currentQuantity = leftmostBinSearch(arr[i], 1);
if(currentQuantity > maxQuantity){
maxQuantity = currentQuantity;
maxIndex = i;
}
}
return maxIndex;
}
}``````

Comment hidden because of low score. Click to expand.
0

I guess this is good enough.
Just a slight improvement:
- when you call leftmostBinSearch within the 'for' loop, first check whether the arr[i][maxQuantity-1] is '1'.
- If yes, only then call leftmostBinSearch and that too by passing it the values: l = 0, r = maxQuantity-1.
- Else, there is no use as we are not interested in anything less than the maxQuantity we already have.

This will improve the performance (although the complexity will still be written as O(m*logn))

Comment hidden because of low score. Click to expand.
0
of 0 vote

Just do a binary search on each column, the row that has the first 1 will be the answer since rows are sorted.

``````int GetRowWithMaxOne(int[,] matrix)
{
for (int i = 0; i < matrix.GetLength(1); i++)
{
int row = DoBinarySearch(matrix, i, 1, 0, matrix.GetLength(1));
if (row != -1) { return row; }
}
return -1;
}

int DoBinarySearch(int[,] matrix, int i, int low, int high, int x)
{
if (low > high)
{
return -1;
}
int mid = low + (high - low) / 2;

if (matrix[i, mid] == x)
{
return mid;
}

if (matrix[i,mid] > x)
{
return DoBinarySearch(matrix, i, low, mid - 1, x);
}
return DoBinarySearch(matrix, i, mid + 1, high, x);``````

}

Comment hidden because of low score. Click to expand.
0

Sorry I made a mistake when I call the DobinarySearch in the first method. Here is the corrected one....all in c#

``````int GetRowWithMaxOne(int[,] matrix)
{
for (int i = 0; i < matrix.GetLength(1); i++)
{
int row = DoBinarySearch(matrix, i, 0, matrix.GetLength(1),0);
if (row != -1) { return row; }
}
return -1;``````

}

Comment hidden because of low score. Click to expand.
0

``````Sorry I made a mistake when I call the DobinarySearch in the first method. Here is the corrected one....all in c#

int GetRowWithMaxOne(int[,] matrix)
{
for (int i = 0; i < matrix.GetLength(1); i++)
{
int row = DoBinarySearch(matrix, i, 0, matrix.GetLength(1),1);
if (row != -1) { return row; }
}
return -1;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int M[1000][1000], row, col ;
cout << "Enter row :";
cin>>row;
cout <<endl << "Enter col :";
cin>>col;

for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
cin >> M[i][j];

int count;
count = 0;

for (int i=0; i<=row; i++)
{
count = 0;
for(int j=0; j<=col; j++)
{
if(M[i][j] == 1)
{
count++;
}
}
if(count > col/2)
{
cout << "Row no" << i + 1;

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

outer loop binary search. inner loop each line.
1. If at that column, no line is 1, move column cursor left (binary jump).
2. If found one line has 1, remove all lines having 0 on that column until another line having 1 is found.
3. If two lines are found, move column cursor right (binary jump).
4. If there is only one line left, return that line.
5. If there is no column to move, return the first line of the array (all lines having same number of 1s).

``````<?php
function findMaxOnes(\$a) {
\$nl = count(\$a);
if (\$nl == 0) return null;
\$nc = count(\$a[0]);
\$s = 0;
\$e = \$nc - 1;
while (\$s <= \$e) {
\$founds = 0;
\$m = (int)((\$s + \$e) / 2);
foreach (\$a as \$i => \$l) {
if (\$l[\$m] == 1) {
if (\$founds == 0) {
\$founds = 1;
foreach (\$a as \$j => \$ll) {
if (\$j == \$i) break;
unset(\$a[\$j]);
}
} elseif (\$founds == 1) {
\$e = \$m - 1;
break;
}
} elseif (\$founds == 1) {
unset(\$a[\$i]);
}
}
if (\$founds == 0) {
\$s = \$m + 1;
}
if (count(\$a) == 1) {
return reset(\$a);
}
}
return reset(\$a);
}
\$a = [[0, 0, 0, 1,],
[1, 1, 1, 1,],
[0, 0, 1, 1,],
[0, 1, 1, 1,],
];
var_dump(findMaxOnes(\$a));``````

Comment hidden because of low score. Click to expand.
0

worst case, all are 0s: O(mlogn).
average O(2logn).

Comment hidden because of low score. Click to expand.
0
of 0 vote

Java Code
Complexity: O(mlogn)

``````public class ZerosOnesIn2DArray {

public static void main(String[] args) {
int arr[][] = {{0,0,0,1},{0,1,1,1},{1,1,1,1},{0,0,1,1}};
System.out.println(new ZerosOnesIn2DArray().getMaxOnesRow(arr));
}

public int getMaxOnesRow(int[][] arr){
int row = arr.length;
int col = arr[0].length;
int temp[]=arr[0];
int maxOnesLoc = binarySearch(arr[0], 0, col, 1);
int maxOnesRow = 0;
for(int i=1;i<row;i++){
if(arr[i][maxOnesLoc]==1){
int currOnesLoc = binarySearch(arr[i], 0, maxOnesLoc, 1);
if(currOnesLoc<maxOnesLoc){
maxOnesLoc = currOnesLoc;
maxOnesRow = i;
}
}

}

return maxOnesRow;
}
public int binarySearch(int []arr, int low, int high, int val)
{
if(high<low){
return -1;
}
int mid =(low+high)/2;
int output = 0;
if(arr[mid]<val){
low = mid+1;
output =binarySearch(arr, low, high, val);
}
else if(arr[mid]>val){
high = mid-1;
output =binarySearch(arr, low, high, val);
}
else{
if(mid!=0 && arr[mid-1]==val){
high = mid-1;
output =binarySearch(arr, low, high, val);
}
else{
output = mid;
}
}
return output;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Add the numbers in each row and return the row with the highest sum

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
* Solution:
* Convert the bits in each row to a number
* store max_number while comparing
* Complexity: O(n)
* Better solution would be O(logn)
*/
main()
{
int arr[][4] =
{
{0,0,0,1},
{0,0,1,1},
{0,1,1,1},
{1,1,1,1}
};
int max_num =0;
int max_row =0;
unsigned int num     =0;
int i =0;
for(i=0;i<4;i++)
{
num = arr[i][0] | (arr[i][1] << 1UL) | (arr[i][2] << 2UL)| (arr[i][3] << 3UL);
if(num > max_num)
{
max_num = num;
max_row = i;
}
}
printf("\nMax num of 1 are in row =%d\n",max_row);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
* Earlier tried with O(n)
* but that is not correct. If we make a large array then it boils down to O(n2)
* Following is an effort for O(nlog(n))
*/
{
int small_index =1;
int large_index =4;  /* Number of columns */
int middle_index = (small_index + large_index)/2;
int row =0;
int lowest_pos = 4; /* At max pos */
int pos =0;
for(i=0;i<4;i++)
{
small_index =1;
large_index =4;  /* Number of columns */
while(1)
{
if(small_index > large_index)
break;
if(arr[i][middle_index] == 1)
{
large_index = middle_index-1;
pos = middle_index;
}
else
{
small_index = middle_index +1;
}
middle_index = (small_index + large_index)/2;
}
if(pos < lowest_pos)
{
lowest_pos = pos;
row = i;
}
}

printf("\n By O(nlog(n)) Menthod: Max num of 1 are in row =%d\n",row);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.DataInputStream;
import java.io.IOException;

public class MatrixCount {

public static void main(String[] args) throws NumberFormatException, IOException{
int arr[][] = new int[4][4];
int max =0;

System.out.println("Matrix");
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
DataInputStream dis = new DataInputStream(System.in);
}
}
for(int i=0;i<4;i++){
int count =0;
for(int j=0;j<4;j++){
if(arr[i][j] == 1){
count ++;
}
}
if(count > max){
max = count;
}
}
System.out.println("Max 1's "+max);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my code in Java that uses a binary search to solve the problem. This implementation of binary search is aware of duplicates, and returns the first position where the element being searched occurs in the array.

In case of more than one row in the matrix contains the same number of 1's, the latest row will be returned. This can be easily fixed maintaining a data structure to store all indexes with the same result of binary search.

``````public class JobInterviewQuestion {

public static void main(String[] args) {
final int[][] m = {
{0, 0, 0, 1}, // Row 1
{1, 1, 1, 1}, // Row 2
{0, 0, 1, 1}, // Row 3
{0, 1, 1, 1}, // Row 4
};
System.out.println("The row that contains maximum number of 1s is: " + findMaxNumberOf1s(m));
}

//Time complexity: O(nlog(n))
public static int findMaxNumberOf1s(final int[][] m) {
int smallerPos = m.length;
int maxRow = -1;
for (int r = 0; r < m.length; r++) {
final int currPos = binarySearchFirstPosition(m[r], 1);
if (currPos < smallerPos) {
smallerPos = currPos;
maxRow = r;
}
}
return maxRow + 1;
}

//Time complexity: O(log(n))
private static int binarySearchFirstPosition(final int[] a, final int value) {

int lo = 0;
int hi = a.length - 1;

while (lo <= hi) {
final int mid = (lo + hi) / 2;
if (value < a[mid]) hi = mid - 1;
else if (value > a[mid]) lo = mid + 1;
else if (mid - 1 >= lo && a[mid - 1] == a[mid]) hi = mid - 1;
else return mid;
}
return -1;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Given that rows are sorted:

public static int getRowWithMaxOnes(int[][] matrix) {
int i=0,j=0;
while(true){
if(matrix[i][j]==1){
return i;
}
else{
i++;
}
if(i==matrix.length) {
j++;
i=0;
}

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it is like Radix Sorting, but scan from most left digit.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int max_num_one(int [][] matrix, int row, int col)
{
int maxrow = 0;
int num_one = col;

for(int i=0; i<row;++i){
for (int j = 0; j < col; ++j){
if(matrix[i][j] == 1){
if (j == 0)
return i;
else{
if(j < num_one){
max_row = i;
num_one = j;
}
break;
}
}
}
}

return maxrow;
}``````

Comment hidden because of low score. Click to expand.
0

By the way, this code will not work if there is no '1' in the matrix

Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution is here the complexity is O(n + m)
geeksforgeeks.org/find-the-row-with-maximum-number-1s

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// Method 2: O(n) start at position [0][n - 1]
// if we see 1 we move left (j--)
// if we see 0 we move down (i++)
int maximumRow2(int **a, int rows, int cols) {
int maxRow = -1;
int i = 0;
int j = cols - 1;
while (i < rows - 1 && j > 0) {
if (a[i][j] == 1) {
j--;
maxRow = i;
} else {
i++;
}
}
return i;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. scan for each row with first occurence position of 1 in it. store the position in a array, if not found use some large numbr.
2. once all rows are completed, check the position array to have lower number. then that index+1 is the row with max sum

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int row = -1;
for(int i=0; i<n.length; i++){
// Start scan from right end
int zeroPos = -1;
for(int j=n[i].length-1; j>=0; j--){
if(n[i][j] == 0){
zeroPos = j;
break;
}
}
if(zeroPos == -1){
row = i;
break;
} else {
int thisRow = n[i].length - 1 - zeroPos;
if(thisRow > row){
row = i;
}
}
}
System.out.println(row);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.practice.algo.and.ds.bitmanipulation;

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

int[][] arr = {{0,0,0,1},{1,1,1,1},{0,0,1,1},{0,1,1,1}};
int n = 1;
for(int i =0;i<3;i++){
n |=(n<<1);
}
int count = Integer.MIN_VALUE;
for(int i=0;i<arr.length;i++){
String str = "";
for(int j=0;j<arr.length;j++){
str+=arr[i][j];
}
int c= Integer.bitCount(Integer.parseInt(str, 2) & n);
if(c > count){
count = c;
}

}
System.out.println(count);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

//Algorithm
traverse column wize, Stop the element which has 1
//
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

int MyArray[10][10];

void main(int argc, char **argv)
{
int Row = 0;
int Col = 0;
//Get the number of row and column
printf("Enter the number of rows ");
scanf("%d",&Row);
printf("\nEnter the number of Col ");
scanf("%d",&Col);
// Get the array
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf("\n Enter the element Row %d Col %d -->",i,j);
scanf("%d",&MyArray[i][j]);
}
}

for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf(" %d",MyArray[i][j]);
}
printf("\n");
}

/// *** Logic Starts from Here ***///
for(int j=0; j < Col; j++)
{
int sum= 0;
int i;
for(i=0; i < Row; i++)
{
if(MyArray[i][j])
{
break;
}
}
if(i < Row)
{
//We got an row with 1
printf("row %d you are looking for",i);
break;
}
}
getch();
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse column wize. Stop to the element which has 1.

``````#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

int MyArray[10][10];

void main(int argc, char **argv)
{
int Row = 0;
int Col = 0;
//Get the number of row and column
printf("Enter the number of rows ");
scanf("%d",&Row);
printf("\nEnter the number of Col ");
scanf("%d",&Col);
// Get the array
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf("\n Enter the element Row %d Col %d -->",i,j);
scanf("%d",&MyArray[i][j]);
}
}

for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf(" %d",MyArray[i][j]);
}
printf("\n");
}

/// *** Logic Starts from Here ***///
for(int j=0; j < Col; j++)
{
int sum= 0;
int i;
for(i=0; i < Row; i++)
{
if(MyArray[i][j])
{
break;
}
}
if(i < Row)
{
//We got an row with 1
printf("row %d you are looking for",i);
break;
}
}
getch();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

int MyArray[10][10];

void main(int argc, char **argv)
{
int Row = 0;
int Col = 0;
//Get the number of row and column
printf("Enter the number of rows ");
scanf("%d",&Row);
printf("\nEnter the number of Col ");
scanf("%d",&Col);
// Get the array
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf("\n Enter the element Row %d Col %d -->",i,j);
scanf("%d",&MyArray[i][j]);
}
}

for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf(" %d",MyArray[i][j]);
}
printf("\n");
}

/// *** Logic Starts from Here ***///
for(int j=0; j < Col; j++)
{
int sum= 0;
int i;
for(i=0; i < Row; i++)
{
if(MyArray[i][j])
{
break;
}
}
if(i < Row)
{
//We got an row with 1
printf("row %d you are looking for",i);
break;
}
}
getch();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

int MyArray[10][10];

void main(int argc, char **argv)
{
int Row = 0;
int Col = 0;
//Get the number of row and column
printf("Enter the number of rows ");
scanf("%d",&Row);
printf("\nEnter the number of Col ");
scanf("%d",&Col);
// Get the array
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf("\n Enter the element Row %d Col %d -->",i,j);
scanf("%d",&MyArray[i][j]);
}
}

for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf(" %d",MyArray[i][j]);
}
printf("\n");
}

/// *** Logic Starts from Here ***///
for(int j=0; j < Col; j++)
{
int sum= 0;
int i;
for(i=0; i < Row; i++)
{
if(MyArray[i][j])
{
break;
}
}
if(i < Row)
{
//We got an row with 1
printf("row %d you are looking for",i);
break;
}
}
getch();
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

int MyArray[10][10];

void main(int argc, char **argv)
{
int Row = 0;
int Col = 0;
//Get the number of row and column
printf("Enter the number of rows ");
scanf("%d",&Row);
printf("\nEnter the number of Col ");
scanf("%d",&Col);
// Get the array
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf("\n Enter the element Row %d Col %d -->",i,j);
scanf("%d",&MyArray[i][j]);
}
}

for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf(" %d",MyArray[i][j]);
}
printf("\n");
}

/// *** Logic Starts from Here ***///
for(int j=0; j < Col; j++)
{
int sum= 0;
int i;
for(i=0; i < Row; i++)
{
if(MyArray[i][j])
{
break;
}
}
if(i < Row)
{
//We got an row with 1
printf("row %d you are looking for",i);
break;
}
}
getch();``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include "stdio.h"
#include "conio.h"
#include "stdlib.h"

int MyArray[10][10];

void main(int argc, char **argv)
{
int Row = 0;
int Col = 0;
//Get the number of row and column
printf("Enter the number of rows ");
scanf("%d",&Row);
printf("\nEnter the number of Col ");
scanf("%d",&Col);
// Get the array
for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf("\n Enter the element Row %d Col %d -->",i,j);
scanf("%d",&MyArray[i][j]);
}
}

for(int i = 0; i < Row; i++)
{
for(int j = 0 ; j < Col; j++)
{
printf(" %d",MyArray[i][j]);
}
printf("\n");
}

/// *** Logic Starts from Here ***///
for(int j=0; j < Col; j++)
{
int sum= 0;
int i;
for(i=0; i < Row; i++)
{
if(MyArray[i][j])
{
break;
}
}
if(i < Row)
{
//We got an row with 1
printf("row %d you are looking for",i);
break;
}
}
getch();``````

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Y cant we traverse columns. presence of 1 in the Zeroth index of the row means that is the row which contains the maximum number of 1s. Please correct me if i am wrong.

My idea is

for(i=0;i<m;i++)
{
for (j=0;j<n;j++)
{
if(a[j][i]=='1')
{
break;
}
}
}

The value in the arraylist+1 gives the Row wiith max num of 1s.

Comment hidden because of low score. Click to expand.
-1
of 3 vote

This is a very simple question:
since it is already sorted on each row, the first 1 you find while scanning top to bottom on each column will be the row with the max 1's.

``````int findRowWithMaxNumberOfOnes(int[][] matrix, int len, int hight)
{
for(int i=0; i<len; i++) //scanning column on each row
for(int j=0; j<hight; j++) //scanning the column
if(matrix[j][i] == 1)
return j;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

(above was my answer- i was just not signed in)
BTW- if all of the rows contains all ones than return the first row is fine.

Comment hidden because of low score. Click to expand.
1
of 1 vote

In the worst case , when all are zero except the one at right bottom, it takes O(m*n).... I like your idea but instead lets do binary search on column for number 1 ---- in this case the worst case will be O(mlogn)

Comment hidden because of low score. Click to expand.
0

Here is O(mlogn) implementation in c#

int GetRowWithMaxOne(int[,] matrix)
{
for (int i = 0; i < matrix.GetLength(1); i++)
{
int row = DoBinarySearch(matrix, i, 1, 0, matrix.GetLength(1));
if (row != -1) { return row; }
}
return -1;
}

int DoBinarySearch(int[,] matrix, int i, int low, int high, int x)
{
if (low > high)
{
return -1;
}
int mid = low + (high - low) / 2;

if (matrix[i, mid] == x)
{
return mid;
}

if (matrix[i,mid] > x)
{
return DoBinarySearch(matrix, i, low, mid - 1, x);
}
return DoBinarySearch(matrix, i, mid + 1, high, x);

}

Comment hidden because of low score. Click to expand.
0

This code will not work if the following input is given

00111
01111
00011

It will return the first row, not second row.

Comment hidden because of low score. Click to expand.
0

The problem is simple but your solution isn't. O(mn) complexity for computation.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.