## Amazon Interview Question

SDE-2s**Country:**United States

**Interview Type:**In-Person

This can be done using maximum contiguous sum subarray.

1. First add forward and backward for each location. like 1 forward + 2 backward for 1st index i.e. ith forward + (i+1)th backward for ith index cost.

2. Now apply maximum contiguous sum subarray to get the subarray <i,j>. Answer would be <i, j+1>.

Time Complexity: O(n) + O(n).

Space Complexity: O(n). (for storing the result. we can make it O(1), if we reuse the any of the forward and backward input array).

Sort one of the arrays of length N. Iterate the other array of length M and do a binary search in the first array updating the global maximum. O(N*log(N) + M*log(N))

- adr October 10, 2018