Skip to main content

Find the row with maximum number of 1s

In computer science, a row with the maximum number of 1s is a problem that is commonly encountered when working with binary matrices. Given a binary matrix (a matrix where each element is either 0 or 1), the goal is to find the row that has the most 1s.

One of the most straightforward algorithms for solving this problem is to loop through each row in the matrix, and count the number of 1s in that row. Keep track of the row with the maximum number of 1s found so far, and update it if a row is found with more 1s. Once all rows have been examined, the row with the maximum number of 1s can be returned.

This algorithm has a time complexity of O(nm), where n is the number of rows in the matrix, and m is the number of columns. However, there are more efficient algorithms that can solve this problem in O(nlogm) or even O(n+m) time complexity.

Code Solution

//C Program 
//Find the row with maximum number of 1s
#include <stdio.h>

#define ROW 5
#define COL 4

//Method which are find a row which is contains 
//max number of 1's element
void max_one_row(int matrix[][COL])
{
  int length=0,result=0,row_sum=0;

  for (int i = 0; i < ROW; ++i)
  {
    row_sum=0; 

    for (int j = 0; j < COL; ++j)
    {
      //Sum of row element
      row_sum+=matrix[i][j];
    }
    if(row_sum > length)
    {
      length=row_sum;
      result=i;
    }
  }
  if(length==0)
  {
    printf("1s not found\n");
  }
  else
  {
    printf("Maximum number of 1's element exist in row %d\n",result );
  }
}
int main()
{

  //matrix which is contain 0's and 1's
  int matrix[][COL]= { 
    {0, 0, 0, 1},       
    {0, 1, 1, 1},  
    {1, 1, 1, 1},  
    {0, 0, 0, 0},
    {1, 0, 1, 0}
  };  
  
  max_one_row(matrix);

  return 0;
}

Output

Maximum number of 1's element exist in row 2
/*
  C++ Program
  Find the row with maximum number of 1s
*/
#include<iostream>
#define ROW 5
#define COL 4
using namespace std;


class MyMatrix {
	public:
		int rows;
	int cols;
	MyMatrix() {
		//Get matrix size
		this->rows = ROW;
		this->cols = COL;
	}
	//Method which are find a row which is contains 
	//max number of 1's element
	void max_one_row(int matrix[][COL]) {
		int length = 0, result = 0, row_sum = 0;
		for (int i = 0; i < this->rows; ++i) {
			row_sum = 0;
			for (int j = 0; j < this->cols; ++j) {
				//Sum of row element
				row_sum += matrix[i][j];
			}
			if (row_sum > length) {
				//When getting a new max length row
				length = row_sum;
				result = i;
			}
		}
		if (length == 0) {
			cout << "1s not found\n";
		} else {
			cout << "Maximum number of 1's element exist in row " << result << "\n";
		}
	}
};
int main() {
	int matrix[][COL] = {
		{
			0,
			0,
			0,
			1
		},
		{
			0,
			1,
			1,
			1
		},
		{
			1,
			1,
			1,
			1
		},
		{
			0,
			0,
			0,
			0
		},
		{
			1,
			0,
			1,
			0
		}
	};
	MyMatrix obj ;
	obj.max_one_row(matrix);
	return 0;
}

Output

Maximum number of 1's element exist in row 2
/*
  Java Program
  Find the row with maximum number of 1s
*/
public class MyMatrix {

  public int rows;
  public int cols;
  public MyMatrix(int [][]matrix)
  {
    //Get matrix size
    this.rows = matrix.length;
    this.cols = matrix[0].length;

  }
  //Method which are find a row which is contains 
  //max number of 1's element
  public void max_one_row(int [][]matrix)
  {
    int length=0,result=0,row_sum=0;

    for (int i = 0; i < this.rows; ++i)
    {
      row_sum=0; 

      for (int j = 0; j < this.cols; ++j)
      {
        //Sum of row element
        row_sum+=matrix[i][j];
      }
      if(row_sum > length)
      {
        //When getting a new max length row
        length=row_sum;
        result=i;
      }
    }
    if(length==0)
    {
      System.out.print("1s not found\n");
    }
    else
    {
      System.out.print("Maximum number of 1's element exist in row "+result+"\n" );
    }
  }
  public static void main(String[] args) 
  {
    //matrix which is contain 0's and 1's
    int [][]matrix= { 
      {0, 0, 0, 1},       
      {0, 1, 1, 1},  
      {1, 1, 1, 1},  
      {0, 0, 0, 0},
      {1, 0, 1, 0}
    };  

    MyMatrix obj = new MyMatrix(matrix);
    obj.max_one_row(matrix);
  }
}

Output

Maximum number of 1's element exist in row 2
/*
  C# Program
  Find the row with maximum number of 1s
*/
using System;

public class MyMatrix {
	int rows;
	int cols;
	MyMatrix(int[,] matrix) {
		//Get matrix size
		this.rows = matrix.GetLength(0);
		this.cols = matrix.GetLength(1);
	}
	//Method which are find a row which is contains 
	//max number of 1's element
	public void max_one_row(int[,] matrix) {
		int length = 0, result = 0, row_sum = 0;
		for (int i = 0; i < this.rows; ++i) {
			row_sum = 0;
			for (int j = 0; j < this.cols; ++j) {
				//Sum of row element
				row_sum += matrix[i,j];
			}
			if (row_sum >length) {
				//When getting a new max.Length row
				length = row_sum;
				result = i;
			}
		}
		if (length == 0) {
			Console.Write("1s not found\n");
		} else {
			Console.Write("Maximum number of 1's element exist in row " + result + "\n");
		}
	}
	public static void Main(String[] args) {
		int[,]
		//matrix which is contain 0's and 1's
		matrix = {
			{
				0,
				0,
				0,
				1
			},
			{
				0,
				1,
				1,
				1
			},
			{
				1,
				1,
				1,
				1
			},
			{
				0,
				0,
				0,
				0
			},
			{
				1,
				0,
				1,
				0
			}
		};
		MyMatrix obj = new MyMatrix(matrix);
		obj.max_one_row(matrix);
	}
}

Output

Maximum number of 1's element exist in row 2
<?php
/*
  Php Program
  Find the row with maximum number of 1s
*/
class MyMatrix {
	public $rows;
	public $cols;

	function __construct($matrix) {
		//Get matrix size
		$this->rows = count($matrix);
		$this->cols = count($matrix[0]);
	}
	//Method which are find a row which is contains 
	//max number of 1's element

	public 	function max_one_row($matrix) {
		$length = 0;
		$result = 0;
		$row_sum = 0;
		for ($i = 0; $i < $this->rows; ++$i) {
			$row_sum = 0;
			for ($j = 0; $j < $this->cols; ++$j) {
				//Sum of row element
				$row_sum += $matrix[$i][$j];
			}
			if ($row_sum > $length) {
				//When getting a new max length row
				$length = $row_sum;
				$result = $i;
			}
		}
		if ($length == 0) {
			echo("1s not found\n");
		} else {
			echo("Maximum number of 1's element exist in row ". $result ."\n");
		}
	}
}

function main() {
	//matrix which is contain 0's and 1's
	$matrix = array(array(0, 0, 0, 1), array(0, 1, 1, 1), array(1, 1, 1, 1), array(0, 0, 0, 0), array(1, 0, 1, 0));
	$obj = new MyMatrix($matrix);
	$obj->max_one_row($matrix);

}
main();

Output

Maximum number of 1's element exist in row 2
/*
  Node Js Program
  Find the row with maximum number of 1s
*/
class MyMatrix {
	constructor(matrix) {
		//Get matrix size
		this.rows = matrix.length;
		this.cols = matrix[0].length;
	}

	//Method which are find a row which is contains 
	//max number of 1's element
	max_one_row(matrix) {
		var length = 0;
		var result = 0;
		var row_sum = 0;
		for (var i = 0; i < this.rows; ++i) {
			row_sum = 0;
			for (var j = 0; j < this.cols; ++j) {
				//Sum of row element
				row_sum += matrix[i][j];
			}

			if (row_sum > length) {
				//When getting a new max length row
				length = row_sum;
				result = i;
			}
		}

		if (length == 0) {
			process.stdout.write("1s not found\n");
		} else {
			process.stdout.write("Maximum number of 1's element exist in row " + result + "\n");
		}
	}
}

function main(args) {
	//matrix which is contain 0's and 1's
	var matrix = [
		[0, 0, 0, 1],
		[0, 1, 1, 1],
		[1, 1, 1, 1],
		[0, 0, 0, 0],
		[1, 0, 1, 0]
	];
	var obj = new MyMatrix(matrix);
	obj.max_one_row(matrix);
}

main();

Output

Maximum number of 1's element exist in row 2
# Python 3 Program
# Find the row with maximum number of 1s
class MyMatrix :
	
	def __init__(self, matrix) :
		# Get matrix size
		self.rows = len(matrix)
		self.cols = len(matrix[0])
	
	# Method which are find a row which is contains 
	# max number of 1's element
	def max_one_row(self, matrix) :
		length = 0
		result = 0
		row_sum = 0
		i = 0
		while (i < self.rows) :
			row_sum = 0
			j = 0
			while (j < self.cols) :
				# Sum of row element
				row_sum += matrix[i][j]
				j += 1
			
			if (row_sum > length) :
				# When getting a new max length row
				length = row_sum
				result = i
			
			i += 1
		
		if (length == 0) :
			print("1s not found\n", end = "")
		else :
			print("Maximum number of 1's element exist in row ", result ,"\n", end = "")
		
	

def main() :
	matrix = [
		[0, 0, 0, 1],
		[0, 1, 1, 1],
		[1, 1, 1, 1],
		[0, 0, 0, 0],
		[1, 0, 1, 0]
	]
	obj = MyMatrix(matrix)
	obj.max_one_row(matrix)


if __name__ == "__main__":
	main()

Output

Maximum number of 1's element exist in row  2
# Ruby Program
# Find the row with maximum number of 1s
class MyMatrix 
	# Define the accessor and reader of class MyMatrix
	attr_reader :rows, :cols
	attr_accessor :rows, :cols
	def initialize(matrix) 
		# Get matrix size
		self.rows = matrix.length
		self.cols = matrix[0].length
	end
	# Method which are find a row which is contains 
	# max number of 1's element
	def max_one_row(matrix) 
		length = 0
		result = 0
		row_sum = 0
		i = 0
		while (i < self.rows) 
			row_sum = 0
			j = 0
			while (j < self.cols) 
				# Sum of row element
				row_sum += matrix[i][j]
				j += 1
			end
			if (row_sum > length) 
				# When getting a new max length row
				length = row_sum
				result = i
			end
			i += 1
		end
		if (length == 0) 
			print("1s not found\n")
		else 
			print("Maximum number of 1's element exist in row ", result ,"\n")
		end
	end
end
def main() 
	matrix = [
		[0, 0, 0, 1],
		[0, 1, 1, 1],
		[1, 1, 1, 1],
		[0, 0, 0, 0],
		[1, 0, 1, 0]
	]
	obj = MyMatrix.new(matrix)
	obj.max_one_row(matrix)
end


main()

Output

Maximum number of 1's element exist in row 2

/*
  Scala Program
  Find the row with maximum number of 1s
*/
class MyMatrix(var rows: Int,var cols: Int) {
	def this(matrix: Array[Array[Int]]) {
		//Get matrix size
		this( matrix.length,matrix(0).length);
	}
	//Method which are find a row which is contains 
	//max number of 1's element
	def max_one_row(matrix: Array[Array[Int]]): Unit = {
		var length: Int = 0;
		var result: Int = 0;
		var row_sum: Int = 0;
		var i: Int = 0;
		while (i < this.rows) {
			row_sum = 0;
			var j: Int = 0;
			while (j < this.cols) {
				//Sum of row element
				row_sum += matrix(i)(j);
				j += 1;
			}
			if (row_sum > length) {
				//When getting a new max length row
				length = row_sum;
				result = i;
			}
			i += 1;
		}
		if (length == 0) {
			print("1s not found\n");
		} else {
			print("Maximum number of 1's element exist in row " + result + "\n");
		}
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val matrix: Array[Array[Int]] = Array(
			Array(0, 0, 0, 1),
			Array(0, 1, 1, 1),
			Array(1, 1, 1, 1),
			Array(0, 0, 0, 0),
			Array(1, 0, 1, 0));
		val obj: MyMatrix = new MyMatrix(matrix);
		obj.max_one_row(matrix);
	}
}

Output

Maximum number of 1's element exist in row 2
/*
  Java Program
  Find the row with maximum number of 1s
*/
class MyMatrix {
	var rows: Int;
	var cols: Int;
	init(_ matrix: [
		[Int]
	]) {
		//Get matrix size
		self.rows = matrix.count;
		self.cols = matrix[0].count;
	}
	//Method which are find a row which is contains 
	//max number of 1's element
	func max_one_row(_ matrix: [
		[Int]
	]) {
		var length: Int = 0;
		var result: Int = 0;
		var row_sum: Int = 0;
		var i: Int = 0;
		while (i < self.rows) {
			row_sum = 0;
			var j: Int = 0;
			while (j < self.cols) {
				//Sum of row element
				row_sum += matrix[i][j];
				j += 1;
			}
			if (row_sum > length) {
				//When getting a new max length row
				length = row_sum;
				result = i;
			}
			i += 1;
		}
		if (length == 0) {
			print("1s not found\n", terminator: "");
		} else {
			print("Maximum number of 1's element exist in row ", result , "\n", terminator: "");
		}
	}
}
func main() {
	let matrix: [
		[Int]
	] = [
		[0, 0, 0, 1],
		[0, 1, 1, 1],
		[1, 1, 1, 1],
		[0, 0, 0, 0],
		[1, 0, 1, 0]
	];
	let obj: MyMatrix = MyMatrix(matrix);
	obj.max_one_row(matrix);
}
main();

Output

Maximum number of 1's element exist in row  2
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment