Approach:

• The idea is based on converting the given input matrix ARR into row echelon form.
• Since we know that the rank of the matrix can not be greater than min(N, M). So we will check if N > M then we will transpose the input matrix ARR since we are using row echelon form so the matrix has to be transformed in such a way that in each row all the elements to the left of the diagonal element must be zero. And the count of non-zero diagonal elements in each row will be equal to our rank of the matrix.
• Otherwise, we will proceed with the next step without performing the transpose of the given matrix ARR.
• Now we will traverse over each row and perform the following operations:
  • If the diagonal element is non-zero then we will make all the elements in that column as zero except the diagonal element by finding the appropriate multiplier.
  • If it is zero then two cases arise:
  • case1: If there is a row below the current row with a non - zero entry in the same column then we will swap both of these rows.
  • case2: if we are unable to find a row with a non -zero entry in the current column then we will swap this current column with the last column.
  • Now we will decrement the number of rows by one so that the row can be processed again.
• Now we will iterate through all the rows and count the diagonal element which is equal to our rank of the matrix.

Algorithm:

• First, check if the N is greater than M then transpose the given input matrix ARR. Otherwise, proceed to the next step without performing transpose of the given matrix ARR.
• Now create a variable swapCol equal to M - 1 which will be used when we have to swap the columns.
• Now iterate through each row from i = 0 to i = N-1 and perform the following operations:
  • If the diagonal element ARR[i][i] is not zero then we have to make all the elements in the current column i to zero except the diagonal element. For this, we will iterate through each row again from j = 0 to j =N-1 and for the element where j is not equal to i we will perform:
    • We will calculate the appropriate multiplier for that row i.e multiplier = (double)ARR[j][i]/ARR[i][i].
    • Now update the whole row j as ARR[j][k] -= multiplier*ARR[i][k]  where k = 0 to k = M. 
  • Otherwise, perform the following operations:
    • we will create a variable isSwapped equal to false initially which will denote whether we have swapped two rows.
    • Now traverse through all rows below the current row i and if we are able to find a non-zero entry in the ARR in the same column i then we have to swap these two rows and update isSwapped as true and break the loop.
    • Now check if isSwapped is equal to false then swap the current column i with the column represented by swapCol and decrement the value of swapCol by one.
    • Now decrease the value of i by one so that the row can be processed again.  
• Create a variable rank initialized to 0.
• Now traverse through all rows again and increment the rank by one if there exits a non - zero diagonal element in each row.
• Finally, return the rank as the required answer.

O(N*M), where N is the number of rows and M is the number of columns.

Since a temporary matrix will be created while doing transpose which takes O(N*M) space. So the overall space complexity will be O(N*M).  

O((N^2)*M), where N is the number of rows and M is the number of columns.

Since we are traversing over each row which takes O(N) time and while traversing each row two conditions are there which takes O(N*M) time each. So the overall time complexity will be O((N^2)*M).   

/*

    Time Complexity O(N^2*M)

    Space Complexity: O(N*M)



    Where 'N' is the number of rows and 'M' is the number of columns

*/



import java.util.ArrayList;



public class Solution {



	private static ArrayList> transpose(ArrayList> arr, int n, int m) {



		ArrayList > temp = new ArrayList> (m);



		for (int i = 0; i < m; i++) {

			temp.add(new ArrayList(n));

			for (int j = 0; j < n; j++) {

				temp.get(i).add(arr.get(j).get(i));

			}

		}



		return temp;

	}





	// Function for swapping the rows

	private static void swapRow(ArrayList> arr, int n1, int n2, int m) {



		int i, j, temp;



		for (i = 0; i < m; i++) {



			temp = arr.get(n1).get(i);

			arr.get(n1).set(i, arr.get(n2).get(i));

			arr.get(n2).set(i, temp);

		}

	}



	// Function for swapping the columns

	private static  void swapCol(ArrayList> arr, int m1, int m2, int n) {



		int i, j, temp;



		for (i = 0; i < n; i++) {



			temp = arr.get(i).get(m1);

			arr.get(i).set(m1, arr.get(i). get(m2));

			arr.get(i).set(m2, temp);



		}

	}



	public static int findRankOfMatrix(ArrayList> arr) {



		int n = arr.size();

		int m = arr.get(0).size();



		// If number of N is greater then M then do transpose of the matrix

		if (n > m) {



			arr = transpose(arr, n, m);

			int temp = n;

			n = m;

			m = temp;

		}



		// Now create a variable swapCol equal to M - 1 which will be used when we have to swap the columns

		int swapPos = m - 1;

		int i = 0, j = 0, k = 0;



		// Iterate through each row

		for (i = 0; i < n; i++) {



			// If there is a non-zero diagonal element then we have to make all the elements in the current column to zero except the diagonal element

			if (arr.get(i).get(i) != 0) {



				for (j = 0; j < n; j++) {

					if (j != i) {



						if (arr.get(j).get(i) != 0) {

							double multiplier = (double)arr.get(j).get(i) / arr.get(i).get(i);

							for (k = 0; k < m; k++) {



								arr.get(j).set(k, arr.get(j).get(k) - (int)(multiplier * (double)arr.get(i).get(k)));

							}

						}

					}

				}

			}



			// If the diagonal element is zero

			else {



				/* Find if there exists a row with a non - zero enetry in same column

				 If so swap these tow rows and break the loop

				 */

				boolean isSwapped = false;

				for (j = i + 1; j < n; j++) {



					if (arr.get(j).get(i) != 0) {



						swapRow(arr, i, j, m);

						isSwapped = true;

						break;

					}

				}



				// Now check if isSwapped is equal to false then swap the current column i with the column represented by swapCol and decrement the value of swapCol by one

				if (!isSwapped) {



					if (swapPos > i) {



						swapCol(arr, i, swapPos, n);

						swapPos--;

					} else {

						break;

					}

				}



				// Now decrease the value of i by one so that the row can be processed again

				i--;

			}

		}



		// Rank will be equal to non-zero diagonal element in each row

		int rank = 0;

		for (i = 0; i < n; i++) {



			if (arr.get(i).get(i) != 0)

				rank++;

			else

				break;

		}



		return rank;

	}

}

'''

   Time Complexity: O((N^2)*M)

   Space Complexity: O(N*M)



   Where 'N' is the number of rows and 'M' is the number of columns

'''



# Function to find the transpose of the matrix

def transpose(arr, n, m):



    temp = [[0 for i in range(n)] for j in range(m)]

    

    for i in range(n):

        for j in range(m): 

            temp[j][i] = arr[i][j];



    arr = temp

    return arr



# Function for swapping the rows

def swapRow(arr, n1, n2, m):



    for i in range(m):

        temp = arr[n1][i]

        arr[n1][i] = arr[n2][i]

        arr[n2][i] = temp

    

    return arr



# Function for swapping the columns

def swapCol(arr, m1, m2, n):



    for i in range(n):

        temp = arr[i][m1]

        arr[i][m1] = arr[i][m2]

        arr[i][m2] = temp

    return arr



def findRankOfMatrix(arr):



    n = len(arr)

    m = len(arr[0])



    # If number of N is greater then M then do transpose of the matrix

    if (n > m):

        arr = transpose(arr, n, m)

        n, m = m, n

    

    # Now create a variable swapCol equal to M - 1 which will be used when we have to swap the columns

    swapPos = m - 1



    i = 0

    # Iterate through each row

    while(i        # If there is a non-zero diagonal element then we have to make all the elements in the current column to zero except the diagonal element

        if (arr[i][i] != 0):

            for j in range(n):



                    if (j != i and arr[j][i] != 0):

                        multiplier = arr[j][i] / arr[i][i]



                        for k in range(m):

                            arr[j][k] -= multiplier * arr[i][k]



            # Increase i by 1 so we can process next row

            i += 1



        # If the diagonal element is zero

        else:

            # Find if there exists a row with a non - zero enetry in same column

            # If so swap these tow rows and break the loop

            isSwapped = False

            for j in range(i+1,n):

                

                if (arr[j][i]):

                    arr = swapRow(arr, i, j, m)

                    isSwapped = True

                    break



            # Now check if isSwapped is equal to false then swap the current column i with the column represented by swapCol and decrement the value of swapCol by one

            if (isSwapped == False):



                if (swapPos > i):

                    arr = swapCol(arr, i, swapPos, n)

                    swapPos -= 1



                else:

                    break



            

        

    # Rank will be equal to non-zero diagonal element in each row

    rank = 0

    for i in range(n):

        if (arr[i][i]):

            rank += 1

        else:

            break



    return rank

/*

   Time Complexity: O((N^2)*M)

   Space Complexity: O(N*M)



   Where 'N' is the number of rows and 'M' is the number of columns

*/



// Function to find the transpose of the matrix

void transpose(vector> &arr, int n, int m)

{

	vector> temp(m, vector(n));



	for (int i = 0; i < n; i++)

	{

		for (int j = 0; j < m; j++)

		{

			temp[j][i] = arr[i][j];

		}

	}



	arr = temp;

}



// Function for swapping the rows

void swapRow(vector> &arr, int n1, int n2, int m)

{

	int i, j, temp;

	for (i = 0; i < m; i++)

	{

		temp = arr[n1][i];

		arr[n1][i] = arr[n2][i];

		arr[n2][i] = temp;

	}

}



// Function for swapping the columns

void swapCol(vector> &arr, int m1, int m2, int n)

{

	int i, j, temp;

	for (i = 0; i < n; i++)

	{

		temp = arr[i][m1];

		arr[i][m1] = arr[i][m2];

		arr[i][m2] = temp;

	}

}



int findRankOfMatrix(vector> &arr)

{

	int n = arr.size();

	int m = arr[0].size();



	// If number of N is greater then M then do transpose of the matrix

	if (n > m)

	{

		transpose(arr, n, m);

		int temp = n;

		n = m;

		m = temp;

	}



	// Now create a variable swapCol equal to M - 1 which will be used when we have to swap the columns

	int swapPos = m - 1;

	int i, j, k;



	// Iterate through each row

	for (i = 0; i < n; i++)

	{

		// If there is a non-zero diagonal element then we have to make all the elements in the current column to zero except the diagonal element

		if (arr[i][i])

		{

			for (j = 0; j < n; j++)

			{

				if (j != i)

				{

					if (arr[j][i])

					{

						double multiplier = (double)arr[j][i] / arr[i][i];

						for (k = 0; k < m; k++)

						{

							arr[j][k] -= multiplier * arr[i][k];

						}

					}

				}

			}

		}



		// If the diagonal element is zero

		else

		{

			// Find if there exists a row with a non - zero enetry in same column

			// If so swap these tow rows and break the loop

			bool isSwapped = false;

			for (j = i + 1; j < n; j++)

			{

				if (arr[j][i])

				{

					swapRow(arr, i, j, m);

					isSwapped = true;

					break;

				}

			}



			// Now check if isSwapped is equal to false then swap the current column i with the column represented by swapCol and decrement the value of swapCol by one

			if (!isSwapped)

			{

				if (swapPos > i)

				{

					swapCol(arr, i, swapPos, n);

					swapPos--;

				}

				else

				{

					break;

				}

			}



			// Now decrease the value of i by one so that the row can be processed again

			i--;

		}

	}



	// Rank will be equal to non-zero diagonal element in each row

	int rank = 0;

	for (i = 0; i < n; i++)

	{

		if (arr[i][i])

			rank++;

		else

			break;

	}



	return rank;

}