CC-10 : Find lucky number in matrix.

Description:

A lucky number in a matrix is defined as the element that is minimum in its row in the matrix and maximum in its column in the matrix. Given input matrix mat, check and return the lucky number from the matrix.

Test cases and expected outputs:

Input	Expected outputs
mat = { {5,3,4,6}, {4,1,3,1}, {2,1,2,3}, {6,2,7,9}};	Lucky Number: 3
mat = { {5,9,8,9,4}, {9,3,2,7,1}, {1,2,3,9,3}, {2,3,6,9,2}, {7,2,3,9,1}};	Lucky Number: 4
mat = { {4,8,7,9,7}, {2,3,6,7,8},};	Lucky Number: 4

Pseudocode:

The java method should accept following input parameters: mat (integer matrix).

Initialize an Arraylist named luckyNumbers to hold all lucky numbers found in mat. An ArrayList is a resizable array that can be used to hold elements, when we are not sure of the number of elements that need to be stored. For example, we do not know how many lucky numbers may exist in mat.

Initialize a variable minInRow to hold the minimum number of each row.

Initialize a variable maxInCol to hold the maximum number in each column.

Initialize a variable minColIdx to hold the column index of minInRow.

Iterate through mat using a for loop, using variable rIdx as loop counter. Loop variable rIdx will be initialized with value 0 and will iterate through all the matrix’s columns one by one till rIdx < mat.length:

Iterate through mat using a for loop, using variable cIdx as loop counter. Loop variable cIdx will be initialized with value 0 and will iterate through all the matrix’s columns one by one till cIdx < mat[0].length:

If (mat[rIdx][cIdx] < minInRow), then set minInRow to mat[rIdx][cIdx] and set mInColIdx to cIdx.

After above inner for loop completes we will have the minimum number of the current row stored in minInRow and the column of this element stored in minColIdx.

o Iterate through mat using a for loop, using variable r2Idx as loop counter. Loop variable r2Idx will be initialized with value 0 and will iterate through all the matrix’s columns one by one till rIdx < mat.length:

If (mat[r2Idx][minColIdx] > maxInCol), then set maxInCol to mat[r2Idx][minColIdx].

After above loop completes if (minInRow==maxInCol), we have found a lucky number, add it to luckyNumbers ArrayList.

After above loops complete, return luckyNumbers ArrayList.

Code:

public ArrayList matArrayFindLuckyNumber(int[][] mat) throws Exception{
	ArrayList<Integer> luckyNumbers=new ArrayList<Integer>();
	int minInRow=Integer.MAX_VALUE;
	int maxInCol=Integer.MIN_VALUE;
	int minColIdx=Integer.MAX_VALUE;
	for (int rIdx=0; rIdx < mat.length; rIdx++) {
		for (int cIdx=0; cIdx < mat[0].length; cIdx++) {
			if (mat[rIdx][cIdx] < minInRow) {
				minInRow=mat[rIdx][cIdx];
				minColIdx=cIdx;
			}
		}
		for (int r2Idx=0; r2Idx < mat.length; r2Idx++) {
			if (mat[r2Idx][minColIdx] > maxInCol) {
				maxInCol=mat[r2Idx][minColIdx];
			}
		}
		if (minInRow==maxInCol) {
			luckyNumbers.add(minInRow);
		}
	}	
	return luckyNumbers;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.ArrayList;

public class MdArrayFindLuckyNumber {
	
public ArrayList matArrayFindLuckyNumber(int[][] mat) throws Exception{
	ArrayList<Integer> luckyNumbers=new ArrayList<Integer>();
	int minInRow=Integer.MAX_VALUE;
	int maxInCol=Integer.MIN_VALUE;
	int minColIdx=Integer.MAX_VALUE;
	for (int rIdx=0; rIdx < mat.length; rIdx++) {
		for (int cIdx=0; cIdx < mat[0].length; cIdx++) {
			if (mat[rIdx][cIdx] < minInRow) {
				minInRow=mat[rIdx][cIdx];
				minColIdx=cIdx;
			}
		}
		for (int r2Idx=0; r2Idx < mat.length; r2Idx++) {
			if (mat[r2Idx][minColIdx] > maxInCol) {
				maxInCol=mat[r2Idx][minColIdx];
			}
		}
		if (minInRow==maxInCol) {
			luckyNumbers.add(minInRow);
		}
	}	
	return luckyNumbers;
}
	
public static void main(String[] args) {
	MdArrayFindLuckyNumber ap=new MdArrayFindLuckyNumber();
	ArrayList retArrList;
	try {
	int[][] arr = {	{5,3,4,6},
					{4,1,3,1},	
					{2,1,2,3},
					{6,2,7,9}
	};
	print2dArray(arr, "The 2d Array");
	retArrList=ap.matArrayFindLuckyNumber(arr);
	printArrayListSummary(retArrList, "Lucky Numbers");
			
	int[][] arr1 = {	{5,9,8,9,4},
						{9,3,2,7,1},	
						{1,2,3,9,3},
						{2,3,6,9,2},
						{7,2,4,9,1}
								
	};
	print2dArray(arr1, "The 2d Array");
	retArrList=ap.matArrayFindLuckyNumber(arr1);
	printArrayListSummary(retArrList, "Lucky Numbers");
			
			
	int[][] arr2 = {	{4,8,7,9,7},
						{2,3,6,7,8},	
	};
	print2dArray(arr2, "The 2d Array");
	retArrList=ap.matArrayFindLuckyNumber(arr2);
	printArrayListSummary(retArrList, "Lucky Numbers");

			
	}catch (Exception exception) {
	System.out.print("Exception,"+ exception);
	exception.printStackTrace();
				
	}
}
			
public static void print2dArray(int[][] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input 2d Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("*********************************************************************");
	System.out.print(label+" : \n");
	int rIdx=0; int cIdx=0;
	for (rIdx=0; rIdx < intArray.length; rIdx++) {
		for (cIdx=0; cIdx < intArray[rIdx].length; cIdx++) {
			System.out.print(intArray[rIdx][cIdx]);
			if (cIdx < intArray[rIdx].length) System.out.print(",");
		}
		System.out.print("\n");
	} 
	System.out.println();
	System.out.println("**********************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;	
}

public static void printArrayListSummary(ArrayList al, String label) throws Exception {
	if (al == null) { System.out.println("\n\n Input ArrayList was null !! \n"); return; }
	System.out.println();
	System.out.println("***********************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < al.size(); arrayIndex++) {
			System.out.print(al.get(arrayIndex));
			if (arrayIndex < al.size()-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println("************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}			
		
		

}