Find the number of negative integers from row wise or column wise from a sorted matrix

Find the number of negative integers from row wise or column wise from a sorted matrix
This is a frequently asked question for a experienced interview.
Here i am trying to solve this in two different ways, normal way and an optimised method.

Main Class

/**
 * 
 */
package com.rakesh.matrix.bo;

/**
 * @author Rakesh KR
 * @since  August 19th 13:15 2k17
 */
public class RunMatrix {

 public static void main(String[] args) {
  
  MatrixUtils matrixUtils = new MatrixUtils();
  
  try{
   
   System.out.println("------ Matrix ------");
   
   matrixUtils.makeMartix();
  // matrixUtils.printMatrix();
   
   matrixUtils.sortRowMatrix();
   matrixUtils.transpose();
   matrixUtils.sortRowMatrix();
   matrixUtils.transpose(); 
  // matrixUtils.printMatrix();
   
   long t1 = System.currentTimeMillis();
   System.out.println("NegativeNumbers Count Normal    Way : "+matrixUtils.countNegativeNumbersNormal());
   long t2 = System.currentTimeMillis();
   System.out.println("Time for Normal Way :"+(t2-t1)+" ms");
   t1 = System.currentTimeMillis();
   System.out.println("NegativeNumbers Count Optimized Way : "+matrixUtils.countNegativeNumbersOptimized());
   t2 = System.currentTimeMillis();
   System.out.println("Time for Optimized Way :"+(t2-t1)+" ms");
   
  } catch(Exception e){
   e.printStackTrace();
  } finally{
   matrixUtils = null;
  }

 }

}

Sub Class

/**
 * 
 */
package com.rakesh.matrix.bo;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

/**
 * @author Rakesh KR
 * @since  August 19th 13:17 2k17
 */
public class MatrixUtils {
 
 public int m;
 public int n;
 public int[][] matrix;
 
 public void makeMartix(){
  
  Scanner sc = new Scanner(System.in);
  
  try{
   System.out.println("Size Of Matrix (mxn) : ");
   n = sc.nextInt();
   m = sc.nextInt();
   matrix = new int[n][m];
  // System.out.println("Enter the details to matrix : ");
   int    max    = 99;
   int    min    = -99;
   Random random = new Random();
   for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
  //   matrix[i][j] = sc.nextInt();
     matrix[i][j] = random.nextInt(max + 1 -min) + min; 
    }
   }
  } catch(Exception e){
   e.printStackTrace();
  } finally{
   sc.close();
  }
  
 }
 
 public void printMatrix(){
  
  try{
   System.out.print("The matrix is : \n");
   for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
     System.out.print(" "+matrix[i][j]+" ");
    }
    System.out.print("\n");
   }
   System.out.print("\n");
  } catch(Exception e){
   e.printStackTrace();
  } finally{
   
  }
  
 }
 
 public void sortRowMatrix(){
  
  try{
   for(int i=0; i<matrix.length; i++){
    Arrays.sort(matrix[i]);
   }
  } catch(Exception e){
   e.printStackTrace();
  } finally{
   
  }
  
 }
 
 public void transpose(){
     for (int i = 0; i < matrix.length; i++) {
         for (int j = i; j < matrix[0].length; j++) {
             int tmp1 = matrix[i][j];
             int tmp2 = matrix[j][i];
             matrix[j][i] = tmp1;
             matrix[i][j] = tmp2;
         }
     }
 }
 
 public int countNegativeNumbersNormal(){
  
  int count = 0;
  
  try{
   for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
     if(matrix[i][j]<0){
      count ++;
     }
    }
   }
  } catch(Exception e){
   e.printStackTrace();
  } finally{
   
  }
  
  return count;
 }
 
 public int countNegativeNumbersOptimized(){
  
  int count = 0;
  
  try{
   int i = 0;
   int j = m-1;
   while(j>=0 && i<n){
    if(matrix[i][j]<0){
     count+=(j+1);
     i+=1;
    } else{
     j-=1;
    }
   }
  } catch(Exception e){
   e.printStackTrace();
  } finally{
   
  }
  
  return count;
 }
 
}

Methods:

makeMartix()

This method is used to make a random matrix which consists of positive and negative vales. 

Having min value as -99 and max value as 99.

printMatrix()
This method is used to print an mxn matrix in a user readable manner.
sortRowMatrix()
This method is used to sort an mxn matrix.
transpose()
This method is used to find the transpose of an mxn matrix.
countNegativeNumbersNormal()
An normal way to count the negative numbers from an mxn matrix. 
Its having an 0(n^2) complexity. 
countNegativeNumbersOptimized()
An optimized way to count the negative numbers from an mxn sorted matrix. 

Some tested Results : 
With an 2x2 matrix  :-

------ Matrix ------
Size Of Matrix (mxn) : 
2 2
The matrix is : 
 -53  40 
 -57  10 

The matrix is : 
 -57  10 
 -53  40 

NegativeNumbers Count Normal    Way : 2
Time for Normal Way :0 ms
NegativeNumbers Count Optimized Way : 2
Time for Optimized Way :0 ms

With an 100x100 matrix  :-

------ Matrix ------
Size Of Matrix (mxn) : 
100 100
NegativeNumbers Count Normal    Way : 4906
Time for Normal Way :1 ms
NegativeNumbers Count Optimized Way : 4906
Time for Optimized Way :0 ms

With an 5000x5000 matrix  :-

------ Matrix ------
Size Of Matrix (mxn) : 
5000 5000
NegativeNumbers Count Normal    Way : 12438372
Time for Normal Way :27 ms
NegativeNumbers Count Optimized Way : 12438372
Time for Optimized Way :1 ms

With an 10000x10000 matrix  :-

------ Matrix ------
Size Of Matrix (mxn) : 
10000 10000
NegativeNumbers Count Normal    Way : 49745496
Time for Normal Way :88 ms
NegativeNumbers Count Optimized Way : 49745496
Time for Optimized Way :2 ms