Programming — Saddle Point in a 2-D Array: 25-Comp-A4 Program Design and Data Structures, December 2017, Q3

Question 3: Programming — Saddle Point in a 2-D Array (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. An $n\times n$ integer array, values in $[1,99]$, guaranteed to contain exactly one saddle point (row-minimum that is also its column's maximum). Worked example: the given $6\times6$ array, saddle element 4 at $A(3,3)$ (1-indexed).

Find. A program that reads the array and prints the saddle value and its (row, column) location.

Approach. For each row, find its minimum and the column it occurs in, then check whether that same value is the maximum of that column; since exactly one saddle point exists, stop as soon as it is found.

Note why a per-row check suffices. The saddle point must be a row minimum, so scanning every row's minimum and testing it against its own column's maximum will find it in at most $n$ row scans (each row scan is $O(n)$ for the minimum plus $O(n)$ to re-scan its column), i.e. $O(n^2)$ overall — no need to compare every pair of rows and columns.

Write the program.

#include <stdio.h>

#define MAXN 50

int main(void)
{
    int a[MAXN][MAXN];
    int n, i, j, min_val, min_col, col_max;
    int found = 0;

    printf("Enter n: ");
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &a[i][j]);

    for (i = 0; i < n && !found; i++) {
        min_val = a[i][0];
        min_col = 0;
        for (j = 1; j < n; j++)
            if (a[i][j] < min_val) { min_val = a[i][j]; min_col = j; }

        col_max = a[0][min_col];
        for (j = 1; j < n; j++)
            if (a[j][min_col] > col_max) col_max = a[j][min_col];

        if (min_val == col_max) {
            printf("Saddle element: %d at row %d, column %d\n",
                   min_val, i + 1, min_col + 1);
            found = 1;
        }
    }
    return 0;
}

Confirm against the worked example. Row 3 (1-indexed) is $8\ 9\ 4\ 5\ 6\ 8$, whose minimum is 4 at column 3; column 3 is $1,2,4,3,1,2$, whose maximum is 4 — the two agree, so the saddle point is confirmed at $(3,3)$ with no earlier row (1 or 2) satisfying the test. $$\boxed{\text{saddle}=4 \text{ at } (row=3,\ col=3)}$$

Question 3 — results
Quantity	Value
Row-3 minimum	4 (column 3)
Column-3 maximum	4
Saddle element	4
Saddle location (1-indexed)	row 3, column 3

Concept & Theory

Topic. Saddle-point search in a matrix — a row-local test combined with a column-global check.

Key relations. $A(i,j)$ is a saddle point iff $A(i,j)=\min_k A(i,k)$ AND $A(i,j)=\max_k A(k,j)$.

Why this works. A saddle point is, by definition, weakly smaller than every element in its own row and weakly larger than every element in its own column; because the problem guarantees uniqueness, it suffices to test every row's own minimum (a necessary condition) against its column's maximum (the sufficient condition), rather than the $O(n^3)$ approach of testing every cell against both its full row and full column.

Common pitfall. Confusing which extremum applies to which axis (row-minimum vs. column-maximum, not the reverse); breaking ties incorrectly when a row has more than one occurrence of its minimum value (only the specific column where the minimum was found needs the column-maximum test, not every tied column) — not an issue here since uniqueness is assumed.

Source. Cormen et al., Introduction to Algorithms, 4th ed., §2.1–2.2 (array scanning algorithms and loop invariants).

Question 3 of 9: Programming — Saddle Point in a 2-D Array

Question 3: Programming — Saddle Point in a 2-D Array (20 marks)