How should I practice Staircase Search In A Sorted Matrix?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Goldman Sachs onsite interview problems in FastPrep.

Is Staircase Search In A Sorted Matrix associated with Goldman Sachs?

FastPrep tags this as a Goldman Sachs onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Matrix

Staircase Search In A Sorted Matrix

Learn this problem

● Medium

Goldman SachsFULLTIMEONSITE INTERVIEW

Problem statement

You are given a nonempty rectangular integer matrix matrix and an integer target.

Every row is sorted in nondecreasing order from left to right. Every column is sorted in nondecreasing order from top to bottom. Adjacent rows are not required to form one globally sorted list.

Return true if target appears in matrix, and false otherwise.

What the interview report shared

The Superday report asked a staircase problem to search. It did not restate the matrix contract. This exercise uses conventional 2D Young-tableau staircase search from a corner.

Function

staircaseSearch(matrix: int[][], target: int) → boolean

Examples

Example 1

matrix = [[1,4,7],[2,5,8],[3,6,9]]target = 5return = true

Starting at the top-right value 7, move left because 5 is smaller, then move down because 4 is smaller than 5. The next cell is 5.

Example 2

matrix = [[1,4,7],[2,5,8],[3,6,9]]target = 10return = false

The same walk from 7 reaches the bottom-right value 9 without seeing 10.

Constraints

1 <= matrix.length, matrix[i].length <= 300.
matrix is rectangular: every row has the same length.
-10^9 <= matrix[i][j], target <= 10^9.
Each row is sorted nondecreasing left to right.
Each column is sorted nondecreasing top to bottom.