CareerCup

Since the matrix is sparse, I would like to store the data in a hashmap of hashmap rather than the traditional [][].

class SparseMatrix {
    private final Map<Integer, Map<Integer, Integer>> map;
    private final int N;
    private final int M;
    SparseMatrix(int numRow, int numCol) {
        N = numRow;
        M = numCol;
        map = new HashMap<>();
    }

    // assume 0 index
    void set(int row, int col, int val) {
        if (row < 0 || row >= N || col < 0 || col >= M) {
            throw new IllegalArgumentException();
        }
        Map<Integer, Integer> rowMap = map.get(row);
        if (rowMap == null) {
            rowMap = new HashMap<>();
            map.put(row, rowMap);
        }
        rowMap.put(col, val);
    }

    int sum(int row, int col) {
        int sum = 0;
        for(int r : map.keySet()) {
            if (r <= row) {
                for(int c : map.get(r).keySet()) {
                    if (c <= col) {
                        sum += map.get(r).get(c);
                    }
                }
            }
        }
        return sum;
    }
}

void set(int row, int col, int val) {
	return matrix[row][col] = val;
}

int sum(int row, int col){
	int res = 0;
	for(int r = 0; r <= row; r++){
		if(r==row){
			for(int c = 0; c <= col; c++){
				res += matrix[r][c];
} 
		} else {
			for(int c = 0; c <= matrix[r].length; c++){
				res += matrix[r][c];
} 
		}
	}
	return res;
}

sorry for the bad format above.

This can be done using 2d segment/BIT tree. The idea is that you first build a tree by first coordinate and then for each node of that tree you build a segment tree by second coordinate.
Since input parameters are int, you can build a segment tree for [0,MAX_INT] * [0, MAX_INT] and you will have O(log(INT_MAX)^2) complexity.
Do they really ask you to implement 2d segment trees? I doubt one would write that if never written before and this is so topcoder/hackerrank specific.

Yes, BIT is good if matrix is not sparse. Here matrix is sparse so need to use some other data structure/ algo to improve space and time complexity (Map).

We can use a single hash where the key is a 64-bit int that has both the row and column in it (shift row 32 bits, OR with column).

Here's the code in C#:

private Dictionary<long, int> dict = new Dictionary<long, int>();

        public void set(int row, int col, int val) {
            dict[makeCoord(row, col)] = val;
        }

        public int sum(int row, int col) {
            int result = 0;
            for (int i = 0 ; i <= row; i++) {
                for (int j = 0 ; j <= col; j++) {
                    long coord = makeCoord(i,j);
                    if (this.dict.ContainsKey(coord)) {
                        result += this.dict[makeCoord(i,j)];
                    }
                }
            }
            return result;
        }        

        private long makeCoord(int row, int col) {
            long coord = (long)row << 32;
            return (coord | (long)col); 
        }

I did not remember that it was SPARSE, but in any case you can get the idea. The time complexity is O(rows) or O(columns):.

public class NotSparseMatrix{
	private int[][] matrix;
	private int[][] columnSum;

	private int rows, columns;

	public SparseMatrix(int rows, int columns){
		this.columns = columns;
		this.rows = rows;

		this.matrix = new int[columns][rows];
		this.columnSum = new int[columns][rows];
	}

	public void set(int row, int col, int val){
		if(row < rows && col < columns){
			int difference = val - matrix[col][row];
			for(int i = row; i < rows; i++){
				columnSum[col][i] += difference;
			}
		}

	}

	public int sum(int row, int col){
		int result = 0;
		if(row < rows && col < columns){
			for(int i = 0; i <= col; i++){
				result += columnSum[i][row];
			}
		}
		return result;
	}

}

class SparseMatrix(object):
    def __init__(self):
        self.vals = dict()
    
    def set_val(self, row, col, val):
        self.vals[(row, col)] = val
    
    def sum_matrix(self, row, col):
        result = 0
        if len(self.vals) < (row+1)*(col+1):
            for i, j in self.vals:
                if i <= row and j <= col:
                    result += self.vals[(i, j)]
        else:
            for i in xrange(row+1):
                for j in xrange(col+1):
                    if (i, j) in self.vals:
                        result += self.vals[(i, j)]
        
        return result

sm = SparseMatrix()
sm.set_val(1,1,10)
sm.set_val(2,3,10)
print sm.sum_matrix(3,3)