algorithmlanguage-agnostic# Algorithm to calculate number of intersecting discs

Given an array `A`

of `N`

integers we draw `N`

discs in a 2D plane, such that i-th disc has center in `(0,i)`

and a radius `A[i]`

. We say that k-th disc and j-th disc intersect, if k-th and j-th discs have at least one common point.

Write a function

```
int number_of_disc_intersections(int[] A);
```

which given an array `A`

describing `N`

discs as explained above, returns the number of pairs of intersecting discs. For example, given `N=6`

and

```
A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0
```

there are 11 pairs of intersecting discs:

```
0th and 1st
0th and 2nd
0th and 4th
1st and 2nd
1st and 3rd
1st and 4th
1st and 5th
2nd and 3rd
2nd and 4th
3rd and 4th
4th and 5th
```

so the function should return 11.
The function should return -1 if the number of intersecting pairs exceeds 10,000,000. The function may assume that `N`

does not exceed 10,000,000.

Solution

So you want to find the number of intersections of the intervals `[i-A[i], i+A[i]]`

.

Maintain a sorted array (call it X) containing the `i-A[i]`

(also have some extra space which has the value `i+A[i]`

in there).

Now walk the array X, starting at the leftmost interval (i.e smallest `i-A[i]`

).

For the current interval, do a binary search to see where the right end point of the interval (i.e. `i+A[i]`

) will go (called the rank). Now you know that it intersects all the elements to the left.

Increment a counter with the rank and subtract current position (assuming one indexed) as we don't want to double count intervals and self intersections.

*O(nlogn)* time, *O(n)* space.

- Difference between back tracking and dynamic programming
- How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?
- How do I predict the required size of a Base32 Decode output?
- Reversing AND Bitwise
- Why does my binary search need an extra comparison? log2(N)+1
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- What is the Time Complexity and Space Complexity of extending a string according to a rule?
- Skyscraper puzzle algorithm
- Check if all elements in a list are equal
- Bitwise Interval Arithmetic
- fast algorithm for drawing filled circles?
- How to find distance from the latitude and longitude of two locations?
- Determine if two rectangles overlap each other?
- Randomly Splitting a Graph according to Conditions
- Maximize distance while pushing crates
- Free a binary tree without recursion
- How can I estimate number of nodes in given tree structure?
- Explanation of class Definition for Binary Trees in leetcode
- Procedural Generation of 2D Rooms
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Advanced Java idiom for 2+ classes implementing a generic interface
- Is there any algorithm in c# to singularize - pluralize a word?
- Number of Common sub sequences of two strings
- Trying to solve problem 19 on Euler Project
- is a "non-decreasing" sequence "increasing"?
- Is it possible to get the original value of a number, after several multiplications **with overflow**?
- Algorithm to determine the highest and lowest possible finishing position of a team in a league
- Algorithm to calculate the number of divisors of a given number
- Rolling or sliding window iterator?
- best way to pick a random subset from a collection?