Discovering Lucky Numbers in a Matrix: A Java Solution

Discovering Lucky Numbers in a Matrix: A Java Solution

Welcome to my blog! Today, we will explore an intriguing problem involving matrices: finding lucky numbers. This article will guide you through the problem, provide a detailed solution in Java, and ensure your code is both efficient and easy to understand.

Understanding the Problem

A lucky number in a matrix is defined as an element that is the minimum in its row and the maximum in its column. Given an m x n matrix of distinct numbers, our goal is to find all lucky numbers and return them in any order.

Problem Constraints:

  • The matrix dimensions are m x n.
  • Each element in the matrix is distinct.
  • 1 ≤ n, m ≤ 50
  • 1 ≤ matrix[i][j] ≤ 105

Example Scenarios

Example 1:

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

Explanation: 15 is the only lucky number as 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 as it is the minimum in its row and the maximum in its column.

Example 3:

Input: matrix = [[7, 8], [1, 2]]
Output: [7]

Explanation: 7 is the only lucky number as it is the minimum in its row and the maximum in its column.

Java Solution

Let's dive into the Java solution for finding lucky numbers in a matrix.

import java.util.ArrayList;
import java.util.List;

public class LuckyNumbersInMatrix {
    public static List luckyNumbers(int[][] matrix) {
        List result = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        
        // Find the minimum elements in each row
        int[] minRow = new int[m];
        for (int i = 0; i < m; i++) {
            int min = matrix[i][0];
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] < min) {
                    min = matrix[i][j];
                }
            }
            minRow[i] = min;
        }

        // Find the maximum elements in each column
        int[] maxCol = new int[n];
        for (int j = 0; j < n; j++) {
            int max = matrix[0][j];
            for (int i = 1; i < m; i++) {
                if (matrix[i][j] > max) {
                    max = matrix[i][j];
                }
            }
            maxCol[j] = max;
        }

        // Check for lucky numbers
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == minRow[i] && matrix[i][j] == maxCol[j]) {
                    result.add(matrix[i][j]);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] matrix1 = {
            {3, 7, 8},
            {9, 11, 13},
            {15, 16, 17}
        };
        int[][] matrix2 = {
            {1, 10, 4, 2},
            {9, 3, 8, 7},
            {15, 16, 17, 12}
        };
        int[][] matrix3 = {
            {7, 8},
            {1, 2}
        };

        System.out.println("Lucky numbers in matrix1: " + luckyNumbers(matrix1)); // Output: [15]
        System.out.println("Lucky numbers in matrix2: " + luckyNumbers(matrix2)); // Output: [12]
        System.out.println("Lucky numbers in matrix3: " + luckyNumbers(matrix3)); // Output: [7]
    }
}

Solution Breakdown

  1. Finding Minimum Elements in Rows: Iterate through each row to find the minimum element and store it in the minRow array.
  2. Finding Maximum Elements in Columns: Iterate through each column to find the maximum element and store it in the maxCol array.
  3. Checking for Lucky Numbers: Check each element in the matrix to see if it is both the minimum in its row and the maximum in its column. If so, it is added to the result list.

Happy coding, and stay tuned for more programming challenges and solutions!

Post a Comment for "Discovering Lucky Numbers in a Matrix: A Java Solution"