How to find a number in a matrix efficiently?

  • Thread starter Thread starter frankfjf
  • Start date Start date
  • Tags Tags
    Data Structures
Click For Summary

Discussion Overview

The discussion revolves around finding an efficient algorithm to determine if a number X exists in an N x N matrix where each row and column is sorted in increasing order. Participants explore potential approaches and strategies for achieving an O(N) worst-case complexity solution.

Discussion Character

  • Homework-related
  • Exploratory
  • Mathematical reasoning

Main Points Raised

  • One participant expresses uncertainty about how to leverage the matrix's properties to achieve the desired complexity, noting that a naive approach would lead to O(N^2) complexity.
  • Another participant suggests examining diagonal elements and questions what bounds can be expected from these elements given the matrix's structure.
  • There is a mention that the top left element is the smallest and the bottom right element is the largest, leading to a discussion about the implications of these facts for searching.
  • A follow-up question asks what the "ideal" element to compare next would be if the target number is between the smallest and largest elements.
  • One participant proposes comparing the element that is one down and one to the right of the current element as a potential next step.
  • Another participant introduces a simpler case of searching in a known ascending array, prompting a discussion about the quickest way to determine if a number exists within it.
  • An analogy involving guessing a random number is presented, exploring strategies to minimize the number of guesses based on feedback from the guesses.

Areas of Agreement / Disagreement

Participants do not reach a consensus on a specific algorithm or approach. Multiple ideas and strategies are proposed, but no definitive solution emerges from the discussion.

Contextual Notes

Participants express uncertainty about the application of diagonal traversal and the implications of the matrix's sorted properties. There are also unresolved questions about the efficiency of various proposed strategies.

Who May Find This Useful

This discussion may be of interest to students and individuals looking for algorithmic strategies in matrix search problems, particularly in the context of homework or academic study in computer science and mathematics.

frankfjf
Messages
166
Reaction score
0
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.
 
Technology news on Phys.org
frankfjf said:
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.

Have you tried looking at the diagonal elements? What bounds can you expect from these elements given the restrictions that are placed on the matrix?
 
Only thing that comes to mind is that the top left element would have to be the smallest and the bottom right element would ahve to be the largest.
 
frankfjf said:
Only thing that comes to mind is that the top left element would have to be the smallest and the bottom right element would ahve to be the largest.
OK, assuming the number you're searching for is greather than the top left number and smaller than the bottom right number, what is the "ideal" element to compare next?
 
The one that's 1 down and 1 to the right of the current element, I'd imagine.
 
How about starting with a simpler case, if you had a known ascending array (a list, not a matrix) of numbers (each number in the list is greater than the preceding number) , what would be the quickest to see if a given number existed in the array of numbers?
 
Last edited:
Hm. I'd say seeing if it was between the smallest and largest numbers, assuming it wasn't one of those.
 
Another analogy then. A computer picks a random number between 1 and 1024, and you have to guess what the number is within so many tries. Each time you guess, the computer will tell you if the number is less than your guess, greater than your guess, or equal to your guess (you found the number). What strategy could you use to minimize the average number of guesses?
 

Similar threads

Python Partial pivoting in getting the reduced row echelon form of a matrix
  • · Replies 2 ·
Replies
2
Views
2K
MHB How to Sort Elements of a Matrix in O(n) Time Complexity?
  • · Replies 1 ·
Replies
1
Views
2K
How Can We Efficiently Parallelize the N-Queens Problem?
  • · Replies 11 ·
Replies
11
Views
5K
Python Simple code example of transforming matrix into upper triangular form
  • · Replies 3 ·
Replies
3
Views
2K
MHB Dynamic programming: which recurrence relation do we use?
  • · Replies 2 ·
Replies
2
Views
2K
Challenge: Find the minimum amount of draws possible for a list of integers
  • · Replies 9 ·
Replies
9
Views
3K
Fast pentadiagonal matrix solver
  • · Replies 1 ·
Replies
1
Views
4K
MHB Find path to minimum cost from start to finish
  • · Replies 19 ·
Replies
19
Views
2K
Understanding busy beavers (noncomputability)
  • · Replies 2 ·
Replies
2
Views
2K
Can someone recommend an algorithm to optimize this data
  • · Replies 25 ·
Replies
25
Views
3K