An array is given, and an index present in it.
A window must be chosen such that it includes the index, has this component maximized — sum(a[i]...a[j])*(j-i+1), but the component must be equal to or less than the threshold (sum(a[i]...a[j])*(j-i+1) <= threshold).
How we can solve this question optimally?
One example of the problem:
Input
N: 8
Arr[]: [2,-3,-4,5,5,6,7,8]
Ind: 4
Threshold = 20
Output
One possible answer
[5,5]
Explanation of output
[5, 5] = 10*2 = 20 <= 20 (threshold)
Is it given, that the elements can be non-negative only ?
Yes, they can be negative too.
I can think of an O(nlog(n)). But it will only work when all a[i]>=0.
We will find the minimum index l such that sum(a[l]...a[i])*(i-l+1)<threshold and then we will loop from l to i. For each iteration we will find a suitable right index>=i using binary search and store the maximum valid answer. Whenever we get a better answer, we simply update the answer.
we can use two pointer as well if they are non-negative. Take two pointers l ,r.pointing to first element of the array initially now we expand the range ( increment r ) as long as we can expand (i.e sum(a[i]...a[j])*(j-i+1) <= threshold) and if the component of our range exceeds the threshold we shrink our range (increment l ). and we can take the maximum among the plausible ranges to get our answer.
It will give a WA
Input Arr : [1,2,3,4,-5].
Ind : 3
Threshold =25.
Yes, he did mention that it will only work when all the values are non-negative.
Oh I didn't saw that , my bad
How is the output [5,5] , and do we have to find component with minimum length or any component will work , and what are the constraints .
Any component will work.
Explanation of output [5, 5] = 10*2 = 20 <= 20 (threshold)
Shouldn't it be [4,5] ( 1 based indexing )
I had placed actual elements there, your output is correct if we return the indexes
I'm not sure as I am noob but we can use DP here to compute all values lesser than Or equal to threshold which includes index element and print max of it again I'm not sure I'm just telling one of the possibility that came to my mind
This is O(n²) in the worst case as count of such numbers can be of the order n². For example take threshold value to be very large, and all the elements to 0 maybe. Now whatever combination you take you will get the value less than threshold value. Suppose there are r elements to the right of index and l elements to the left of index (can be index itself). Total number of possibilities = r*l = r*(n-r) This will be maximum at r=n/2. Therefore in the worst case total number of possibilities = n²/4 .... So even if you use some kind of dp to store all the values less than or equal to threshold then also it's O(n²) atleast.
What if we use some kind of modified kadane here?
Looks very hard, I've seen some similar problems in the past (no spoilers) and even without the threshold they were rather tough, so I don't think that netflix expects a subquadratic solution here.
Thanks for the affirmation. I was wondering how one can expect to achieve subquadratic time in an interview.
Ok, I posted to get a sense of answers. I proposed quadratic too myself during the interview.
can we use CHT here ??
like lets say the line $$$y = threshold $$$, passing through the envelope of hull, interesects on two x-coordinates,$$$x_{left}$$$ and $$$x_{right}$$$ , so for the range $$$[x_{left},x_{right}]$$$, answer is the value on the hull, but how to optimally construct envelope for range so we could answer for any point in range $$$[-\infty,\infty] $$$.
Or any other way to solve this, just curious !! :)
Can't think of anything close to linear/nlogn,i believe that they were expecting O(N*N).
Did you talk through the bruteforce and then gradually arrived to some optimal solution taking hints from interviewer?