last day (16 days later) » 

9:02 PM
0
Q: 3SUM algorithm for ranges in array

cracraWe are given an integer array of size 5000. Then, we are given 10^5 queries which consists of 2 indices (ai, bi). For each query, we have to solve the 3SUM problem on the subarray[ai...bi], and give the number of unordered triples of distinct indices i, j, k such that A[i] + A[j] + A[k] = 0. Her...

 
Link to the problem?
 
I don't have the link, but all the relevant information is in my post. If you have any questions, please ask.
 
Can you give examples? With the 3SUM query, we have to check if a triplet exists with sum = 0? Also, if there ain't a link, how did you come up with 2 seconds time frame?
 
I added some examples and specified the problem further. To answer your first question, we have to find the number of triplets where the sum = 0 in a subarray (refer to the problem statement). For the second question, that is just the time frame we have to solve it in.
 
I think we can cache the ranges while calculating the triplets which would take O(n) space extra space to answer each query in O(1) time.
 
9:02 PM
Could you elaborate on that? Because that would fit in the time frame...
 
I am thinking further on trying to calculate answer for a range as it is a little tricky. For example, let's say we found a triplet in range [1,4] and [1,5]. If we find a triplet in the range [3,7], it kind of collides with previous ranges' answers.
 
Hey vivek, thanks for the help so far. I think first I could do the O(N^2) 3sum algorithm on the original array, and then store the results in a new one
I would have to sort them in a way for easy access
Maybe we could use segment trees for range querying? Not sure though.
 

  last day (16 days later) »