Swift solution - Divide and Conquer, Binary Search


  • 0
    class Solution {
        func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
            if matrix.count < 1 {
                return false
            }
            
            let m = matrix.count
            let n = matrix[0].count
            
            return helper(matrix, [0, 0], [m - 1, n - 1], target)
        }
        
        private func helper(_ matrix: [[Int]], _ upperLeft: [Int], _ lowerRight: [Int], _ target: Int) -> Bool {
            if upperLeft[0] > lowerRight[0] || upperLeft[1] > lowerRight[1] || lowerRight[0] >= matrix.count || lowerRight[1] >= matrix[0].count {
                return false
            }
            if lowerRight[0] - upperLeft[0] == 0 && lowerRight[1] - upperLeft[1] == 0 {
                return matrix[upperLeft[0]][upperLeft[1]] == target
            }
            
            let rowMiddle = (upperLeft[0] + lowerRight[0]) >> 1
            let colMiddle = (upperLeft[1] + lowerRight[1]) >> 1
            let diff = matrix[rowMiddle][colMiddle] - target
            
            if diff > 0 {
                return helper(matrix, upperLeft, [rowMiddle, colMiddle], target) || helper(matrix, [upperLeft[0], colMiddle + 1], [rowMiddle, lowerRight[1]], target) || helper(matrix, [rowMiddle + 1, upperLeft[1]], [lowerRight[0], colMiddle], target)
            } else if diff < 0 {
                return helper(matrix, [upperLeft[0], colMiddle + 1], [rowMiddle, lowerRight[1]], target) || helper(matrix, [rowMiddle + 1, upperLeft[1]], [lowerRight[0], colMiddle], target) || helper(matrix, [rowMiddle + 1, colMiddle + 1], lowerRight, target)
            }
            
            return true
        }
    
        func searchMatrix_BinarySearch(_ matrix: [[Int]], _ target: Int) -> Bool {
            if matrix.count < 1 || matrix[0].count < 1 {
                return false
            }
            
            var col = matrix[0].count - 1
            var row = 0
            
            while col >= 0 && row <= matrix.count - 1 {
                if target == matrix[row][col] {
                    return true
                } else if target < matrix[row][col] {
                    col -= 1
                } else {
                    row += 1
                }
            }
            
            return false
        }
    }
    

Log in to reply
 

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