Hi, I had a phone screen with snap today. Here is the question i was asked.
Image region with sum
Write code which determines whether the sum of all elements in a rectangular area
in a square 2d array are equal to a target, and if true, prints out the coordinates
(top left and bottom right) of a rectangular area which has the target sum.
Constraints:
- All elements in the array are positive
- The input array is valid (e.g all rows have the same length)
- If there are multiple solutions, any one is valid, don't need to find all
Example 1:
Input array:
[2, 6, 4]
[8, 3, 1]
[4, 5, 2]
Target:
20
Output:
[1,0], [2,1]
This region sums to 20:
[_, _, _]
[8, 3, _]
[4, 5, _]Started with brute force, asked to run the code, Talked about time complexity.
Gave me couple of pointers, but i counldn't solve it the most optimal way.
I guess i need to prepare more.