LeetCode Entry

74. Search a 2D Matrix

07.08.2023 medium 2023 kotlin

D Binary Search

74. Search a 2D Matrix medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/301

Problem TLDR

2D Binary Search

Intuition

Just a Binary Search

Approach

For more robust code:

  • inclusive lo and hi
  • the last condition lo == hi
  • move borders lo = mid + 1, hi = mid - 1
  • check the result
  • use built-in functions

Complexity

  • Time complexity: \(O(log(n*m))\)

  • Space complexity: \(O(1)\)

Code


    fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
        var lo = 0
        var hi = matrix.lastIndex
        while (lo <= hi) {
          val mid = lo + (hi - lo) / 2
          val row = matrix[mid]
          if (target in row.first()..row.last())
            return row.binarySearch(target) >= 0
          if (target < row.first()) hi = mid - 1 else lo = mid + 1
        }
        return false
    }