Saddle points: row maximum and column minimum.
A saddle point is the largest in its row and the smallest in its column — a strict, beautiful 2D property.
A saddle point is a cell that simultaneously equals the maximum value in its row and the minimum value in its column. Such cells are rare but well-defined, and finding them combines several core 2D patterns.
Saddle-point problems test row-max scanning, column-min scanning, and the ability to combine two conditions over the same cell.
Two checks per cell.
Compute row max and column min, then test equality.
Row max helper
private static int rowMax(int[][] m, int r) {
int max = m[r][0];
for (int c = 1; c < m[r].length; c++) {
if (m[r][c] > max) max = m[r][c];
}
return max;
}Column min helper
private static int colMin(int[][] m, int c) {
int min = m[0][c];
for (int r = 1; r < m.length; r++) {
if (m[r][c] < min) min = m[r][c];
}
return min;
}Saddle-point check
public static boolean isSaddlePoint(int[][] m, int r, int c) {
return m[r][c] == rowMax(m, r) && m[r][c] == colMin(m, c);
}Find all saddle points
public static int countSaddlePoints(int[][] m) {
int count = 0;
for (int r = 0; r < m.length; r++) {
for (int c = 0; c < m[r].length; c++) {
if (isSaddlePoint(m, r, c)) count++;
}
}
return count;
}This version is simple but does extra work — computing row/column extremes repeatedly. For larger grids, precompute arrays of row maxes and column mins.
Saddle-point vocabulary.
Used in matrix-theory style problems.
- Saddle point — cell that is row max and column min simultaneously.
- Row maximum — largest element in a row.
- Column minimum — smallest element in a column.
- Combined condition — both checks must hold.
- Precomputed extremes — caching row maxes and column mins for efficiency.
How saddle-point problems are tested.
Helper composition and correct comparison directions matter.
- Helper methods. Splitting into rowMax/colMin earns design credit.
- Initialization of extremes. Use
m[r][0]for max andm[0][c]for min, then scan from index 1. - Ties. Multiple cells can be row maxes; saddle-point criteria still apply.
Find the saddle point.
A small grid; verify by hand.
Problem. Find the saddle point in:
{{ 3, 1, 2},
{ 5, 4, 6},
{ 7, 8, 9}}Step 1. Row maxes: row 0 → 3, row 1 → 6, row 2 → 9.
Step 2. Column mins: col 0 → 3, col 1 → 1, col 2 → 2.
Step 3. Check each row-max cell:
- (0, 0) = 3 = row max. Column min of col 0 is 3 = m[0][0]. ✓ Saddle point!
- (1, 2) = 6 = row max. Column min of col 2 is 2, not 6. ✗
- (2, 2) = 9 = row max. Column min of col 2 is 2, not 9. ✗
Answer. Saddle point at (0, 0).
Saddle-point pitfalls.
Most are confused row/column reasoning.
- Swapping max and min. Row max + column min is the definition; reversing breaks it.
- Initializing extremes to 0. Negative cells become invisible.
- Not checking both conditions. A row max alone isn't enough.
- Comparing values from different rows. Be precise about which row and column you scan.
Saddle-point checklist.
Both criteria must hold.
Saddle Point Reference
AP Quick Reference| Check | Means | AP Exam Tip |
|---|---|---|
| Row max equals cell | No bigger value in the row | Initialize with m[r][0]. |
| Column min equals cell | No smaller value in the column | Initialize with m[0][c]. |
| Both true | Saddle point | Combine with &&. |
| Helpers | Cleaner code | Earns design credit. |
How to master saddle points.
Build the two helpers; then composition is trivial.
Use the three practice tools below this lesson in order:
- MCQ Practice — for small grids, compute every row max and column min before answering.
- Java Lab — implement rowMax, colMin, and isSaddlePoint separately. Then write the counter.
- FRQ Practice — for "find the cell that is X and Y" problems, write a helper per condition and compose.
Practice — attempt these now.
AP-style assessments aligned to this lesson. Time them.