Vdopia Interview Question
Country: United States
Interview Type: Phone Interview
First: O((2^n-1) * (2^n-1)) is O(2^(2n)), not O(4^n).
Second: it's not necessarily true that you have to probe all possible subarrays. For instance, suppose you were given an n of length n and you wanted to find the maximum pair (i.e., the largest sum of any two elements in the array, not necessarily consecutive). There are n^2 pairs, but it would take you only O(n) time to find this -- you just find the largest two elements.
It can be solved in O(m^2 * n^2) which I mentioned as O(n^4) as follows :-
Iterate over the sub-array from 1 to n
Iterate over the sub-array from 1 to m
iterate over the rows
iterate over the columns
In the above 4 iterations all the possible sub-arrays can be covered. which is O(n^4).
Finding the largest 2 elements may not solve the problem. As we have to add all the elements of the sub-array, hence the two largest may contain a very low element, which could make it lesser than the individual sub-array.
Modified Kadane algorithm can perform the task.
Time Complexity: O(M^2*N)
Space Complexity: O(M)// number of rows
Check for each sub-array starting with column number i to column number j. Store the sum[elements with row 0 will be summed & stored in temp[0] & so on] in the temporary buffer. Apply kadane algorithm on the temp[] to find the maximum sum contiguous subsequence. Let maximum sum subsequence in temp[] lies between y1 & y2. Keep updating the maximum sum till now as well as y1,y2,i&j.
How can you solve it in n^4. If I assume that I have been given nxn array then count of possible sub arrays would be (2^n -1 ) *(2^n-1), which is exponential in n, so, just probing such data would mean o(4^n).
- ghost May 25, 2012