Lucky Numbers in a Matrix Leetcode Solution

The Lucky Numbers in a Matrix Leetcode Solution problem asked us to find a lucky integer from the given matrix. A lucky integer is defined as a number that is the minimum among all other elements in its row and maximum among its column. So there may be more than one lucky integer in the given matrix. So we have the liberty of any one of them. In case there is no lucky number in the matrix, we need to return an empty vector. So before diving deep into the solution, let us have a look at a few examples.

matrix = [[3,7,8],[9,11,13],[15,16,17]]

[15]

Explanation:  15 is the minimum number in its row, and also the maximum element in its column. Thus 15 is being returned as output.

Approach to Lucky Numbers in a Matrix Leetcode Solution

The problem Lucky Numbers in a Matrix Leetcode Solution is one of the standard ones. And is asked very often in many coding rounds. The problem is simple since we simply need to check if there exists any element that is minimum in its row. And at the same time it should be maximum in its column. So, we can easily do this, by using two temporary arrays. These arrays store the minimum element of each row and the maximum element of each column.

After that, we need to check if there exists some element that is common in both these temporary arrays. So, we can use HashSet where we insert the elements of one array. Then we traverse over the elements of the second array and check if it is present in the HashSet. If some element is present in both the arrays we return that as output. But if w do not get any match, we return an empty vector as answer.

Code for Lucky Numbers in a Matrix Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

vector<int> luckyNumbers (vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    vector<int> row(n, INT_MAX), col(m, INT_MIN);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            row[i] = min(row[i], matrix[i][j]);
    }
    unordered_set<int> s;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++)
            col[i] = max(col[i], matrix[j][i]);
    }
    for(int i=0;i<n;i++)
        s.insert(row[i]);
    for(int i=0;i<m;i++)
        if(s.count(col[i]))
            return {col[i]};
    return {};
}

int main(){
    vector<vector<int>> v = {{3,7,8},{9,11,13},{15,16,17}};
    vector<int> output = luckyNumbers(v);
    for(auto x: output)
        cout<<x;
}

15

Java code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<Integer> luckyNumbers (int[][] matrix) {
      int n = matrix.length;
      int m = matrix[0].length;
      int[] row = new int[n];
      for(int i=0;i<n;i++)
          row[i] = Integer.MAX_VALUE;
      int[] col = new int[m];
      for(int i=0;i<m;i++)
          col[i] = Integer.MIN_VALUE;
      for(int i=0;i<n;i++){
          for(int j=0;j<m;j++)
              row[i] = Math.min(row[i], matrix[i][j]);
      }
      HashSet<Integer> s = new HashSet<Integer>();
      for(int i=0;i<m;i++){
          for(int j=0;j<n;j++)
              col[i] = Math.max(col[i], matrix[j][i]);
      }
      for(int i=0;i<n;i++)
          s.add(row[i]);
      for(int i=0;i<m;i++)
          if(s.contains(col[i]))
              return new ArrayList(Arrays.asList((col[i])));
      return new ArrayList();
  }

  public static void main (String[] args) throws java.lang.Exception
  {
    int[][] matrix = {{3,7,8},{9,11,13},{15,16,17}};
    List<Integer> output = luckyNumbers(matrix);
    if(output.size() > 0)
      System.out.print(output.get(0));
    
  }
}

15

Complexity Analysis

Time Complexity

O(N*M), where N and M are the elements in rows and columns of the array.

Space Complexity

O(N+M), because we use two temporary arrays.