CareerCup

1. Start from top right corner.
2. Go left if it has 1 on its left, down otherwise
3. We find the longest 1 sequence in O(m+n).

We keep count of the longest sequence.

Reiterate over the collumn where the longest ends
And print the row info if it has a 1 on that position.

Binary search each row to find the starting location of 1s. This will have a O(m*log(n)) run time.

"1. Start from top right corner.
2. Go left if it has 1 on its left, down otherwise
3. We find the longest 1 sequence in O(m+n).

We keep count of the longest sequence.

Reiterate over the collumn where the longest ends
And print the row info if it has a 1 on that position."

Your answer is good but I think it is incomplete, what if the last row in the example matrix had one more 1, the sequence you found in step 3 might not be the longest, one fix could be to iterate over the column where the current longest sequence begins and try to reapply steps 1 and 2. You must also keep track of the current max length and the position of the row that you found it and if there are no more rows to reapply steps 1 and 2 then you know you got the longest sequence and you can start printing the positions. I think the complexity should stay the same.

Binary search each row to find the first location of 1. This will have a run time of O(m*log(n))

pretty easy in recursion - DP - C#.

public void RecursionColumnWise(int[,] matrix, int rowSize, int colSize, int row = 0, int col = 0)
        {
            if (col > colSize) return;

            if (matrix[row, col] == 1)
            {
                Console.WriteLine("{0}, {1}", row + 1, colSize - col + 1); //Adding 1 to prime the index
                if (row >= rowSize)
                    return;
            }
            if (row >= rowSize && col < colSize)
                // Only when it scanned all of the rows and still columns left to scan - jump to next column from the beginning. 
                // Beginning means row = 0 and next column
                RecursionColumnWise(matrix, rowSize, colSize, 0, col + 1);
            else
                // else scan across all the element in the row
                RecursionColumnWise(matrix, rowSize, colSize, row + 1, col);
        }

Here is my implementation in Java:

public static void main(String[] args) {
    try (Scanner scanner = new Scanner(System.in)) {
      int n = scanner.nextInt();
      int m = scanner.nextInt();
      int[][] matrix = new int[m][n];
      for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
          matrix[i][j] = scanner.nextInt();
        }
      }
      StringBuilder output = new StringBuilder();
      for (int[] rowDetails : getRowsWithMaxOnes(matrix)) {
        output.append('[').append(rowDetails[0]).append(", ").append(rowDetails[1]).append(']')
            .append(System.lineSeparator());
      }
      System.out.print(output);
    }
}

private static List<int[]> getRowsWithMaxOnes(int[][] matrix) {
    List<int[]> results = new ArrayList<>();
    int maxAmount = 0;
    for (int i = 0; i < matrix.length; i++) {
      int maxOfCurrentLine = 0;
      if (maxAmount == 0) {
        for (int j = matrix[i].length - 1; j >= 0; j--) {
          if (matrix[i][j] == 1) {
            maxAmount = matrix[i].length - j;
          } else {
            results.add(new int[]{i + 1, maxAmount});
            break;
          }
        }
      } else {
        for (int j = matrix[i].length - maxAmount; j >= 0; j--) {
          if (matrix[i][j] == 0) {
            maxOfCurrentLine = matrix[i].length - j - 1;
            break;
          }
        }
        if (maxOfCurrentLine == maxAmount) {
          results.add(new int[]{i + 1, maxAmount});
        } else if (maxOfCurrentLine > maxAmount) {
          results.clear();
          maxAmount = maxOfCurrentLine;
          results.add(new int[]{i + 1, maxAmount});
        }
      }
    }
    return results;
 }

Samples of both input and output:

The first:
12 6
0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1 1

[2, 8]
[6, 8]
The second:
3 3
0 0 0
0 0 0
0 0 0

[1, 0]
[2, 0]
[3, 0]
The third:
3 3
0 0 0
0 0 1
0 1 1

[3, 2]

Implementation based on first response:

// Returns: Row index and Count
public static IEnumerable<Tuple<int, int>> GetMaximumRows(int[,] a)
{
	
	var result = new List<Tuple<int,int>>();
	int m = a.GetLength(1);
	int j = m - 1;
	
	for (int i=0; i < a.GetLength(0); i++)
	{
		
		if (a[i,j] == 0)
			continue;
		
		if (j > 0 && a[i,j-1] == 1)
		{
			result.Clear();
			while (j > 0 && a[i,j-1] == 1)
				j--;
		}
		
		result.Add(Tuple.Create(i, m-j));
	}
	
	return result;
}

def row_max_1s(mat):
    m = len(mat)
    n = len(mat[0])
    j = len(mat[0]) - 1
    cur_row = 0
    while cur_row < len(mat):
        while j >= 0 and mat[cur_row][j] == 1:
            j -= 1
        if j < 0:
            return cur_row
        cur_row += 1
    return cur_row

public static int getMaxOnes(int[][] arr) {
        if(arr==null)throw new NullPointerException("Null array");
        int max = 0;
        int row = 0;
        for (int col = arr[0].length-1;col >= 0 && row<arr.length;col-- ){
            if(arr[row][col]==1)
                max++;
            else {
                row++;
                while(row < arr.length && arr[row][col]==0)
                    row++;
                if(row < arr.length)
                max++;
            }
        }
        return max;
    }

import java.io.*;

class Array {
	public static void main (String[] args) {
		int arr[][] = {{0,0,0,1,1,1},
		               {0,0,1,1,1,1},
		               {0,0,0,0,0,0},
		               {0,0,1,1,1,1}};
		findMaxRow(arr);
	}
	
	static void findMaxRow(int arr[][]) {
	    int index = arr[0].length - 1;
	    for(int i=0; i<arr.length; i++){
	        while(arr[i][index] == 1) {
	            index--;
	        }
	    }
	    for(int i=0; i<arr.length; i++){
	        if(arr[i][index+1] == 1)
	            System.out.println(i);
	    }
	}
}

import java.util.Scanner;

public class MainClassTestesEstudos {
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		int[][] matrix = new int[m][n];
		int max = 0;
		String result = "";
		for (int i = 0; i < m; i++) 
		{
			int ones = 0;
			for (int j = 0; j < n; j++) 
			{
				matrix[i][j] = scanner.nextInt();
				if (matrix[i][j] == 1) ones++;
		    }
			if (ones > max)
			{
				max = ones; 
				result = "["+(i+1)+", "+max+"]\n";
			} else if (ones == max) result += "["+(i+1)+", "+max+"]\n";
		}
		scanner.close();
		System.out.println(result);
	}
}

As the array is sorted :
1. Iterate through all the rows.
2. For each row, start from the last column, until you hit a 0 element.
3. Keep track of the 1 count for each row in a HashMap, and also keep track of the max 1 count seen so far.
4. Iterate through the HashMap and print all the rows (keys) with the value as the max count of 1.

public static List<List<Integer>> getAnswer(int[][] arr){
		int maxCount = 0;
		int colLength = arr[0].length -1;
		HashMap<Integer, Integer> map = new HashMap<>();
		for(int i = 0; i < arr.length; i++){
			int j = arr[i].length-1;
			while(arr[i][j] != 0){
				j--;
			}
			int currL = colLength - j;
			map.put(i, currL);
			if(maxCount < currL ){
				maxCount = currL;
			}
		}
		List<List<Integer>> res = new ArrayList<>();
		for(Map.Entry<Integer, Integer> e: map.entrySet()){
			if(e.getValue() == maxCount){
				List<Integer> t = new ArrayList<>();
				t.add(e.getKey()+1);
				t.add(maxCount);
				res.add(t); 
			}
		}
		return res;
	}
	
	public static void main(String[] args){
		int[][] arr = {{0,0,0,0,0,0,0,1,1,1,1,1},
				       {0,0,0,0,1,1,1,1,1,1,1,1},
				       {0,0,0,0,0,0,1,1,1,1,1,1},
				       {0,0,0,0,0,0,0,0,0,1,1,1},
				       {0,0,0,0,0,0,0,1,1,1,1,1},
				       {0,0,0,0,1,1,1,1,1,1,1,1}};
		System.out.println(getAnswer(arr));
	}

zeroFound = false
for col = 0 to len(row 1) {
for each row in source array
if row[col] == 1, this row must have the maximum of 1s
zeroFound = true
if zeroFound, break
}

public class MostOnes {
    public static String run(int[][] src) {
        StringBuilder s = new StringBuilder();
        int len = src[0].length;
        boolean zeroFound = false;
        for(int col = 0 ; col < len && !zeroFound; col ++) {
            for(int row = 0; row < src.length; row++) {
                if(src[row][col] == 1) {
                    zeroFound = true;
                    s.append("[").append(row + 1).append(",").append(len - col).append("]");
                }
            }
        }
        return s.toString();
    }
}

test case

@Test
    public void test() {
        int[][] arr = {{0,0,0,0,0,0,0,1,1,1,1,1},
                {0,0,0,0,1,1,1,1,1,1,1,1},
                {0,0,0,0,0,0,1,1,1,1,1,1},
                {0,0,0,0,0,0,0,0,0,1,1,1},
                {0,0,0,0,0,0,0,1,1,1,1,1},
                {0,0,0,0,1,1,1,1,1,1,1,1}};
        String result = MostOnes.run(arr);
        Assert.assertEquals("[2,8][6,8]", result);
    }

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

	public static int maxOnesInRow(int matr[][]) {
		int maxOnes = 1;
		int i = matr.length - 1;
		int j = 0;
		while (i >= 0 && j >= 0) {
			while (matr[i][j] == 1)
				j--;
			while (matr[i][j] == 0)
				j++;
			maxOnes = Math.max(matr[0].length - j, maxOnes);
			i--;
		}
		return maxOnes;
	}

public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int row = in.nextInt();
int col = in.nextInt();
int[][] arr = new int[row][col];
for(int i = 0; i < row; i++) {
for(int j = 0 ; j < col; j++) {
arr[i][j] = in.nextInt();
}
}

Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int maxCount = 0;
int count = 0;
int l = 0;
for(int k = col-1; k >= 0; k--){
while(l < row) {
if(arr[l][k] == 1) {
count++;
k--;
} else {
if(count >= maxCount) {
maxCount = count;
//System.out.println("arr[" + l + "][" + k + "] " + arr[l][k]);
map.put(l, maxCount);

}
l++;
}
}
}

for(int i : map.keySet()) {
if(map.get(i) == maxCount && arr[i][col-maxCount] == 1) {
System.out.println(i+1 + " " + map.get(i));
}
}
}