---

Mastering Saddle Points in Common Lisp: From Zero to Hero

A saddle point in a matrix is an element that is simultaneously the maximum value in its row and the minimum value in its column. This comprehensive guide provides a complete walkthrough on how to identify these unique coordinates using Common Lisp, covering matrix traversal, algorithmic logic, and performance optimization.

Imagine you're searching for the perfect spot to build a treehouse. You have a topographical map, a grid of numbers representing tree heights. You want a spot with an unobstructed view of the sunrise and sunset, meaning it must be the tallest tree in its east-west row. But you also want it nestled in a valley for protection, making it the shortest tree in its north-south column. This perfect spot is a "saddle point."

Finding this ideal location in a vast forest, or more abstractly, in a large dataset, can feel like an overwhelming task. How do you systematically check every single point against its entire row and column without getting lost? This is a classic computational problem that tests your ability to handle multi-dimensional data structures and implement efficient search algorithms. In this guide, we'll demystify this challenge and show you how the expressive power of Common Lisp makes it an elegant tool for solving it.

---

What Exactly Is a Saddle Point?

In mathematics and computer science, a saddle point is a specific element within a two-dimensional array or matrix that holds a unique distinction. To qualify as a saddle point, an element must satisfy two strict conditions simultaneously:

• Row Maximum: It must be greater than or equal to every other element in its own row.
• Column Minimum: It must be less than or equal to every other element in its own column.

The name "saddle point" comes from its resemblance to the shape of a horse's saddle, which curves up in one direction (front to back) and down in another (side to side). The center point of the saddle is the highest point along the side-to-side axis but the lowest point along the front-to-back axis.

Consider the following 3x3 matrix:

      Col 0  Col 1  Col 2
      ┌───┬───┬───┐
Row 0 │ 9 │ 8 │ 7 │
      ├───┼───┼───┤
Row 1 │ 5 │ 3 │ 2 │  <-- The value '5' is the max in its row.
      ├───┼───┼───┤
Row 2 │ 6 │ 6 │ 7 │
      └───┴───┴───┘
        ^
        │
        The value '5' is the min in its column.

Let's analyze the element 5 at coordinate (1, 0):

• In its row (Row 1), the elements are [5, 3, 2]. The maximum value is 5.
• In its column (Column 0), the elements are [9, 5, 6]. The minimum value is 5.

Since 5 is both the maximum of its row and the minimum of its column, it is a saddle point. A matrix can have zero, one, or multiple saddle points.

---

Why Are Saddle Points Important in the Real World?

While the treehouse analogy is a great starting point, the concept of a saddle point has significant applications in various technical fields. It's a fundamental idea in optimization and equilibrium theory.

Game Theory and Minimax

In two-player, zero-sum games (like chess or tic-tac-toe), a saddle point represents a stable equilibrium. It's the point where one player's maximum possible loss (maximin) is equal to the other player's minimum possible gain (minimax). If a game has a saddle point, it means there is a pure strategy where neither player can improve their outcome by unilaterally changing their move. The value at the saddle point is the "value of the game."

Optimization Problems

In calculus and optimization, saddle points are critical points of a function of multiple variables that are neither a local maximum nor a local minimum. Identifying these points is crucial for understanding the landscape of a function and avoiding them when searching for true optimal solutions using algorithms like gradient descent.

Data Analysis and Signal Processing

When analyzing complex data surfaces, identifying saddle points can help in understanding the topology of the data. It can reveal points of transition or instability in a system, which is valuable in fields ranging from physics to economic modeling.

---

How To Find Saddle Points: The Algorithmic Approach

Before diving into Common Lisp code, it's essential to understand the underlying logic. A straightforward, brute-force algorithm is the most intuitive way to start. The core idea is to inspect every single element in the matrix and check if it meets our two criteria.

Here is a step-by-step breakdown of the logic:

1. Initialization: Create an empty list to store the coordinates of any found saddle points.
2. Outer Loop (Rows): Iterate through each row of the matrix, from the first row to the last.
3. Inner Loop (Columns): For each row, iterate through each column, from the first column to the last. This allows you to visit every element (i, j).
4. The Check: For the current element matrix[i][j]:
   • Check if it's the maximum value in its entire row (row i).
   • Check if it's the minimum value in its entire column (column j).
5. Decision: If both conditions from the previous step are true, then the element is a saddle point. Add its coordinates (i+1, j+1) (using 1-based indexing for readability) to your results list.
6. Completion: After checking every element, return the list of saddle point coordinates.

This process guarantees that we won't miss any potential saddle points because every single cell is evaluated. Let's visualize this flow.

Algorithm Flow Diagram (Naive Approach)

    ● Start
    │
    ▼
  ┌──────────────────┐
  │ Initialize empty │
  │ results list     │
  └─────────┬────────┘
            │
            ▼
  ┌──────────────────┐
  │ For each row `i` │
  └─────────┬────────┘
            │
            ▼
  ┌────────────────────┐
  │ For each column `j`│
  └──────────┬─────────┘
             │
             ▼
    ◆ Is matrix[i][j] the max of row `i`?
   ╱           ╲
  Yes           No
  │              │
  ▼              │
 ◆ Is matrix[i][j] ↘
╱  the min of col `j`? ╲
Yes                   No
 │                     │
 ▼                     │
┌─────────────────┐    │
│ Add (i, j) to   │    │
│ results list    ├────┘
└─────────────────┘    │
 │                     │
 └──────────┬──────────┘
            │
            ▼
  ┌──────────────────┐
  │ Return results   │
  └──────────────────┘
            │
            ▼
         ● End

This approach is correct and easy to understand, but as we'll see later, it's not the most efficient. For each of the M x N elements, we perform a scan of its row (N elements) and its column (M elements), leading to a significant number of comparisons.

---

Where Common Lisp Shines: The Implementation

Now, let's translate this logic into Common Lisp code. The solution provided in the kodikra.com module is a functional and idiomatic way to tackle the problem. We'll break it down function by function to understand every detail.

The solution is split into two main functions: a helper function get-rows-or-columns to abstract away data access, and the main function saddle-points that orchestrates the search.

The Helper Function: get-rows-or-columns

Working with columns in a row-major matrix can be cumbersome. This helper function cleverly provides a unified way to extract either all rows or all columns from the input matrix. This is a form of matrix transposition when fetching columns.

(defun get-rows-or-columns (matrix dimension)
  "Extracts all rows (dimension=0) or all columns (dimension=1) from a matrix."
  (loop for i from 0 below (array-dimension matrix dimension)
        collect (loop for j from 0 below (array-dimension matrix (abs (1- dimension)))
                      if (zerop dimension)
                        collect (aref matrix i j)
                      else
                        collect (aref matrix j i))))

Code Walkthrough:

• (defun get-rows-or-columns (matrix dimension)): Defines a function that takes the matrix and a dimension flag as input. By convention, dimension=0 will mean "get rows" and dimension=1 will mean "get columns".
• (loop for i from 0 below (array-dimension matrix dimension) ...): This is the outer loop.
  • If dimension is 0, it iterates from i = 0 to the number of rows.
  • If dimension is 1, it iterates from i = 0 to the number of columns.
• collect (loop for j from 0 below (array-dimension matrix (abs (1- dimension))) ...): This is the inner loop. The magic happens in (abs (1- dimension)).
  • If dimension is 0, (abs (1- 0)) is 1. The inner loop iterates through the columns.
  • If dimension is 1, (abs (1- 1)) is 0. The inner loop iterates through the rows.
• if (zerop dimension) collect (aref matrix i j) else collect (aref matrix j i): This is the core logic.
  • If we are getting rows (dimension=0), we access elements as (aref matrix i j), which is the standard row-by-row traversal.
  • If we are getting columns (dimension=1), we access elements as (aref matrix j i). This swaps the indices, effectively reading down a column for each outer loop iteration.

The result is a list of lists. If you ask for rows, you get '((row1) (row2) ...). If you ask for columns, you get '((col1) (col2) ...).

The Main Function: saddle-points

This function uses the helper to get the data it needs and then iterates through the matrix to find the saddle points.

(defun saddle-points (matrix)
  "Calculates the saddle points of a matrix."
  (unless (equal (array-dimensions matrix) '(0)) ; Handle empty matrix case
    (let* ((rows (get-rows-or-columns matrix 0))
           (cols (get-rows-or-columns matrix 1)))
      (loop for r from 0 below (length rows)
            append (loop for c from 0 below (length cols)
                         for val = (aref matrix r c)
                         when (and (= val (apply #'max (nth r rows)))
                                   (= val (apply #'min (nth c cols))))
                           collect (list (1+ r) (1+ c)))))))

Code Walkthrough:

• (unless (equal (array-dimensions matrix) '(0)) ...): This is a guard clause. It checks if the matrix is empty (specifically, if it has 0 rows). If it is, it returns NIL, preventing errors. The original solution had '(1 0), which is a bit specific; checking for a dimension of '(0) is a more general way to handle an empty matrix from make-array.
• (let* ((rows (get-rows-or-columns matrix 0)) (cols (get-rows-or-columns matrix 1))) ...): This sets up our local variables. let* is used so that cols could potentially reference rows if needed (though it doesn't here). We call our helper function to pre-calculate all rows and all columns and store them.
• (loop for r from 0 below (length rows) ...): The outer loop iterates through the row indices, from 0 to num_rows - 1.
• append (loop for c from 0 below (length cols) ...): The inner loop iterates through column indices. The append keyword is used to collect results from each inner loop run and flatten them into a single list.
• for val = (aref matrix r c): For each coordinate (r, c), we fetch its value and store it in the local loop variable val.
• when (and (= val (apply #'max (nth r rows))) (= val (apply #'min (nth c cols)))): This is the heart of the saddle point check.
  • (nth r rows) retrieves the list representing the r-th row.
  • (apply #'max ...) finds the maximum value in that list.
  • (= val ...) checks if our current element's value is equal to the row maximum.
  • The same logic is repeated for the column minimum using (nth c cols) and #'min.
  • The and macro ensures both conditions must be true.
• collect (list (1+ r) (1+ c)): If the when condition is met, we create a list with the 1-based coordinates (row+1, col+1) and collect it.

---

A More Performant Approach: Pre-computation

The provided solution is functionally correct and quite readable. However, it has a performance bottleneck. Inside the nested loops, for every single element, it calls apply #'max on a row and apply #'min on a column. This means the max of each row and min of each column are recalculated many, many times.

The time complexity is roughly O(M * N * (M + N)), where M is the number of rows and N is the number of columns. We can dramatically improve this to O(M * N) by pre-computing the maximums and minimums first.

The Optimized Algorithm

1. Create an array called row-maxes of size M. Iterate through each row of the matrix and store its maximum value in this array.
2. Create an array called col-mins of size N. Iterate through each column of the matrix and store its minimum value in this array.
3. Iterate through the matrix a final time. For each element matrix[r][c], it is a saddle point if and only if matrix[r][c] == row-maxes[r] AND matrix[r][c] == col-mins[c].

This approach involves three separate passes over the data, but none of them are nested in a way that causes a complexity explosion. The total work is proportional to scanning the matrix three times, which simplifies to O(M * N).

Optimized Algorithm Flow Diagram

    ● Start
    │
    ▼
  ┌──────────────────┐
  │ Create array     │
  │ `row-maxes`      │
  └─────────┬────────┘
            │
            ▼
  ┌──────────────────┐
  │ For each row `i`,│
  │ find max, store  │
  │ in `row-maxes[i]`│
  └─────────┬────────┘
            │
            ▼
  ┌──────────────────┐
  │ Create array     │
  │ `col-mins`       │
  └─────────┬────────┘
            │
            ▼
  ┌──────────────────┐
  │ For each col `j`,│
  │ find min, store  │
  │ in `col-mins[j]` │
  └─────────┬────────┘
            │
            ▼
  ┌──────────────────┐
  │ For each element │
  │ `matrix[i][j]`   │
  └─────────┬────────┘
            │
            ▼
   ◆ matrix[i][j] == row-maxes[i]
   │   AND
   ◆ matrix[i][j] == col-mins[j]?
   ╱           ╲
  Yes           No
  │              │
  ▼              │
┌───────────┐    │
│ Add (i, j)│    │
│ to results├────┘
└───────────┘    │
 │               │
 └───────┬───────┘
         ▼
    ● End

Optimized Common Lisp Implementation

Here is how you could write the more performant version in Common Lisp:

(defun saddle-points-optimized (matrix)
  "Calculates saddle points efficiently by pre-computing row maxes and col mins."
  (destructuring-bind (rows cols) (array-dimensions matrix)
    (when (and (> rows 0) (> cols 0))
      (let ((row-maxes (make-array rows))
            (col-mins (make-array cols)))

        ;; 1. Pre-compute maximum of each row
        (loop for r from 0 below rows
              do (setf (aref row-maxes r)
                       (loop for c from 0 below cols
                             maximize (aref matrix r c))))

        ;; 2. Pre-compute minimum of each column
        (loop for c from 0 below cols
              do (setf (aref col-mins c)
                       (loop for r from 0 below rows
                             minimize (aref matrix r c))))

        ;; 3. Find points that match both criteria
        (loop for r from 0 below rows
              append (loop for c from 0 below cols
                           for val = (aref matrix r c)
                           when (and (= val (aref row-maxes r))
                                     (= val (aref col-mins c)))
                             collect (list (1+ r) (1+ c))))))))

Comparison of Approaches

Let's summarize the trade-offs between the two implementations.

Attribute	Initial Kodikra Solution	Optimized Solution
Time Complexity	O(M*N * (M+N)) - Slower	O(M*N) - Faster
Space Complexity	O(M*N) for storing rows/cols lists	O(M+N) for storing maxes/mins arrays
Readability	Good, but logic is nested. The `get-rows-or-columns` helper adds a layer of abstraction.	Arguably clearer, as the three distinct steps (find maxes, find mins, check points) are separate.
Idiomatic Lisp	Very idiomatic, uses functional helpers and `apply`.	Also idiomatic, uses `loop`'s `maximize` and `minimize` clauses for concise computation.

For small matrices, the difference is negligible. But for large datasets, the optimized version will be orders of magnitude faster, making it the superior choice for production systems.

---

Frequently Asked Questions (FAQ)

Can a matrix have more than one saddle point?

Yes, absolutely. If multiple elements satisfy the condition, they are all considered saddle points. This can happen if the values are not unique. For example, in the matrix [[3, 3], [1, 1]], both 3's are saddle points.

What happens if the input matrix is empty?

A well-written function should handle this gracefully. Our functions check for empty or invalid dimensions and return an empty list (NIL in Lisp), which is the correct behavior as an empty matrix contains no saddle points.

Is the value of a saddle point always unique?

No. As seen in the example above, you can have multiple saddle points with the same value. However, if a matrix has more than one saddle point, all saddle points must have the same value. This is because if S1 and S2 are two saddle points, S1 must be less than or equal to any element in its column (including S2 if they share a column), and S2 must be less than or equal to any element in its column (including S1). A similar logic applies to rows, forcing them to be equal.

How does this concept relate to the Minimax theorem in game theory?

The Minimax theorem states that for every two-person, zero-sum game with finite strategies, there exists a value V and a mixed strategy for each player, such that one player can guarantee a win of at least V, and the other can guarantee a loss of at most V. A saddle point in the game's payoff matrix represents a case where this equilibrium can be achieved with a "pure strategy" (always choosing the same move), and the value of the saddle point is the value V of the game.

Why use Common Lisp for this kind of problem?

Common Lisp excels at symbolic manipulation and rapid prototyping. Its powerful LOOP macro, interactive development environment (REPL), and robust condition system make it ideal for exploring algorithms. As demonstrated, complex iterations and data transformations can often be expressed very concisely and elegantly.

Are there built-in Lisp functions that can simplify this task further?

While there isn't a single `find-saddle-points` function, Common Lisp's rich library of sequence functions and the LOOP macro are the primary tools. For more advanced numerical computing, libraries like Lisp-Stat or numerical libraries that interface with BLAS/LAPACK could provide highly optimized matrix operations, though that would be overkill for this specific problem.

---

Conclusion

We've journeyed from a simple real-world problem—finding the perfect treehouse spot—to a deep understanding of saddle points and their implementation in Common Lisp. You've learned not just what a saddle point is, but how to devise an algorithm to find it, how to implement that algorithm idiomatically, and most importantly, how to analyze its performance and optimize it for efficiency.

The key takeaway is the power of pre-computation. By taking a moment to calculate row maximums and column minimums upfront, we transformed an algorithm with polynomial complexity into a much more scalable linear-time solution. This principle of avoiding redundant work inside loops is a cornerstone of writing efficient code in any language.

This module from the kodikra.com curriculum serves as a perfect example of how a seemingly simple problem can teach profound lessons about algorithmic design, data structures, and the unique strengths of a language like Common Lisp.

Disclaimer: All code examples are written for modern Common Lisp and have been tested with implementations like SBCL 2.4.x. Behavior may vary with older or different Lisp implementations.

Ready to tackle the next challenge? Continue your journey on the Common Lisp learning path or explore our complete guide to Common Lisp for more in-depth tutorials.

---

Published by Kodikra — Your trusted Common-lisp learning resource.