- #1

- 168

- 0

## Main Question or Discussion Point

Hi guys, was wondering if someone could help me with a homework problem.

The problem: The input is an N x N matrix of numbers that is already in memory. Each individual row is increasing from left to right. Each individual column is increasing from top to bottom. Give an O(N) worst-case algorithm that decides if a number X is in the matrix.

Attempt at a solution: To be honest, I'm quite stumped. I know that the obvious solution is to check each element for the number, but that could be a O(N^2) complexity algorithm. I know that with a single loop one could traverse the matrix diagonally either starting from the top left and going toward the bottom right, or the other way around, but am not sure how to use this observation to come up with an O(N) complexity algorithm, assuming I'm off to a good start.

The professor has said that a pseudocode solution is fine.

The problem: The input is an N x N matrix of numbers that is already in memory. Each individual row is increasing from left to right. Each individual column is increasing from top to bottom. Give an O(N) worst-case algorithm that decides if a number X is in the matrix.

Attempt at a solution: To be honest, I'm quite stumped. I know that the obvious solution is to check each element for the number, but that could be a O(N^2) complexity algorithm. I know that with a single loop one could traverse the matrix diagonally either starting from the top left and going toward the bottom right, or the other way around, but am not sure how to use this observation to come up with an O(N) complexity algorithm, assuming I'm off to a good start.

The professor has said that a pseudocode solution is fine.