Golang solutions O(m+n) traversal and 2 dimensions binary search


  • 0

    O(m+n) solution, the idea is well explained at here: https://discuss.leetcode.com/topic/20064/my-concise-o-m-n-java-solution. Honestly I could not come up with the solution until I read the thread.

    func searchMatrix(matrix [][]int, target int) bool {
    	ylen := len(matrix)
    	if ylen == 0 {
    		return false
    	}
    	xlen := len(matrix[0])
    	if xlen == 0 {
    		return false
    	}
    
    	x, y := xlen-1, 0
    	current := matrix[y][x]
    
    	stop := false
    	for {
    		switch {
    		case current < target:
    			y++
    			stop = (y > ylen-1)
    		case current > target:
    			x--
    			stop = (x < 0)
    		default:
    			return true
    		}
    		if stop {
    			break
    		}
    		current = matrix[y][x]
    	}
    	return false
    
    

    2 dimensions binary search. We can drop 1/4 of the whole area each time, but a number of calls of recursive function increased by 3 times on every drop. I like this explanation: https://discuss.leetcode.com/topic/33240/java-an-easy-to-understand-divide-and-conquer-method

    I think the complexity is 3^log4(mn)? not so confident.

    func searchMatrix(matrix [][]int, target int) bool {
    	ylen := len(matrix)
    	if ylen == 0 {
    		return false
    	}
    	xlen := len(matrix[0])
    
    	top, bottom, left, right := 0, ylen-1, 0, xlen-1
    	res := false
    	doSearch(&res, matrix, target, top, bottom, left, right)
    	return res
    }
    
    func doSearch(res *bool, matrix [][]int, target int, top, bottom, left, right int) {
    	if *res || bottom < top || right < left {
    		return
    	}
    	midy, midx := top+(bottom-top)/2, left+(right-left)/2
    	mid := matrix[midy][midx]
    	if mid == target {
    		*res = true
    		return
    	}
    
    	if mid < target {
    		doSearch(res, matrix, target, top, midy, midx+1, right)
    		doSearch(res, matrix, target, top+1, bottom, midx+1, right)
    		doSearch(res, matrix, target, top+1, bottom, left, midx)
    		return
    	}
    	doSearch(res, matrix, target, top, midy-1, left, midx-1)
    	doSearch(res, matrix, target, top, midy-1, midx, right)
    	doSearch(res, matrix, target, midy, bottom, left, midx-1)
    }
    
    

Log in to reply
 

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