NumberOfDiscIntersections

//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.
	private int NumberOfDiscInterSectionsSolution(int[] a)
	{
	    int result = 0;
	    int[] dps = new int[a.length];
	    int[] dpe = new int[a.length];

	    for (int i = 0, t = a.length - 1; i < a.length; i++)
	    {
	        int s = i > a[i]? i - a[i]: 0;
	        int e = t - i > a[i]? i + a[i]: t;
	        dps[s]++;
	        dpe[e]++;
	    }

	    int t = 0;
	    for (int i = 0; i < a.length; i++)
	    {
	        if (dps[i] > 0)
	        {
	            result += t * dps[i];
	            result += dps[i] * (dps[i] - 1) / 2;
	            if (10000000 < result) return -1;
	            t += dps[i];
	        }
	        t -= dpe[i];
	    }

	    return result;
	}




int[] n = {1,5,2,1,4,0};
System.out.println("Number Of Disc Inter Sections : "+obj.NumberOfDiscInterSectionsSolution(n));