Goldman Sachs: Search for a Target in a Matrix Sorted by Rows and Columns

Quick Overview

Decide whether a target value appears in an integer matrix whose rows and columns are each sorted in non-decreasing order. It tests how well a candidate exploits ordering in two directions to avoid scanning every cell, and how carefully they handle duplicates, single-row inputs, and boundary values.

Search for a Target in a Matrix Sorted by Rows and Columns

Company: Goldman Sachs

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

Given a matrix of integers in which every row is sorted in non-decreasing order from left to right and every column is sorted in non-decreasing order from top to bottom, determine whether a target value appears anywhere in the matrix. ### Function Signature `search_sorted_matrix(matrix: list[list[int]], target: int) -> bool` ### Rules - Return `True` if at least one cell equals `target`, and `False` otherwise. - Values may repeat within a row, within a column, or across the matrix. - A row does not have to start after the previous row ends: the first value of a row may be smaller than the last value of the row above it. ### Constraints - `matrix` has `m` rows and `n` columns, with `1 <= m <= 300` and `1 <= n <= 300`; every row has length `n`. - Every element and `target` is an integer in `[-1000000000, 1000000000]`. - The intended solution does not examine every cell. ### Examples Input: `matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]], target = 9` Output: `True` Input: `matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]], target = 15` Output: `False` Input: `matrix = [[-5,-5,0]], target = 1` Output: `False`

Overview: Decide whether a target value appears in an integer matrix whose rows and columns are each sorted in non-decreasing order. It tests how well a candidate exploits ordering in two directions to avoid scanning every cell, and how carefully they handle duplicates, single-row inputs, and boundary values.

You are given a matrix of integers in which every row is sorted in non-decreasing order from left to right and every column is sorted in non-decreasing order from top to bottom. Given an integer `target`, determine whether `target` appears anywhere in the matrix. Return `True` if at least one cell of the matrix equals `target`, and `False` otherwise. The answer is a single boolean, so there is no ordering or tie-breaking to decide: duplicates do not change the result, because you only report existence and never a position. Values may repeat within a row, within a column, or across the matrix. A row does not have to start after the previous row ends: the first value of a row may be smaller than the last value of the row above it, so reading the matrix row by row into one flat list does not necessarily produce a sorted list. The intended solution does not examine every cell. Every element and `target` lies in `[-1000000000, 1000000000]`, so no value can exceed `2^31 - 1` and no arithmetic on these values is required; a 32-bit signed integer is sufficient in every language (Java `int`, C++ `int`). ### Examples Example 1: ``` matrix = [[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17]] target = 9 -> True ``` The cell at row 2, column 2 holds 9, so the target is present. Note that this matrix illustrates the overlap rule: row 1 starts at 2, which is smaller than 11, the last value of row 0. Example 2: ``` matrix = [[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17]] target = 15 -> False ``` The matrix contains 14 and 16 but no 15, so the answer is False. Example 3: ``` matrix = [[-5, -5, 0]] target = 1 -> False ``` A single row with a duplicated value and no cell above 0.

Constraints

`matrix` has `m` rows and `n` columns, with `1 <= m <= 300` and `1 <= n <= 300`; every row has length `n`.
Every row of `matrix` is sorted in non-decreasing order from left to right.
Every column of `matrix` is sorted in non-decreasing order from top to bottom.
Values may repeat within a row, within a column, or across the matrix.
A row does not have to start after the previous row ends: the first value of a row may be smaller than the last value of the row above it.
Every element of `matrix` and `target` is an integer in `[-1000000000, 1000000000]`; no value can exceed `2^31 - 1`, so a 32-bit signed integer type is sufficient.
Return `True` if at least one cell equals `target`, and `False` otherwise.
The intended solution does not examine every cell.

Examples

Input: ([[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17]], 9)

Expected Output: True

Explanation: Source example 1: 9 sits at row 2, column 2, so the target is present.

Input: ([[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17]], 15)

Expected Output: False

Explanation: Source example 2: the matrix holds 14 and 16 but never 15, a gap between present values.

Hints

Both sorted properties hold at the same time. Ask what a single comparison against one well-chosen cell can rule out: is there a starting position from which one comparison eliminates an entire row or an entire column of candidates?
Reading the cells row by row into one flat list does not give you a sorted list, because a row may begin below where the previous row ended. Any approach that assumes a single global order over all cells is unsound on this input.
You only have to report whether the value exists, not where it is or how many times, so repeated values never need to be disambiguated.

Approach

Algorithm (staircase / saddle-point walk). Because each row is sorted left to right and each column is sorted top to bottom, the top-right cell of any sub-rectangle is the largest value in its row of that rectangle and the smallest value in its column of that rectangle. Start at row = 0, col = n - 1 and compare matrix[row][col] with the target:

equal: the target exists, return True;
greater than the target: every cell below it in column col is >= it, hence also greater than the target, so no occurrence of the target can be in that column; drop the column with col -= 1;
less than the target: every cell to its left in row row is <= it, hence also less than the target, so no occurrence of the target can be in that row; drop the row with row += 1.

Invariant: before each comparison, if the target occurs anywhere in the matrix then it occurs inside the sub-rectangle rows [row, m-1] x columns [0, col]. It holds trivially at the start (the whole matrix). Each step removes exactly one full column or one full row that provably contains no occurrence of the target, so the invariant is preserved and no occurrence is ever skipped.

Correctness: the loop can only exit in two ways. If it returns True, it has seen a cell equal to the target, so the answer is genuinely True. If it exits because row == m or col < 0, the surviving rectangle is empty, and by the invariant the target occurs nowhere in the matrix, so False is correct.

Termination and complexity: every iteration either increases row by one or decreases col by one, both bounded, so at most m + n - 1 cells are inspected. Time is O(m + n) and space is O(1) beyond the input, which satisfies the requirement that the intended solution does not examine every cell.

Duplicates: the walk decides existence only. If several cells hold the target, the first one the staircase reaches returns True; the order in which equal values are visited is irrelevant to the boolean answer.

Edge cases: a 1x1 matrix performs a single comparison; a single row (m = 1) degenerates into a right-to-left scan because the walk can only move left before falling off the left edge or matching; a single column (n = 1) only moves down; a matrix whose cells are all equal returns on the first comparison when it matches and otherwise walks one full edge; a target below the global minimum exits off the left edge and a target above the global maximum exits off the bottom edge. A row whose first value is smaller than the previous row's last value is handled naturally, since the argument above only uses within-row and within-column order, never a flattened global order. The reference implementations also guard an empty matrix or an empty first row by returning False, even though the constraints guarantee m >= 1 and n >= 1.

Time complexity:

O(m + n)

Space complexity:

O(1)