Category: interview

This problem can be solved using Kadane’s Algorithm.
We start by taking an empty array of zeros of size of the number of rows of input matrix.
We move from left to right columns and calculate max for every column and update up, down, left, right accordingly.
Input matrix mxn
Time = O(m*n*n)
Space = O(m)

package algos;

import java.util.HashMap;

class solution {

	public solution() {
	}

	public HashMap getMaxSum(int[] arr) {
		int max = arr[0], start = 0, end = 0, mstart = 0, mend = 0, currmax = arr[0];
		for (int i = 1; i < arr.length; i++) {

			if (arr[i] > arr[i] + currmax) {
				currmax = arr[i];
				start = i;
				end = i;
			} else {
				currmax = currmax + arr[i];
				end = i;
			}

			if (currmax > max) {
				max = currmax;
				mstart = start;
				mend = end;
			}
		}
		HashMap result = new HashMap();
		result.put("up", mstart);
		result.put("down", mend);
		result.put("max", max);
		return result;
	}

	public HashMap getMaxSubArray(int[][] matrix) {
		int max = matrix[0][0], left = 0, right = 0, up = 0, down = 0;
		int[] rowArray = new int[matrix.length];
		for (int cl = 0; cl < matrix[0].length; cl++) {
			for (int i = 0; i < matrix.length; i++) {
				rowArray[i] = 0;
			}
			for (int cr = cl; cr < matrix[0].length; cr++) {
				for (int row = 0; row < matrix.length; row++) {
					rowArray[row] += matrix[row][cr];
				}
				HashMap currentSet = getMaxSum(rowArray);
				if (currentSet.get("max") > max) {
					max = currentSet.get("max");
					up = currentSet.get("up");
					down = currentSet.get("down");
					left = cl;
					right = cr;
				}
			}
		}

		HashMap result = new HashMap();
		result.put("up", up);
		result.put("down", down);
		result.put("left", left);
		result.put("right", right);
		result.put("max", max);
		return result;
	}

}

public class kadanes {
	public static void main(String[] args) {
		solution sol = new solution();
		int[][] matrix = { { -2, -2, -2 }, { 2, 2, 2 }, { -2, -2, -2 } };
		HashMap result = sol.getMaxSubArray(matrix);
		System.out.println("max:" + result.get("max") + " up:" + result.get("up") + " down:" + result.get("down")
				+ " left:" + result.get("left") + " right:" + result.get("right"));
	}
}

Output

max:6 up:1 down:1 left:0 right:2

This is an implementation that shows you how to override the comparator to sort objects by a property in a Priority Queue. You can use Priority Queues in algorithms like Dijkstra’s and A* to remove the element with the least f(n) value in each iteration. Overriding the compare method can be used to sort ArrayLists (Dynamic Arrays in Java) with sort() method.

Comparator

package algos;
import java.util.Comparator;
import java.util.PriorityQueue;

class StringLengthComparator implements Comparator {
	@Override
	public int compare(Node x, Node y) {
		// Real code should
		// probably be more robust
		// You could also just return x.val- y.val,
		// which would be more efficient.
		if (x.val < y.val) { return -1; } if (x.val > y.val) {
			return 1;
		}
		return 0;
	}
}

class Node {
	String name;
	int val;

	public Node(String name, int val) {
		this.name = name;
		this.val = val;
	}
}

public class pqcls {
	public static void main(String[] args) {
		Comparator comparator = new StringLengthComparator();
		PriorityQueue queue = new PriorityQueue(10, comparator);
		Node n1 = new Node("Shiva", 2);
		Node n2 = new Node("John", 1);
		queue.add(n1);
		queue.add(n2);
		while (queue.size() != 0) {
			System.out.println(queue.remove().name);
		}
	}
}

Output:
John
Shiva

Lambda Functions

If you want to use a more shorter format you can use lambda functions

package algos;

import java.util.PriorityQueue;

public class pqcls {
 public static void main(String[] args)
 {
 PriorityQueue<Node> queue = 
 new PriorityQueue<Node>(10, (a,b)->a.val-b.val);
 Node n1 = new Node("Shiva", 2);
 Node n2 = new Node("John", 1);
 
 queue.add(n1);
 queue.add(n2);
 
 while (queue.size() != 0)
 {
 System.out.println(queue.remove().name);
 }
 }
 }

Output:
John
Shiva

var test = 3;
var pow;
var str='';
for(var i=0; (test/Math.pow(2,i)) > 1; i++) {
 pow = i;
}

for (var j=pow; j>=0; j--) {
 if ( (test & (1<<j)) > 0) 
 str = str + '1';
 else
 str = str + '0';
}
console.log(str);
// logs the value 11 to console.

Demo