I came across this problem in an online hiring challenge.
Find a position X in the array A consisting of N elements, such that the difference between A x A 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?
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)
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)
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!