Given a m * n matrix of distinct numbers, return all lucky numbers in the matrix in any order.
A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.
Example 1:
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column
Example 2:
Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.
Example 3:
Input: matrix = [[7,8],[1,2]]
Output: [7]
Constraints:
m == mat.length
n == mat[i].length
1 <= n, m <= 50
1 <= matrix[i][j] <= 10^5.
All elements in the matrix are distinct.
Solution:
using System;
using System.Collections.Generic;
using System.Text;
namespace LeetCode.AskGif.Easy.Array
{
public class LuckyNumbersSoln
{
public IList<int> LuckyNumbers(int[][] matrix)
{
var lOBList = new List<int>();
for (int i = 0; i < matrix.Length; i++)
{
int minNumber = matrix[i][0];
int minIndex = 0;
for (int j = 0; j < matrix[0].Length; j++)
{
if (matrix[i][j] < minNumber)
{
minNumber = matrix[i][j];
minIndex = j;
}
}
bool found = true;
for (int k = 0; k < matrix.Length; k++)
{
if (matrix[k][minIndex] > minNumber)
{
found = false;
break;
}
}
if (found)
{
lOBList.Add(minNumber);
return lOBList;
}
}
return new List<int>();
}
}
}
Time Complexity: O(m*n) Where m and n are rows and column of the Matrix.
Space Complexity: O(n) To store the result.
Unit Tests:
using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;
namespace CodingUnitTest.Easy.Array
{
[TestClass]
public class LuckyNumbersSolnTests
{
[TestMethod]
public void LuckyNumbersSoln_First()
{
var matrix = new int[,] {
{ 3, 7, 8 },
{ 9, 11, 13 },
{ 15, 16, 17 }
};
var output = new List<int> { 15 };
var res = new LuckyNumbersSoln().LuckyNumbers(ArrayMapper(matrix));
AreEqual(res, output);
}
[TestMethod]
public void LuckyNumbersSoln_Second()
{
var matrix = new int[,]{
{1, 10, 4, 2 },
{9, 3, 8, 7 },
{15, 16, 17, 12 }
};
var output = new List<int> { 12 };
var res = new LuckyNumbersSoln().LuckyNumbers(ArrayMapper(matrix));
AreEqual(res, output);
}
[TestMethod]
public void LuckyNumbersSoln_Third()
{
var matrix = new int[,]{
{7, 8 },
{1, 2 }
};
var output = new List<int> { 7 };
var res = new LuckyNumbersSoln().LuckyNumbers(ArrayMapper(matrix));
AreEqual(res, output);
}
[TestMethod]
public void LuckyNumbersSoln_Fourth()
{
var matrix = new int[,]{
{ 36376, 85652, 21002, 4510 },
{ 68246, 64237, 42962, 9974 },
{ 32768, 97721, 47338, 5841 },
{ 55103, 18179, 79062, 46542 }
};
var output = new List<int> { };
var res = new LuckyNumbersSoln().LuckyNumbers(ArrayMapper(matrix));
AreEqual(res, output);
}
private void AreEqual(IList<int> res, List<int> output)
{
Assert.AreEqual(res.Count, output.Count);
for (int i = 0; i < res.Count; i++)
{
Assert.AreEqual(res[i], output[i]);
}
}
private int[][] ArrayMapper(int[,] matrix)
{
var arr = new int[matrix.GetLength(0)][];
for (int i = 0; i < matrix.GetLength(0); i++)
{
arr[i] = new int[matrix.GetLength(1)];
for (int j = 0; j < matrix.GetLength(1); j++)
{
arr[i][j] = matrix[i,j];
}
}
return arr;
}
}
}
