Leetcode 240. Search a 2D Matrix II

Accepted Code

Problem Statement

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Test Cases

Example 1:

Taken from Leetcode.com
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2:

Taken from Leetcode.com
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • All the integers in each row are sorted in ascending order.
  • All the integers in each column are sorted in ascending order.
  • -10^9 <= target <= 10^9

Approach

So in this problem we have to look for a number say target inside the given matrix. We actually do a normal row * col traversal inside the matrix and look for the target value. But this is the method if no other speciality about the matrix is given to us.
In the question, we are given that the numbers in each row is sorted from left to right and numbers in each column is sorted from top to bottom in ascending order. So how this helps us.

Suppose we keep our rowPointer to the first row and the colPointer to the last column and do a loop until we reach the last row and the first column.
Inside the loop, just check for the target we are looking for, if we find it then we are good and return true. Else we are left with 2 possibilities.

  1. Either the current number can be greater than the target. This time we just move the column pointer to the left as the number cannot be present in that entire column as we know the entire column is sorted.
  2. Or the current number can be lesser than the target. This time we just move the row pointer down as the number cannot be present in that entire column as we know the entire row is also sorted.

Algorithm

  1. Use 2 pointer says rowP = 0 and colP = col — 1.
  2. Run until rowP < row && colP ≥ 0.
  3. Check for the target inside the matrix. ie matrix[rowP][colP] == target . Return true here.
  4. Check whether matrix[rowP][colP] > target , do colP -= 1.
  5. Check whether matrix[rowP]colP] < target, do rowP += 1.
  6. If we get out of the loop, then the target is not present inside the matrix else we should have caught it from inside the loop. Return false.

Time and Space Complexity

We are moving row and col one at a time. So our time complexity will be O(row + col).

No extra space is being used here. So our space complexity will be O(1).

Code

Java Code

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Rohith Vazhathody

Rohith Vazhathody

Software Engineer | Weekly articles | Interested in DSA, design | Writes about problem solving, algorithm explanation of my understanding and Java Codes.