I'm given an array $A = [a_1, a_2, ....a_n] $ using which I construct $n-1$ contiguous line segments by drawing a line from $(i,a_i)$ to $(i+1, a_{i+1})$. Now, I'm given $q$ queries in the form of $x_1, x_2, y, l, r$ where $l$ and $r$ are the range for the array $A$ and the rest indicate a horizontal line segment $L$ from $(x_1, y)$ to $(x_2, y)$. For each query, I want to find total intersections of $L$ and the segments in the range $l$ and $r$ in $O(q)$ or $O(q\log{n})$ complexity so that total computational complexity becomes: $O(n + q)$ or $O(n + q\log{n})$

I was able to arrive at a solution that works in $O(nq)$ which simply traverses each range and calculates whether $L$ intersects with the segments or not.
I believe, some pre-processing can be done on $A$ which can reduce the complexity.
Any leads will be appreciated!

  • 1
    $\begingroup$ Can you credit the original source where you encountered this task? $\endgroup$ – D.W. Mar 15 '20 at 23:34
  • $\begingroup$ Can you clarify what you want to compute, exactly? The number of intersections of each query can be $\Omega(n)$, so just listing the intersections can take $\Omega(nq)$ time. Are you just interested in the number of intersections? Do you know all the queries beforehand? Is $O(n + q)$ the total time that you want to spend to answer all the queries? (You say that you want to spend $O(n+q)$ tine "for each query", and it is a bit odd that this complexity depends on $q$). $\endgroup$ – Steven Mar 16 '20 at 0:33
  • 1
    $\begingroup$ @D.W. The source is my friend, who asked me about this problem. He might be knowing the original source $\endgroup$ – Kunal Gupta Mar 16 '20 at 7:29
  • $\begingroup$ @Steven I want to compute, total number intersections of the line $L$ with the segments in the range provided. Yes, I know all the queries beforehand. Yes, $O(n+q)$ is the total time I want to spend on the queries $\endgroup$ – Kunal Gupta Mar 16 '20 at 7:31
  • $\begingroup$ @Steven It seems to me each query can only have 1 intersection, if I understood this correctly. The input array is not $n$ arbirary points, rather its the $n$ points $(i, a_i)$ for $i$ between $1$ and $n$. $\endgroup$ – 6005 Mar 16 '20 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.