Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class Solution {
- public int solution(int[] radiuses) {
- int length = radiuses.length;
- int[] startCounts = new int[length];
- int[] endCounts = new int[length];
- // make sure there's no overflows
- for (int i = 0; i < length; i++) {
- radiuses[i] = Math.min(length, radiuses[i]);
- }
- int lastPos = length - 1;
- for (int i = 0; i < length; i++) {
- int radius = radiuses[i];
- int startPos = Math.max(i - radius, 0);
- int endPos = Math.min(i + radius, lastPos);
- startCounts[startPos]++;
- endCounts[endPos]++;
- }
- // printAll(startCounts);
- // printAll(endCounts);
- int intersectCount = 0;
- int currentLayerCount = 0;
- for (int i = 0; i < length; i++) {
- int newStarts = startCounts[i];
- int newEnds = endCounts[i];
- intersectCount += newStarts * currentLayerCount + (newStarts * (newStarts - 1)) / 2;
- currentLayerCount = currentLayerCount + newStarts - newEnds;
- // short circuit return
- if(intersectCount > 10000000) {
- return -1;
- }
- }
- return intersectCount;
- }
- public void printAll(int[] numbers) {
- int length = numbers.length;
- for (int i = 0; i < length; i++) {
- System.out.println(numbers[i]);
- }
- System.out.println("");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement