Java sol using Count-Of-Range and Max sub area problem


  • 0
    C
    public int maxSumSubmatrix(int[][] matrix, int k) {
    		int y = matrix.length;
    		int x = matrix[0].length;
    
                    // rotating the matrix virtually 
    		if (y > x) {
    			int temp = x;
    			x = y;
    			y = temp;
    		}
    
                    // array to store the summation of rows or cols depending on the matrix size
    		int[] arr = new int[x];
    		int maxArea = Integer.MIN_VALUE;
    
                    // runtime of = O(m*m*nlong(n)) where m = longer dimension and n = shorter dimension of matrix
    		for (int left = 0; left < y; left++) {
    			Arrays.fill(arr, 0);
    			for (int right = left; right < y; right++) {
    				for (int i = 0; i < x; i++) {
    					int curVal = 0;
    					if (matrix.length > matrix[0].length) {
    						curVal = matrix[i][right];
    					} else {
    						curVal = matrix[right][i];
    					}
    					
    					arr[i] += curVal;
    
                                            // terminating it incase we find k
    					if (curVal == k || arr[i] == k) {
    						return k;
    					}
    				}
    
                                   // This is same as Count-of-sum-range problem 
    				TreeSet<Integer> set = new TreeSet<Integer>();
    				set.add(0);
    				
    				int curSum = 0;
    				
    				for (int i = 0; i < arr.length; i++) {
    					curSum += arr[i];
    					Integer val = set.ceiling(curSum - k);
    					
    					if(val != null){
            				maxArea = Math.max(maxArea, curSum - val);
    					}
    					
    					set.add(curSum);
    				}
    			}
    		}
    		
    		return maxArea;
    	}
    

Log in to reply
 

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