Skills101
← All coding problems

Saddle Points

mediumMatrix+20 XPTime limit 2s

A cell is a saddle point if its value is the smallest in its row and also the largest in its column (ties are allowed: "smallest" means no value in the row is smaller, "largest" means no value in the column is larger). Think of a mountain pass — the lowest point along one direction, the highest along the other.

Print every saddle point.

Input:

  • line 1: r c
  • next r lines: c integers each

Output: each saddle point as row col (1-based) on its own line, in row-major order (top to bottom, then left to right) — or -1 if there are none.

Constraints: 1 ≤ r, c ≤ 500, −10⁹ ≤ value ≤ 10⁹.

Think about it: checking each cell against its whole row and column costs O(r·c·(r + c)). Instead compute every row minimum and every column maximum once; a cell is a saddle point when it equals both.

Sample input 1

3 3
3 8 7
2 1 5
1 0 4

Sample output 1

1 1

Sample input 2

2 2
1 2
3 4

Sample output 2

2 1

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.