CareerCup

int func ( int a[], int m, int n )
{

int row;
i = m;
j = n;
while( i >= 0 && j >=0 )
{
if( a[i][j] )
{
j--;
row =i;
}
else
i--;
}
return(row);
}

The idea here is to scan right until you reach a 1, then scan down until you reach a 0, then right until you reach a 1, continue this cycle and record when you reach a new 1. This will be your max row.

#include <stdio.h>

int findRowMaxOnes(int *arr, int m, int n)
{
	int i = 0, j = n-1;
	while(!((i == m) || (j < 0)))
	{
		if (*((arr+i*n)+j) == 1)
			j--;
		
		if (*((arr+i*n)+j) == 0)
			i++;
	}
	return n-j-1;

}


int main()
{
	int ans;
	int arr[6][10] = {
			{0,0,0,0,0,1,1,1,1,1},
			{0,0,0,0,0,0,1,1,1,1},
			{0,0,0,0,1,1,1,1,1,1},
			{0,0,0,1,1,1,1,1,1,1},
			{0,0,0,0,0,0,1,1,1,1},
			{0,0,1,1,1,1,1,1,1,1},
			};

	ans = findRowMaxOnes((int *)arr, 6, 10);
	printf("%d\n", ans);
}

public class MatrixWithMaxOnes
    {
        public int FindRowWithMaxOnes(int[][] matrix)
        {
            int maxRow = 0, index=0, prevIndex =0;
            for(int i =0;i<matrix.Length;i++)
            {
                index = BinarySearch(matrix[i], 0, matrix[i].Length-1);
                
                if (index <= prevIndex)
                {
                    prevIndex = index;
                    index = 0;
                    maxRow = i;
                }
            }
            return maxRow;
        }

        public int BinarySearch(int[] array, int start, int end)
        {
            if (start <= end)
            {
                int mid = (start + end) / 2;
                if((mid ==0 || array[mid-1]<1) && array[mid]==1)
                {
                    return mid;
                }
                else if (array[mid] < 1)
                {
                    return BinarySearch(array, mid + 1, end);
                }
                else
                {
                    return BinarySearch(array, start, mid - 1);
                }
            }
            return -1;
        }

    }

Since each row starts with 0's and followed by 1's you need to scan the rows according to column - worst case if will be O(MN) runtime

public int findRow(int[][] arr) {
		for (int col=arr[0].length; col++)
			for(int row=0; row<arr.length; row++)
				if(arr[row][col] == 1)
					return row;
		
		return -1;
	}

def mostOnesRow(matrix)
	mostOnesRow = 0
	soonestOneCol = matrix[0].size

	0.step(matrix.size - 1, 1) do |row|
		0.step(matrix[row].size - 1, 1) do |col|
			next if col > soonestOneCol 
			if matrix[row][col] == 1
				soonestOneCol = col
				mostOnesRow   = row
			end
		end
	end
	return mostOnesRow
end

typedef class CArray<int, int> CIntArray;

void GetRowWithMaxOnes(int** Array, int numRows, int numCols, CIntArray &myArray)
{
myArray.RemoveAll();
if (Array == NULL || *Array == NULL ||numRows < 1 || numCols < 1) return ;
bool foundOne = false;
for (int i = 0; i < numCols; i++)
{
for (int j = 0; j < numRows; j++)
{
if(Array[j][i] == 1)
{
foundOne = true;
myArray.Add(j+1);
}
}
if (foundOne) break;
}
}

I am returning an Array instead of int because there can be more than one row with the same (MAX) value of ones

binary search on the rows, at each iteration, if there are both 0 and 1 under the heads, sift the heads above 0, and move the rest of the heads to left. if there are only 0 under the heads, move the heads to the right, if there are only 1 under the heads, move the heads to the left. run time O(m lg^2 n)

#include <stdio.h>

int findRowMaxOnes(int *arr, int m, int n)
{
#if 0
int i,j;
for (i=0; i<m; i++)
{
for (j=0; j<n; j++)
//printf("%d ", *((arr+i*n)+j));
printf("\n");
}
return 0;
#endif

int i = 0, j = n-1;
while(!((i == m) || (j < 0)))
{
if (*((arr+i*n)+j) == 1)
j--;

if (*((arr+i*n)+j) == 0)
i++;
}
return n-j-1;

}


int main()
{
int ans;
int arr[6][10] = {
{0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1,1},
{0,0,0,0,1,1,1,1,1,1},
{0,0,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1,1},
{0,0,1,1,1,1,1,1,1,1},
};

ans = findRowMaxOnes((int *)arr, 6, 10);
printf("%d\n", ans);
}

public int findMaxRow(int[][] arr)
{
int max=0;
int rowWithMax=0;
for (int row=0; row < arr.length; row++)
{
int tempMax=0;
for(int col=0; col<arr[0].length; col++)
{
if(arr[row][col] == 1)
{
tempMax=tempMax+1;
}
}

if ( tempMax > max)
{
max=tempMax;
rowWithMax=row;
}

}
return rowWithMax;
}

public int findMaxRow(int[][] arr)
{
int max=0;
int rowWithMax=0;
for (int row=0; row < arr.length; row++)
{
int tempMax=0;
for(int col=0; col<arr[0].length; col++)
{
if(arr[row][col] == 1)
{
tempMax=tempMax+1;
}
}

if ( tempMax > max)
{
max=tempMax;
rowWithMax=row;
}

}
return rowWithMax;
}

Solutions can be done in

O(n)

or

O(log(n))

For first row we can use binary search to find the ending of 0 or starting of 1. for next row we can continue from the last row since we only need to find the lower (i.e. left side of the current index of 1.

public class maxOnes {
	public static int[][] inputArr = { { 0, 0, 0, 1, 1, 1, 1, 1 },
			{ 0, 0, 0, 0, 1, 1, 1, 1 }, { 0, 0, 1, 1, 1, 1, 1, 1 },
			{ 0, 1, 1, 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 1, 1, 1, 1 } };
	
	public static int maxRow=0;
	public static void moveLeft(int row){
		for (int i = 0; i < inputArr[0].length; i++) {
			if(inputArr[row][i]==1){
				maxRow=row;
				moveDown(row,i);
				break;
			}
		}
	}

	public static void moveDown(int row,int col){
		for (int i = row+1; i < inputArr.length; i++) {
			if(inputArr[i][col]==1){
				maxRow=i;
				moveRight(i, col);
				break;
			}
		}
	}
	
	public static void moveRight(int row,int col){
		for (int i = col; i >=0; i--) {
			if(inputArr[row][i]==0){
				moveDown(row, i+1);
				break;
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		moveLeft(0);
		System.out.println(maxRow);
	}

}

public class maxOnes {
	public static int[][] inputArr = { { 0, 0, 0, 1, 1, 1, 1, 1 },
			{ 0, 0, 0, 0, 1, 1, 1, 1 }, { 0, 0, 1, 1, 1, 1, 1, 1 },
			{ 0, 1, 1, 1, 1, 1, 1, 1 }, { 0, 0, 0, 0, 1, 1, 1, 1 } };
	
	public static int maxRow=0;
	public static void moveLeft(int row){
		for (int i = 0; i < inputArr[0].length; i++) {
			if(inputArr[row][i]==1){
				maxRow=row;
				moveDown(row,i);
				break;
			}
		}
	}

	public static void moveDown(int row,int col){
		for (int i = row+1; i < inputArr.length; i++) {
			if(inputArr[i][col]==1){
				maxRow=i;
				moveRight(i, col);
				break;
			}
		}
	}
	
	public static void moveRight(int row,int col){
		for (int i = col; i >=0; i--) {
			if(inputArr[row][i]==0){
				moveDown(row, i+1);
				break;
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		moveLeft(0);
		System.out.println(maxRow);
	}

}

public class MatrixWithMaxOnes
    {
        public int FindRowWithMaxOnes(int[][] matrix)
        {
            int maxRow = 0, index=0, prevIndex =0;
            for(int i =0;i<matrix.Length;i++)
            {
                index = BinarySearch(matrix[i], 0, matrix[i].Length-1);
                
                if (index <= prevIndex)
                {
                    prevIndex = index;
                    index = 0;
                    maxRow = i;
                }
            }
            return maxRow;
        }

        public int BinarySearch(int[] array, int start, int end)
        {
            if (start <= end)
            {
                int mid = (start + end) / 2;
                if((mid ==0 || array[mid-1]<1) && array[mid]==1)
                {
                    return mid;
                }
                else if (array[mid] < 1)
                {
                    return BinarySearch(array, mid + 1, end);
                }
                else
                {
                    return BinarySearch(array, start, mid - 1);
                }
            }
            return -1;
        }

    }

The max value which can be in any row is no. of columns, with this in mind we need to start column based search starting from left most column i.e., with column id 0, this search cannot be binary search or any other optimized as each row value is not incremental(or we don't know) whenever we find first 1 in our column based search we found our row, the value will be =
no. of columns - found_col_id or max_column_id - found_col_id + 1

public int MaxRow(int[][] m)
{
int row=0,col=0,oldMaxRow=0;
//Find first occurence of 1 in row=0;
while(row < m.Length)
{
if(m[row][col]==1)
{
col--; break;
}
else
col++;
}
//try to move down till you hit 0, then move left in the same row;
// repeate till the last row.
while(col<m[0].Length && row < m.Length)
{
//if you hit 1 in down then update column
if(m[row][col]==1)
{
oldMaxRow=row;
while(col>=0){ if( m[row][col]==1) col--; else break; }
}
//else move down further to search 1
else row++;
}

return row;

}

public int MaxRow(int[][] m)
{
int row=0,col=0,oldMaxRow=0;
//Find first occurence of 1 in row=0;
while(row < m.Length)
{
if(m[row][col]==1)
{
col--; break;
}
else
col++;
}
//try to move down till you hit 0, then move left in the same row;
// repeate till the last row.
while(col<m[0].Length && row < m.Length)
{
//if you hit 1 in down then update column
if(m[row][col]==1)
{
oldMaxRow=row;
while(col>=0){ if( m[row][col]==1) col--; else break; }
}
//else move down further to search 1
else row++;
}

return row;

}

public int MaxRow(int[][] m)
	{
		int row=0,col=0,oldMaxRow=0;
		//Find first occurence of 1 in row=0;
		while(row < m.Length)
		{
			if(m[row][col]==1) 
			{
				col--; break;
			}
			else
			col++;
		}
		//try to move down till you hit 0, then move left in the same row;
		// repeate till the last row.
		while(col<m[0].Length && row < m.Length)
		{
			//if you hit 1 in down then update column
			if(m[row][col]==1)
			{
				oldMaxRow=row;
				while(col>=0){ if( m[row][col]==1) col--; else break; }
			}
			//else move down further to search 1
			else row++;
		}
		
		return row;

}

private static int FindLargestRow(int[,] array, int n)
        {
            var largestRow = -1;
            var maxNonZeroCells = 0;

            for (int i = 0; i < n; i++)
            {
                for (int j = n - 1 - maxNonZeroCells; j >= 0; j--)
                {
                    if (array[i, j] == 1)
                    {
                        var nonZeroCells = n - j;
                        if (nonZeroCells > maxNonZeroCells)
                        {
                            maxNonZeroCells = nonZeroCells;
                            largestRow = i;
                        }
                    }
                    else
                        break;
                }
            }
            return largestRow;
        }

A <- Input Matrix
start with A[1] and figure out the first 1 lets the index was j
for k = 2 to n
     if A[k][j] equals 1 then
     while(j > 0 and A[k][j] == 1)
	  j = j -1;
     j = j +1
output n-j as max size, one can save k as well to tell which row

public class bSearch {

    public static void main(String[] args){
        int[][] matrix = {
            {0,0,0,0,0,1,1,1,1,1},
            {0,0,0,0,0,0,1,1,1,1},
            {0,0,0,0,1,1,1,1,1,1},
            {0,0,0,1,1,1,1,1,1,1},
            {0,0,0,0,0,0,1,1,1,1},
            {0,0,1,1,1,1,1,1,1,1},
        };
        System.out.println(maxOnes(matrix));

    }

    private static int maxOnes(int[][] matrix){
        int m = matrix.length;
        int n = matrix[0].length;
        int l = 0; int r = n;
        for(int i = 0; i < m; i++){
            if(matrix[i][r -1] == 1) {
                r = bSearch(matrix[i], l, r -1);
            }
        }
        return n - r;
    }

    private static int bSearch(int[] nums, int l, int r){
        int x = r;
        while(l <= r){
            int mid = l + ((r-l) >>1);
            if(nums[mid] == 1){
                x = mid;
                r = mid -1;
            } else l = mid + 1;
        }
        return x;
    }
}

private static int RowWithMaxOne(int[,] input)
    {
        int maxRow = input.GetLength(0);
        int maxCol = input.GetLength(1);
        int row = 0;
        int col = maxCol - 1;
        int result = 0;
        while (row < maxRow && col >= 0)
        {
            if (input[row, col] == 1)
            {
                col--;
                result = row;
            }
            else
                row++;
        }
        return result;
    }