Blogs Hub

Lucky Numbers in a Matrix - Array - Easy - LeetCode - MiniTV

Lucky Numbers in a Matrix - Array - Easy - LeetCode - मिनी टीवी

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;
        }
    }
}