Posted on by Kalkicode
Code Matrix

Find the row with maximum number of 1s

The problem involves finding the row in a matrix that contains the maximum number of 1s. Given a matrix consisting of 0s and 1s, the task is to determine which row has the highest count of 1s.

Example

Consider the following matrix:

 0  0  0  1
0  1  1  1
1  1  1  1
0  0  0  0
1  0  1  0

In this example, the row with index 2 (0-based index) contains the maximum number of 1s, which is 4.

Idea to Solve the Problem

The idea to solve this problem is to iterate through each row of the matrix and count the number of 1s in each row. Maintain a variable to keep track of the maximum count of 1s encountered so far, and another variable to store the index of the row with the maximum count.

Algorithm

  1. Define a function max_one_row that takes a 2D matrix as a parameter.
  2. Initialize variables length and result to store the maximum count and the index of the row with the maximum count.
  3. Loop through each row of the matrix:
    • Initialize row_sum to 0.
    • Loop through each column of the current row:
      • Add the value of the current element to row_sum.
    • If row_sum is greater than length, update length to row_sum and result to the current row index.
  4. If length is 0, output "1s not found," indicating that there are no 1s in the matrix.
  5. Otherwise, output "Maximum number of 1's element exist in row {result}."

Pseudocode

max_one_row(matrix):
    length = 0
    result = 0

    for i from 0 to ROW:
        row_sum = 0
        for j from 0 to COL:
            add matrix[i][j] to row_sum
        if row_sum > length:
            set length to row_sum
            set result to i

    if length is 0:
        output "1s not found"
    else:
        output "Maximum number of 1's element exist in row {result}"

main:
    matrix = ...  // Define the matrix
    max_one_row(matrix)

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

Output Explanation

The mentioned C code implements the above algorithm to find the row with the maximum number of 1s in a given matrix. It iterates through each row, counts the number of 1s, and keeps track of the row with the maximum count. If no 1s are found in any row, it outputs "1s not found." Otherwise, it outputs the index of the row with the maximum count.

Time Complexity

The time complexity of the algorithm is O(ROW * COL), where ROW is the number of rows and COL is the number of columns in the matrix. This is because the algorithm iterates through each element of the matrix once to calculate the row with the maximum number of 1s.

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