range-sum-query-2d-immutable.go

// https://leetcode.com/problems/range-sum-query-2d-immutable

type NumMatrix struct {
    sums [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    var sums [][]int
    
    for i := 0; i < len(matrix); i++ {
        rows := make([]int, len(matrix[0]))
        prev := 0
        
        for j, val := range matrix[i] {
            prev += val
            rows[j] = prev
        }
        
        sums = append(sums, rows)
    }
    
    return NumMatrix{
        sums: sums,
    }
}

func (m *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    row1 = max(0, row1)
    row2 = max(row1, min(len(m.sums), row2))
    
    col1 = max(0, col1)
    col2 = max(col1, min(len(m.sums[0]), col2))
    
    sum := 0
    
    for row := row1; row <= row2; row++ {
        if col1 < 1 {
            sum += m.sums[row][col2]
        } else {
            sum += m.sums[row][col2] - m.sums[row][col1 - 1]
        }
    }
    
    return sum
}

func min(a, b int) int {
    if a < b {
        return a
    }
    
    return b
}

func max(a, b int) int {
    if a < b {
        return b
    }
    
    return a
}