Point in non-overlapping rectangles [C] (Not recommended in C)
IntuitionMy first idea was to parse all the points from each rectangle and put them in the Solution struct such that each "pick" call is effectively just O(1) w
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
My first idea was to parse all the points from each rectangle and put them in the Solution struct such that each "pick" call is effectively just O(1) with the random number selection on size; the problem with that is the worst case could make my Solution struct balloon to $$2*(10pow10) * sizeof(int)$$:
One rectangle of -MAX_INT to +MAX_INT would be about... 2(x,y point values) * 32(int bits) * 2^30(all points)... for memory.

I didn't want to do that, so I looked around for other ideas. One way is to select a rectangle based of of its area as a proportion of the total area of all rectangles together. Example like this:

rectangle1 [0,3] -> [2,5]: area = $$((2-0)+1) * ((5-3)+1) = 9$$
rectangle2 [-4,-3] -> [0,1]: area = $$((0-(-4))+1) * ((1-(-3))+1) = 5 * 4 = 20$$

The total area is 29 (29 points to choose from); if I randomly select a number 0 to 28, I can select a point within one of those by checking "is the number i chose greater than the current rectangle area?": if yes, move to the next one and subtract so I don't go out of the bound of "indexes".

# Approach
<!-- Describe your approach to solving the problem. -->
Copy over the rectangles and calculate their area into the solution struct. This should contain the size for "how many rectangles", and each rectangle array should have the points that define it and the area.

As I calculate the area of rectangles, I add to a "total area" field on Solution to index out of.

Pick will run through the rectangles checking for the area to select from and use a random index in the appropriate range (lowest to highest on x/y ranges).

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(r) for the initial rectangle parsing,
O(r) for the picking.
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(r), I have ints on Solution for capacity of rectangles, size, and total area (O(1)), pointers to arrays of rectangles (O(128) defined capacity with O(r) non-null pointers initialized), and the array of rectangles have 5 ints (a,b,x,y,area);
# Code
```c []
#include <stdlib.h>

#define RECTANGLES_CAP 128

typedef struct {
  int** rects; 
  int size;
  long int totalArea;
  int capacity; //count of pointers to rectangles
} Solution;


Solution* solutionCreate(int** rects, int rectsSize, int* rectsColSize) {
  //rectangle pointers for storing on Solution
  int** rectPoints = malloc(RECTANGLES_CAP * sizeof(int*));
  for (int c = 0; c < RECTANGLES_CAP; c++) {
    rectPoints[c] = NULL;
  }
  //init memory for it
  Solution* sol = malloc(sizeof(Solution));
  sol->rects = rectPoints;
  sol->capacity = RECTANGLES_CAP;
  sol->size = 0;
  sol->totalArea = 0;

  //pass first time is to parse the rectangle for their points and create a growing vector of space...
  for (int i = 0; i < rectsSize; i++) {
    //allocate the array of rectangles:
    //I will allocate the rectangle with its area (int size X rectangles);
    int *rect = calloc(5, sizeof(int));
    //calculate the area
    int *thisRect = rects[i];
    if (rectsColSize[i] >= 4) {
      memcpy(rect, thisRect, 4 * sizeof(int));
      //last index will be area:

      //length/width is end to end, inclusive (+1)
      int len = thisRect[2] - thisRect[0] + 1;
      int wid = thisRect[3] - thisRect[1] + 1;
      int area = len * wid;
      rect[4] = area;
      sol->totalArea += area;
      //could use i for index since it should basically match as I increase size, but this is also fine
      sol->rects[sol->size] = rect;
      sol->size++;
      printf("Rectangle Added: area=%ld; points=[%d,%d]->[%d,%d]\n",
              rect[4], rect[0], rect[1], rect[2], rect[3]);
    }
  }

  printf("Solution created: totArea=%ld\n", sol->totalArea);
  //random number generator: I don't need to...

  return sol;
    
}

int* solutionPick(Solution* obj, int* retSize) {
  //return array
  int* pick = NULL;

  //I have rectangles, not wasting memory space on (10^10 x 2)int points
  //how do I select space? do by area of rectangles (first rectangle a1, )

  //get a random int between 0 and total area; when I reach 0, that's the rectangle I use.
  long int areaSelect = rand() % obj->totalArea;
  printf("areaSelect = %ld\n", areaSelect);

  //loop through rectangle pointers checking if the area is less, then select a point within the rectangle
  int* rectangle = NULL;
  for (int i = 0; i < obj->size; i++) {
    rectangle = obj->rects[i];
    //do i have a proper pointer?
    if (rectangle) {
      //I'm making an assumption on the length because I created the array:
      //array size should be in idx=4
      int area = rectangle[4];
      //not in this rectangle if we have more area to traverse
      if (areaSelect >= area) {
        areaSelect -= area;
        continue;
      }

      //this rectangle, just break and do the "point finding" outside
      break;
    } else {
      //if I have a null rectangle, i shouldn't bother continuing;
      break;
    }
  }

  if (!rectangle) {
    return NULL;
  }

  //I have successful pick, can use the remaining part of area select to choose a point within the rectangle area
  int len = rectangle[2] - rectangle[0] + 1;
  int wid = rectangle[3] - rectangle[1] + 1;
  
  pick = calloc(2, sizeof(int));

  //index the length first:
  pick[0] = rectangle[0] + (rand() % len);
  pick[1] = rectangle[1] + (rand() % wid);
  *retSize = 2;

  return pick;
}

void solutionFree(Solution* obj) {
  for (int i = 0; i < obj->size; i++) {
    int *rect = obj->rects[i];
    if (rect) {
      free(rect);
    }
  } 
  //freed the individual rectangles, now the pointers to rects and solution container
  free(obj->rects);
  free(obj);
}

void reallocRects(Solution* solution) {
  int** rects = realloc(solution->rects, solution->capacity << 2);
  if (!rects) {
    //something went wrong
    printf("couldn't reallocate\n");
    free(rects);
    solutionFree(solution);
    exit(1);
  }
  solution->rects = rects;
}

/**
 * Your Solution struct will be instantiated and called as such:
 * Solution* obj = solutionCreate(rects, rectsSize, rectsColSize);
 * int* param_1 = solutionPick(obj, retSize);
 
 * solutionFree(obj);
*/
```
['C']