<?php

namespace App;

/**
 * Lucky Numbers in a Matrix
 *
 * Given an m x 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]
 * Explanation: 7 is the only lucky number since it is the minimum in its row and the maximum in its column.
 *
 * https://leetcode.com/problems/lucky-numbers-in-a-matrix
 */
class LuckyNumbersInMatrix
{
    /**
     * @param int[][] $matrix
     * @return int[]
     */
    public function luckyNumbers(array $matrix): array
    {
        $luckyNumbers = [];
        $rows = count($matrix);
        $columns = count($matrix[0]);

        foreach ($matrix as $i => $iValue) {
            $min = $iValue[0];
            $minIndex = 0;

            for ($j = 1; $j < $columns; $j++) {
                if ($iValue[$j] < $min) {
                    $min = $iValue[$j];
                    $minIndex = $j;
                }
            }

            $max = $matrix[0][$minIndex];
            $maxIndex = 0;

            for ($k = 1; $k < $rows; $k++) {
                if ($matrix[$k][$minIndex] > $max) {
                    $max = $matrix[$k][$minIndex];
                    $maxIndex = $k;
                }
            }

            if ($maxIndex === $i) {
                $luckyNumbers[] = $max;
            }
        }

        return $luckyNumbers;
    }
}
