Count distinct colors within a bounding rectangle

Question

I implemented a program that does the following:

Consider the positive quadrant of the xy plane. A colored point is a triple (x,y,c) where x is its x-axis coordinate, y is the y-axis coordinate, and c is an integer representing its color.

This program needs to read a set of N colored points, then take some queries and answer them.

A query is represented by four values, (x₁, y₁, x₂, y₂) and is used to get the number of different colors inside the rectangle confined within the two points of given coordinates.

This program will read:

1. The number N of colored points and M of queries
2. N lines, each containing the three numbers that identify a colored point
3. M lines, each containing a query

It will only output the answers to each query. That is the number of distinct colors within the rectangles.

NOTE

• This code does not perform input-checks. Don't tell me it doesn't. I know. This exercise was not about input-checking. It also doesn't print any messages to the user. This program is to be tested automatically by my university online platform, so it has to strictly get input from stdin print the output. Also please don't comment on usage of scanf() and printf(); I know there are better options but that's not the point.

That being said, I feel that complexity-wise, this algorithm isn't very efficient, or at least could be done better. I haven't done a thorough analysis of it, but the complexity is at least O(NM), which is potentially very very bad. I'm interested in constructive feedback on how I could improve the algorithm to make it faster and do fewer tests.

Here's the code:

#include <stdio.h>
#include <stdlib.h>

typedef struct colpt {
    int x;
    int y;
    int c;
} Cp;

typedef struct q {
    int x1;
    int x2;
    int y1;
    int y2;
} Query;

typedef struct color {
    int c;
    struct color *nextPtr;
} Color;

void freeList(Color **lPtr) {
    Color *currPtr = *lPtr;

    while(currPtr != NULL) {
        Color *tempPtr = currPtr;
        currPtr = currPtr->nextPtr;
        free(tempPtr);
    }
}

Color *newNode(int color) {
    Color *newPtr = malloc(sizeof(Color));
    if(newPtr == NULL) exit(EXIT_FAILURE);

    newPtr->c = color;
    newPtr->nextPtr = NULL;
    return newPtr;
}

int insertAndIncrease(Color **lPtr, int thiscolor) {
    Color *currPtr = *lPtr;
    Color *prevPtr = NULL;

    if(currPtr == NULL) { // list is empty, add current color and return 1
        *lPtr = newNode(thiscolor);
        return 1;
    }

    while(currPtr != NULL && currPtr->c != thiscolor) {
        prevPtr = currPtr;
        currPtr = currPtr->nextPtr;
    }

    if(currPtr == NULL) { // found no color equal to the one passed, so it's a new color
        prevPtr->nextPtr = newNode(thiscolor);
        return 1;
    }
    return 0;
}

void processQuery(Cp *points, int npoints, Query q, int *ncolors) {
    Color *colors = NULL;

    for(size_t i = 0; i < npoints; i++) {
        if(points[i].x >= q.x1 && points[i].x <= q.x2 && points[i].y >= q.y1 && points[i].y <= q.y2) { // if check is passed, then the point is inside the rectangle
            *ncolors = *ncolors + insertAndIncrease(&colors, points[i].c);
        }
    }
    freeList(&colors);
}

void processQueries(Cp *points, int npoints, Query *queries, int nqueries) {
    for(size_t i = 0; i < nqueries; i++) {
        int thisQColors = 0;
        processQuery(points, npoints, queries[i], &thisQColors);
        printf("%d\n", thisQColors);
    }
}

int main() {
    int numPoints, numQueries;

    scanf("%d%d", &numPoints, &numQueries); // get number of colored points

    Cp *arr = malloc(sizeof(Cp) * numPoints); // allocate array of numPoints colored points
    if(arr == NULL) return EXIT_FAILURE;


    Query *queries = malloc(sizeof(Query) * numQueries); // allocate array of numQueries queries
    if(queries == NULL) return EXIT_FAILURE;


    for(size_t i = 0; i < numPoints; i++) { // fill the array
        scanf("%d%d%d", &arr[i].x, &arr[i].y, &arr[i].c);
    }

    for(size_t i = 0; i < numQueries; i++) { // get the queries
        scanf("%d%d%d%d", &queries[i].x1, &queries[i].y1, &queries[i].x2, &queries[i].y2);
    }

    processQueries(arr, numPoints, queries, numQueries);

    free(arr);
    free(queries);

    return EXIT_SUCCESS;
}

Example inputs and outputs:

INPUT
6 4
0 0 1
6 0 1
6 1 13
1 3 8
4 4 9
4 6 137000
2 2 9 7
0 0 7 7 
6 2 7 8 
0 2 5 5

OUTPUT
2
5
0
2

---

INPUT

10 30
3 16 6
11 1 12
16 3 32
7 7 25
3 14 4
3 0 13
6 15 19
1 4 50
1 10 19
11 5 35
7 10 16 14
2 1 16 8
3 15 11 16
14 4 15 15
2 12 3 15
11 15 16 16
3 2 10 9
1 14 9 16
3 3 3 7
4 6 8 15
14 2 15 4
10 15 11 16
4 0 13 5
2 6 5 10
7 6 12 9
1 1 2 9
5 12 11 15
15 1 15 3
6 9 14 11
15 0 16 3
14 0 16 12
15 9 15 16
7 1 13 8
7 2 8 10
7 2 11 12
11 7 13 10
3 3 9 4
11 11 14 11
5 6 6 16
12 8 15 9

OUTPUT

0
4
2
0
1
0
1
3
0
2
0
0
2
0
1
1
1
0
0
1
1
0
3
1
2
0
0
0
1
0

---

INPUT

16 3
7 97 1
21 8 2
30 21 5
14 45 4
5 83 0
7 2 2
12 91 3
3 26 8
1 62 3
20 34 6
15 65 8
18 14 0
29 49 1
29 58 6
27 28 3
27 13 6
2 69 22 99
25 50 26 57
15 50 16 96

OUTPUT
3
0
1
```

Answer 1

I'm interested in constructive feedback on how I could improve the algorithm to make it faster and do less checks.

processQuery() is O(n) with

for(size_t i = 0; i < npoints; i++) {

An alternative would create a binary like tree in 2 dimensions. Not a BST, bit a quadtree. Then the searching within a rectangle could take advantage of potentially O log(n).

As with any advanced search techniques, the real advantage occurs with large n, not so much with n of OP's test code.

Answer 2

The storage of both points and queries is suboptimal - in both cases, they are plain unsorted arrays. We could use better strategies for representing one or both.

As a simple example, consider keeping points as a list of rows in ascending order, with each row being a list of points. Now, when we evaluate a query, we can quickly skip the rows that are before the bounding rectangle, and we can finish when we reach the first row that's after the rectangle. Similarly, we can stop examining a row and quickly move to the next row when we reach the horizontal bound.

Further improvements in indexing rows and columns can be made, potentially leading to a quadtree representation, as used in most serious geospatial applications.

---

Building a linked list of colours for each query involves a lot of small memory allocations, which can be a serious performance hit. We could instead count distinct colours as we read the list of points, and then use a single array of that size to note the colours found (this can even be shared amongst all the queries). We might consider keeping this array sorted (using bsearch() to find elements), though the cost/benefit trade-off to that is less clear-cut than in a case where we know we have many times more lookups than insertions.

---

We're gaining nothing by reading all queries into an array and then executing them sequentially. We could just execute each query immediately after we read it.