Represent points using offsets - FULL explanation with example
Idea:\n\n\n\n Consider above mentioned 3 rectangles. As you can see, rectangles contains 12, 9, 15 integer coordinates respectively.\n So, in total, we have 36 
**Idea:**\n\n![image](https://assets.leetcode.com/users/images/673d8a56-c13f-47d1-ad63-dd2a7c3b9c35_1598084206.445497.png)\n\n* Consider above mentioned 3 rectangles. As you can see, rectangles contains `12, 9, 15` integer coordinates respectively.\n* So, in total, we have 36 points to represent. We can represent them using indices `[0 ... 35]`. Let\'s call them `pointId`\n* Let\'s make an array `offset` which mentions the starting of `pointIdx` that a particular rectangle contains. For example,\n\t* Rectangle 1 will contain pointId `0 to 11 (12 points in total),`, so `offset[0] = 0` (starting value of pointId for rectangle-1)\n\t* Rectangle 2 will contain pointId `12 to 20 (9 points in total)`, so `offset[1] = 12` (starting value of pointId for rectangle-2)\n\t* Rectangle 3 will contains pointId `21 to 35 (36 points in total)`, so `offset[2] = 21` (starting value of pointId for rectangle-3)\n\t* Hence, the `offset = [0, 12, 21]`\n* Now, you can randomly select a pointId from `0` (inclusive) to `36` (exclusive).\n* As you can see, `offset` is in increasing order, so we can perform binary search to find the right position of random pointId, which is basically the rectangle it belongs to.\n* For example, let\'s say random pointId is `20`, we can determine using binary search on `offset`, that it belongs to rectangle-2 (which has pointIds of range `12` to `20`)\n* Now, take the start coordinates of rectangle-2 (using given grid), and determine the `8`th coordinate in that rectangle-2 (because 20 - 12 = 8).\n\n```\nclass Solution {\n\n    int[][] rects;\n    int[] offsets;\n    int range;\n    Random r;\n    public Solution(int[][] rects) {\n        this.rects = rects;\n        this.offsets = new int[rects.length];\n        this.range = 0;\n        r = new Random();\n        \n        for (int i = 0; i < rects.length; i++) {\n            int[] rect = rects[i];\n            \n            int x1 = rect[0],\n                y1 = rect[1],\n                x2 = rect[2],\n                y2 = rect[3];\n            \n            offsets[i] = range;\n            range += (x2 - x1 + 1) * (y2 - y1 + 1);\n        }\n        \n    }\n    \n    public int[] pick() {\n        int randIdx = r.nextInt(range), \n            rectIdx = Arrays.binarySearch(offsets, randIdx); \n        \n        if (rectIdx < 0) {\n            rectIdx = Math.abs(rectIdx + 2);\n        }\n        \n        int[] rect = rects[rectIdx];\n        \n        int idx = randIdx - offsets[rectIdx], \n            x = rect[0], \n            y = rect[1],\n            width = rect[2] - rect[0] + 1, \n            height = rect[3] - rect[1] + 1, \n            row = idx / width, \n            col = idx % width; \n        \n        return new int[]{x + col, y + row};   \n    }\n}\n```\n
[]