Lucky Numbers in a Matrix

easy Matrix (2D arrays)

Problem

A lucky number is a value that is the smallest in its row and also the biggest in its column. Print the different lucky numbers in ascending order (each value once), separated by spaces. Print none if there is no lucky number.

Constraints

  • 1 <= r, c <= 500

Examples

Input

3 3
3 7 8
9 11 13
15 16 17

Output

15

Solutions

Best approachTime O(r * c)Space O(r + c)

Compute the row minimums and the column maximums once, then compare each cell with both. Checking the row and the column again for every cell would be O(r * c * (r + c)).

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process a matrix.
 * Input   : r and c, then r rows of c integers.
 * Output  : The lucky numbers.
 * Approach: Row minimums and column maximums.
 * Time    : O(r * c)
 * Space   : O(r + c)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String solve(int[][] m) {
        int rows = m.length;
        int cols = m[0].length;

        // Step 1: Find the smallest value of every row and the biggest value of every column.
        int[] rowMin = new int[rows];
        int[] colMax = new int[cols];
        java.util.Arrays.fill(rowMin, Integer.MAX_VALUE);
        java.util.Arrays.fill(colMax, Integer.MIN_VALUE);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                rowMin[i] = Math.min(rowMin[i], m[i][j]);
                colMax[j] = Math.max(colMax[j], m[i][j]);
            }
        }

        // Step 2: A lucky number equals both its row minimum and its column maximum. TreeSet sorts and removes repeated values.
        java.util.TreeSet<Integer> lucky = new java.util.TreeSet<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (m[i][j] == rowMin[i] && m[i][j] == colMax[j]) {
                    lucky.add(m[i][j]);
                }
            }
        }

        // Step 3: Make the output text.
        if (lucky.isEmpty()) {
            return "none";
        }
        StringBuilder text = new StringBuilder();
        for (int value : lucky) {
            text.append(text.length() == 0 ? "" : " ").append(value);
        }
        return text.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int rows = scanner.nextInt();
        int cols = scanner.nextInt();
        int[][] m = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                m[i][j] = scanner.nextInt();
            }
        }
        System.out.println(solve(m));
    }
}
Hints (1)
  1. Which two values must a lucky number equal?