Zero Sum subarray
Problem1. Zero Sum Subarray - 

An array contains both positive and negative elements, find the subarray whose sum equals 0.

This algorithm will find all subarrays with sum 0 and it can be easily modified to find the minimal one or to keep track of the start and end indexes. This algorithm is O(n).

Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element.

Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j and k with j < k, then the sum of the input till j is equal to the sum till k and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k.

• NOTE: if j + 1 == k, then k is 0 and that's it! ;)
• NOTE: The algorithm should consider a virtual tmp[-1] = 0;
• NOTE: An empty array has sum 0 and it's minimal and this special case should be brought up as well in an interview. Then the interviewer will say that doesn't count but that's another problem! ;)

The implementation can be done in different ways including using a HashMap with pairs but be careful with the special case in the NOTE section above.

Example:

int[] input = {4,  6,  3, -9, -5, 1, 3, 0, 2}
int[] tmp =   {4, 10, 13,  4, -1, 0, 3, 3, 5}

• Value 4 in tmp at index 0 and 3 ==>take  sum of tmp[1] to tmp[3] = 0, length (3 - 1) + 1 = 4
• Value 0 in tmp at index 5 ==> take sum of tmp[0] to tmp[5] = 0, length (5 - 0) + 1 = 6
• Value 3 in tmp at index 6 and 7 ==> take of sum tmp[7] to tmp[7] = 0, length (7 - 7) + 1 = 1

UPDATE

Assuming that in our tmp array we end up with multiple element with the same value then you have to consider every identical pair in it! Example (keep in mind the virtual '0' at index '-1'):

int[] array = {0, 1, -1, 0}
int[] tmp = {0, 1, 0, 0}

By applying the same algorithm described above the 0-sum subarrays are delimited by the following indexes (included):

[0] [0-2] [0-3] [1-2] [1-3] [3]

Although the presence of multiple entries with the same value might impact the complexity of the algorithm depending on the implementation, I believe that by using an inverted index on tmp (mapping a value to the indexes where it appears) we can keep the running time at O(n).

Problem 2 : To find a subarray in a given array containing negative and positive numbers , having sum k.

The solution for this problem is to first find the prefixsum of all the n elements. Create a hashmap having the key as the prefix sum and the index as the n .

eg : 

position in the array   1 2 3  4  5 6  7  8  9

Elements in the array 4 3 5 -3 -1 2 -3  10  2 

p[1] = 4

p[2] = 7

p[3] = 12

p[4] = 9

p[5] = 8

p[6] = 10

p[7] = 7

p[8] = 17

p[9] = 19

i.e p[9] means sum of all elements from 1 to 9

the hashmap will have these sum as key and index as the value eg .

<4 , 1> , <7 ,2> , <12,3> , <9,4> , <8,5> , <10,6> , <7,7> , <17,8>,<19,9>

in our example lets assume that k =1 , read the first key in hashmap , i.e 4 , subtract it with k , then the key becomes 3 check if the hashmap contains any key with 3 , if yes its index i.e value should be less than the current index , i.e 1. There is no key containing 3 . So move ahead , .. similarly we reach 6 th element in hashmap , i.e <10,6> , then 10-1 = 9 .Check if hashmap contains key 9 , yes it is there and its value which is 4 is less than 6 . Hence one subarray is (4+1,6) i.e (5,6) is one of the indices of the subarray having sum 1.

We missed one case before this case , which <8,5> , i.e check if hashmap contains 8-1 = 7 

we found that <7,2> and its value 2 is less than 5 . Hence the subarray becomes (2+1,5) , which is(3,5).

The crucial insight is to consider all the prefix sums, which are the sums of the first t integers in A for
t = 1, 2, . . . , n. That is, consider each prefix sum, S(t), which is defined as
S(t) = a1 + a2 + · · · + at = Sum of ai where i = 1 to t

If we are given all such prefix sums, then we can compute any subarray summation, s(j,k), i.e sum of the elements from j to k indices , in constant time using the formula
s(j,k) = Sk - Sj-1,
where we use the notational convention that S0 = 0. 
It means that the sum of subarray elements from indices j to k is actually the sum of subarray k elements (P[k]) - (minus) the sum of subarray of j-1 P[j-1] elements .

p[1] = 4

p[2] = 7

p[3] = 12

p[4] = 9

p[5] = 8

p[6] = 10

p[7] = 7

p[8] = 17

p[9] = 19 

S(j,k) = S(k) - S(j-1) = 

S(1,2) = S(2) - S(0) = 7

S(2,2) = S(2) - S(1) = 3

S(1,3) = S(3) - S(0) = 12

S(2,3) = S(3) - S(1) = 8

S(3,3) = S(3) - S(2) = 12 - 7 = 5

S(1,4) = S(4) - S(0) = 9

S(2,4) = S(4) - S(1) = 9 - 4 = 5

S(3,4) = S(4) - S(2) = 9 - 7 = 2

S(4,4) = S(4) - S(3) = 9 - 12 = -3

S(1,5) = S(5) - S(0) = 8 - 0 = 8

S(2,5) = S(5) - S(1) = 8 - 4 = 4 

S(3,5) = S(5) - S(2) = 8 - 7 = 1

S(4,5) = S(5) - S(3) = 8 - 12 = -4

S(5,5) = S(5) - S(4) = 8 - 9 = -1

S(1,6) = ...

S(5,6) = S(6) - S(4) = 10 - 9 = 1

Problem 3 : To find the subarray having maximum sum .in a 1D array.
http://www.ics.uci.edu/~goodrich/teach/cs161/notes/MaxSubarray.pdf

Problem 4 : To find a submatrix in a given matrix having maximum sum .
http://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_07_-_Submatrix_with_largest_sum.jsp

Problem 5 : To find the k th smallest element when two sorted arrays are given.

http://discuss.leetcode.com/questions/136/find-the-k-th-smallest-element-in-the-union-of-two-sorted-arrayshttp://discuss.leetcode.com/questions/136/find-the-k-th-smallest-element-in-the-union-of-two-sorted-arrays