I came across this problem in an online hiring challenge.
The Challenge
Find a position X in the array A consisting of N elements, such that the difference between A[0] x A[1] x ... x A[X] and A[X+1] x A[X+2] x ... x A[N-1] is minimum.
How would you approach this problem in time as well as space efficient way?
My Approach #1
I had two arrays leftArr and rightArr that store the left and right subarray product for each element in the array A.
Then I created another array difference to hold the absolute difference between corresponding elements in leftArr and rightArr.
I used index() and min() function to find the index of the smallest element in the difference array.
RESULT: Memory Limit Exceeded! (for almost all test cases except 2)
My Approach #2
I found the two product arrays to be redundant.
This time, instead of storing the product in arrays, I used two variables leftProduct and rightProduct.
I got rid of the difference array too and instead, had new minDiff and minDiffIndex variables to find the minimum difference and it's index.
Initially, I calculated the product of the entire array and stored it in the rightProduct.
Then, I iterated over the array once again and at each stop, I multiplied the current number with the leftProduct and divided the rightProduct.
Simultaneously, I calculated the difference and saved the index if the difference was found to be smaller than the minDiff.
Finally, I printed the minDiffIndex.
RESULT: Time Limit Exceeded! (for the same test cases)
Conclusion
After being unsuccessful, I gave up and came over to dev.to to ask for better approaches and suggestions.
If you have a better approach in mind, do comment below!
Cheers!
Top comments (6)
By time limit exceeded I assume you mean they wanted to the running time of the algorithm to be faster? If so I think you have a good starting point in your second solution.
I don't have the answer, but I would probably think about why that algorithm is so slow, which might depend on the size of the numbers being multiplied or the size of the arrays themselves.
If the numbers are large maybe there is a way to know something about the difference of the two products without computing the actual products.
For example, without calculating anything I know that the product of [13,27] is less than [14,28], and both will be closer to each other than [13,28,92].
The other thing that comes to mind is you basically have have (N-2) possible values of X, but maybe you don't need to examine all of them? For these kinds of problems I find it helpful to work through the algorithm manually and see where I could cut corners.
My thought process goes something like this:
minDiff
target I need to beat - in this case I case I don't need to know the exact diff, if I can prove it's bigger thanminDiff
minDiff+Z
to be worth calculatingminDiff
minDiff
I doubt this thought process would get me anywhere in an interview setting, but I think it would give me some ideas for different approaches. Even if these ideas don't work, I think I'd learn something about the problem from exploring them.
That's some good insight into the problem!
Also now I'm wondering whether my choice of programming language was the reason for timeout.
Usually in most online platforms, the timeout would be different for different programming languages right?
But the time and memory constraints for this problem was fixed at something like 2s and 350 MB. (I'm unable to check now. The challenge has ended)
And the input was quite large. When I used the / operator, I got an error saying can't divide such a huge float or something like that. I had to use // instead to do integer division.
So maybe, I should have tried in C++/Go too.
The trick is that you can deduce the products for the next
X
from the ones of the currentX
without multiplying everything again:Using that, you just need two passes on the array - once to get the initial product of the second half (the entire array) and once again to update the products for each element and find the minimal difference:
How is this different from my second approach?
Now that I look at it - it isn't. I was probably not paying enough attention when I looked at your original post, and thought that you are calculating the entire products for each index...
The time complexity should be linear, and because every element can change the result you can't have sublinear complexity. So how did you exceed the time complexity? Are they timing the actual run instead of doing complexity analysis?
Yes I think the actual run time is considered for timeout.
I'm unsure of what went wrong. That's why I wanted to discuss about this challenge. :)