Search in a 2D matrix Leetcode Solution

Let’s uncover the solution to the LeetCode problem ‘Search in a 2D Matrix,’ frequently posed by interviewers due to its demand for sorting and finding expertise. If you possess a basic grasp of binary search, it becomes manageable; if not, fret not—I’ll elucidate the determinant of a 2D matrix.

Welcome back, visitors. Today, I’ll address the challenge of finding numbers within a 2D matrix, also known as locating a number in a 2D array, as they are essentially synonymous. I’ll provide a solution in two steps, accompanied by illustrations.

FREE : If you’re a new visitor preparing for an interview and need help or want to request a new question, you can use the form on the right side to ask your question. It’s free and doesn’t require signing in. Alternatively, you can ask in our Quora space, which is also free, and you’ll receive a response within 24 hours. Go ahead and check it out! do check Find the largest sum subarray using Kadane’s Algorithm ,Mastering Object-Oriented Programming in C++, Palindrome Partitioning A Comprehensive Guide , Method Overloading vs. Method Overriding in C#

Why Binary Search in Sorted 2D Matrices

Don’t be confused when I use the terms ‘2D array’ or ‘2D matrix’—they are essentially the same in programming contexts.

Let’s delve into the solution. Imagine the interviewer provides you with a sorted 2D matrix or array, and you’re tasked with locating a number within it. Some developers resort to using two for loops for this search, but that’s incorrect. When dealing with a sorted 2D array, the optimal approach is to employ the binary search algorithm.

Why is it wrong? Because employing two nested for loops results in a time complexity of O(n^2), making it quadratic. However, employing binary search reduces the time complexity to O(n), making it linear. In other words, using O(n) instead of O(n^2) is advantageous, meaning that nested for loops are more time-consuming compared to a single loop. Understand?

How to Search In A 2D Matrix

I believe you’ve read the section on time complexity. If not, please review it, as it’s crucial to understand why I’m opting to use binary search in a 2D array.

The logic behind searching in a 2D matrix is simple when you’re familiar with binary search. I’m going to employ a two-way search approach, considering both rows and columns. For instance, let’s say I have two variables, ‘i’ representing rows and ‘j’ representing columns. To search, I increment ‘i’ and decrement ‘j’ simultaneously. Then, I add a condition: if ‘i’ and ‘j’ point to a value equal to our target value, return true. otherwise, we continue looping. If the loop concludes without finding the target value, we return false, indicating it’s not present in the 2D matrix. Refer to the illustration below for a clearer understanding.

Additionally, it’s crucial to check each iteration: if the value of ‘i’ and ‘j’ is greater than the target value, we decrement ‘j’ to continue searching within the column. Conversely, if our target value is less than the value at ‘i’ and ‘j’, we increment the row value, denoted by ‘i++’. You can observe this behavior in the illustration provided alongside each iteration. target value was 6 in above animation.

If you find this explanation challenging, perhaps starting from a beginner level would be beneficial. Feel free to explore the ‘Beginner’ and ‘Array’ pages, where I’ve explained basic logic from scratch.

Program To Search In a 2D Matrix

Let’s implement a solution for the ‘Search in a 2D Matrix’ problem. You can apply this logic in programs on LeetCode, GeeksforGeeks, or CodeStudio.

Step 1

As a regular visitor, you may recall that we’ve already completed this step. However, for newcomers, our first step remains consistent across all programs: creating the necessary variables with clear and descriptive names. Remember, making a good first impression with your code is crucial during interviews.

Let’s create four variables: ‘rows’, ‘cols’, ‘i’, and ‘j’. ‘rows’ represents the length of the first dimension of the 2D matrix, while ‘cols’ represents the length of the second dimension. We initialize ‘i’ to 0 and ‘j’ to the length of the second dimension minus 1, hence ‘cols – 1’.

private static bool FindNumberInSortedMatrix(int[,] matrix, int target)
{
    int rows = matrix.GetLength(0);
    int cols = matrix.GetLength(1);

    int i = 0;
    int j = cols - 1;


    return false;
}

Step 2

Now, as discussed in the ‘How to Search in a 2D Matrix’ section, I’ll utilize a while loop to iterate through each element. I’ll implement conditions ensuring that ‘i’ remains less than ‘rows’ and ‘j’ remains greater than or equal to 0.

I’ve incorporated a condition to check if the value at ‘i’ and ‘j’ matches the target value; if so, we return true. If not, we check if the value at ‘i’ and ‘j’ is greater than the target, indicating that the target must be in this row. If this condition isn’t met, we increment ‘i’ because the target value is not in this row. Understand?

 private static bool FindNumberInSortedMatrix(int[,] matrix, int target)
 {
     int rows = matrix.GetLength(0);
     int cols = matrix.GetLength(1);

     int i = 0;
     int j = cols - 1;

     while (i < rows && j >= 0)
     {
         if (matrix[i, j] == target)
         {
             return true;
         }
         else if (matrix[i, j] > target)
         {
             j--; // Move left in the current row check above Illustration how it is working
         }
         else
         {
             i++; // Move down to the next row <strong>check above Illustration how it is working</strong>
         }
     }

     return false;
 }

With this code, searching a 2D matrix becomes effortless.

Summarizing Search in a 2D Matrix

We discussed the importance of understanding time complexity when implementing search algorithms in 2D matrices. Emphasizing the efficiency of binary search over nested loops, we explored how binary search reduces time complexity from quadratic (O(n^2)) to linear (O(n)). Explaining the logic behind searching in a 2D matrix using binary search, we highlighted the iterative process of traversing rows and columns simultaneously.

To facilitate understanding, we recommended starting from a beginner level and referred to beginner and array pages for foundational knowledge. Moving on, we emphasized the significance of creating variables with clear names for better code readability. Finally, we implemented the search logic using a while loop and discussed the conditions for iterating through the matrix and finding the target value. Overall, we concluded that with the provided code, searching in a 2D matrix becomes straightforward.