Swift solution - Prefix Sum


  • 0
    class NumMatrix {
        
        let prefixSum: [[Int]]
        
        init(_ matrix: [[Int]]) {
            if matrix.count == 0 || matrix[0].count == 0 {
                return
            }
            
            let m = matrix.count
            let n = matrix[0].count
            var prefixSum = [[Int]](repeatElement([Int](repeatElement(0, count: n + 1)), count: m + 1))
            
            for i in 1...m {
                for j in 1...n {
                    prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1]
                }
            }
            
            self.prefixSum = prefixSum
        }
        
        func sumRegion(_ row1: Int, _ col1: Int, _ row2: Int, _ col2: Int) -> Int {
            let iMin = min(row1, row2)
            let iMax = max(row1, row2)
            let jMin = min(col1, col2)
            let jMax = max(col1, col2)
            
            return prefixSum[iMax + 1][jMax + 1] - prefixSum[iMax + 1][jMin] - prefixSum[iMin][jMax + 1] + prefixSum[iMin][jMin]
        }
        
        
    }
    

Log in to reply
 

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