Write an algorithm such that if an element in an M*N matrix is 0, its entire row and column set to zero.

Program:

Connect n ropes with minimum cost: JAVA

Following is complete algorithm for finding the minimum cost for connecting n ropes.
Let there be n ropes of lengths stored in an array len[0..n-1]
1) Create a min heap and insert all lengths into the min heap.
2) Do following while number of elements in min heap is not one.
……a) Extract the minimum and second minimum from min heap
……b) Add the above two extracted values and insert the added value to the min-heap.
3) Return the value of only left item in min heap.

 For 5,6,7,8 is 11+15+26=52 and not 55.

References:
http://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/

Maximum Sum Path in Two Arrays

Given two sorted arrays such the arrays may have some common elements. Find the sum of the maximum sum path to reach from beginning of any array to end of any of the two arrays. We can switch from one array to another array only at common elements.

Program:

Reference:
http://www.geeksforgeeks.org/maximum-sum-path-across-two-arrays/

Find if there is a subarray with 0 sum

// Print starting and ending indexes of all subarrays with 0 sum.

static boolean isExistSumZero(int[] arr){
int len = arr.length;

if(len == 0) return false;
int sum = 0, start=0, end=0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i< len; i++)
{
sum += arr[i];

if(arr[i] == 0 || sum == 0 || map.get(sum) != null)
{
if(map.get(sum) != null)
start = map.get(sum)+1;
else if(arr[i] == 0) start = i;
else start = 0;
end = i;
System.out.println(start +","+ end);
return true;
}

map.put(sum, i);
}
return false;
}

References:
http://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/

Search in a row wise and column wise sorted matrix

 Given a matrix with row sorted and column sorted, find the number given:

static boolean searchGivenNo(int[][] arr, int x){
int rows = arr.length;
if(rows == 0) return false;

int cols = arr[0].length;

for(int i = 0; i<rows; i++)
{
for(int j = cols-1; j>=0; j--)
{
if(arr[i][j] == x) return true;

if(arr[i][j] < x) break;
}
}
return false;
}


References:
http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/

Smallest subarray with sum greater than a given value

static int findSmallestSubArrayLen(int[] arr, int x){

int len = arr.length;

int sum = 0, min = len, r = 0,rear = 0,front = 0;

for(int i = 0; i<len; i++)
{
sum += arr[i];
if(sum > x)
{
for(; r <= i; )
{
if(sum > x)
{
if(min > i-r+1){
min = i-r+1;
rear = r;
front = i;
}
sum -= arr[r++];
}else break;
}
}
}
if(min != len){
while(rear<=front){
System.out.print(arr[rear++]+",");
}
return min;
}

else return -1;
}

Reference:

http://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/

Create a matrix with alternating rectangles of O and X

Reference:

http://www.geeksforgeeks.org/create-a-matrix-with-alternating-rectangles-of-0-and-x/