| 1 | 1 | def saddle_points(matrix): |
| 2 | | pass |
| 2 | # Edge Case: Empty matrix |
| 3 | if not matrix: |
| 4 | return [] |
| 5 | |
| 6 | # Edge Case: Matrix with empty rows |
| 7 | if any(len(row) == 0 for row in matrix): |
| 8 | # Check if all rows are empty |
| 9 | if all(len(row) == 0 for row in matrix): |
| 10 | return [] |
| 11 | else: |
| 12 | # Mixed empty and non-empty rows mean irregular matrix |
| 13 | raise ValueError("irregular matrix") |
| 14 | |
| 15 | # Edge Case: Irregular matrix (rows of different lengths) |
| 16 | row_length = len(matrix[0]) |
| 17 | if any(len(row) != row_length for row in matrix): |
| 18 | raise ValueError("irregular matrix") |
| 19 | |
| 20 | rows = len(matrix) |
| 21 | cols = row_length |
| 22 | |
| 23 | # Precompute row maxima |
| 24 | row_max = [max(row) for row in matrix] |
| 25 | |
| 26 | # Precompute column minima |
| 27 | col_min = [] |
| 28 | for j in range(cols): |
| 29 | column = [matrix[i][j] for i in range(rows)] |
| 30 | col_min.append(min(column)) |
| 31 | |
| 32 | points = [] |
| 33 | for i in range(rows): |
| 34 | for j in range(cols): |
| 35 | value = matrix[i][j] |
| 36 | # Check if the value is the largest in its row and smallest in its column |
| 37 | if value == row_max[i] and value == col_min[j]: |
| 38 | # The problem uses 1-indexed positions |
| 39 | points.append({"row": i + 1, "column": j + 1}) |
| 40 | |
| 41 | return points |
| 42 | # Handled Edge Cases: empty matrix, matrix with empty rows, irregular matrix, normal matrix with no saddle points, normal matrix with one saddle point, normal matrix with multiple saddle points |