4 lines C, 6 lines Ruby, 7 lines Python, 1-liners

  • 14

    Same O(m+n) method as most, just a bit different style/languages.


    Check the top-right corner. If it's not the target, then remove the top row or rightmost column.

    bool searchMatrix(int** A, int m, int n, int target) {
        int x = ~target;
        while (m && n && (x = A[0][n-1]) != target)
            x < target ? A++, m-- : n--;
        return x == target;


    def search_matrix(matrix, target)
        j = -1
        matrix.each { |row|
            j -= 1 while row[j] && row[j] > target
            return true if row[j] == target


    def searchMatrix(self, matrix, target):
        j = -1
        for row in matrix:
            while j + len(row) and row[j] > target:
                j -= 1
            if row[j] == target:
                return True
        return False


    Relax, I know they're O(mn). This is just for fun (although they did get accepted):

    Python (204 ms):

    def searchMatrix(self, matrix, target):
        return any(target in row for row in matrix)

    Ruby (828 ms):

    def search_matrix(matrix, target)
        matrix.any? { |row| row.include? target }

  • 0

    personally I think this kind of "perl golf" style of code is not going to win your colleagues' hearts in a real production devel setting, due to lower readability , though you probably will get some wow factor in an interview

  • 4

    This is nowhere near code golf (and why "perl"?). These are pretty much regular solutions, maybe except the ternary in the C solution and the j + len(row) in the Python solution. Those two things I might not do in production. Here I do them partly because I find them interesting and worth sharing. There's really no point in sharing the same solution that has already been posted by someone else. That adds absolutely nothing to the discussion and it pisses me off how many people do that.

  • 0

    Very simple, clear and smart solution, as usually of course.

  • 0

    @StefanPochmann Thank you sharing your brilliant code.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.