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/

Spiral traversal of 2D Matrix

Please be careful of m*n and n*n matrix.

Boundary conditions are important.

static void spiralTraversal(int[][] a){

int r = a.length;
int c = a[0].length;

//System.out.println(c);

int r1 = 0, r2 = r-1, c1 = 0, c2 = c-1;

while(r1 <= r2 && c1 <= c2)
{
//System.out.println(r1+","+c2);
for (int i = r1; i <= c2; i ++)
{
System.out.print(a[r1][i]+ " ");
}
r1++;

for(int i = r1; i<= r2 && r1 <= r2; i++)
{
System.out.print(a[i][c2]+ " ");
}

c2--;

for(int i = c2; i>=c1 && c1 <= c2; i--)
{
System.out.print(a[r2][i]+ " ");
}

r2 --;

for(int i = r2; i>=r1; i--)
{
System.out.print(a[i][c1]+ " ");
}
c1++;



}

Find the k-th Smallest Element in the Union of Two Sorted Arrays

Find the minimum element in a sorted and rotated array

/*
-- Base Conditions of array
-- Divide and Conquer Algorithm
-- Find middle element
-- Condition for return result
-- Condition for return left sub array
-- Condition for return right sub array
-- return result if except all test cases
*/

static int minimumElement(int[] a, int l, int r){
if (a == null || r == -1) return -1;
if(l == r) return a[l];

int m = l + (r-l)/2;

if((m-1)>=0 && a[m-1] > a[m]) return a[m];

if(a[l] > a[m]) return minimumElement(a, l, m-1);

else if(a[m] > a[r]) return  minimumElement(a, m+1, r);

return a[0];
}

References:
http://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/