Weakest Strong Link Intuit Python Interview Question

You know that phrase, how a chain is only as strong as its weakest link?

Imagine you had a chain-link fence, represented as a matrix. For the chain-link at position (i, j), the input matrix indicates how strong the chain is at that position (where stronger means a higher number). The numbers in the matrix are unique.

The Weakest Strong Link is defined as the weakest chain-link in its row but also the strongest link in its column.

Given a matrix , return the weakest strong link if it exists; otherwise, return -1. If a weakest strong link exists, it is always exactly one, and it can be proven that no other link will satisfy both conditions simultaneously.

Example #1

Input:
Output:

Explanation:
is the weakest in its row and the strongest in its column , making it the Weakest Strong Link.

Example #2

Input:
Output:

Explanation:
No chain-link satisfies the criteria of being the weakest in its row and the strongest in its column.

To make things easier, let's store the minimum in each row and the maximum in each column using two arrays: for row minimums and for column maximums. After filling these arrays, we iterate over the matrix to check if an element matches both the minimum in its row and the maximum in its column. Since only one element can satisfy both conditions, we return it immediately when found.

Here's the code: