CareerCup

I am not sure if the approach mentioned above is the right way to solve the problem. Please help with any better solutions.

If all ages are in parallel to one of the axises they do not form any squares.

As per my understanding of the question:

You can have two sets of edges, s1 parallel to the x-axis and s2 parallel to the y-axis.

For each edge in s1:
1. edge = (x1, y1) (x2, y1)
len = abs(x2 - x1)
2. check if [(x1, y1 + len), (x2, y1 + len)] [(x1, y1), (x2, y1 + len)] [(x2, y1), (x2, y1 + len)] are valid edges increment totalEdges (add square to set)
3. check if [(x1, y1 - len), (x2, y1 - len)] [(x1, y1), (x2, y1 - len)] [(x2, y1), (x2, y1 - len)] are valid edges increment totalEdges (add square to set)

In 2 and 3 you can take the top left and bottom right points to mark the square and add to a set to avoid duplicates or sort the edges parallel to x-axis by ordinates and just check for edges below the current edge to form a square.

As per my understanding:
1. Maintain a set with edges parallel to the x-axis.
2. For each edge say (x1, y1) (x2, y1):
len = x2 - x1
i. Check if [(x1, y1), (x1 + len, y1)], [(x2, y1),(x2 + len, y1)] and [(x1 + len, y1), (x2 + len, y1)] are valid edges, if so add the square to a set.
ii. Check if [(x1, y1), (x1 - len, y1)], [(x2, y1),(x2 - len, y1)] and [(x1 - len, y1), (x2 - len, y1)] are valid edges, if so add the square to a set.

Instead of checking above and below the edge for valid square, sort the edges parallel to x-axis by ordinates and just check below.

Write functions that given if we assume a segment is on the left will return the top right and bottom segments
If the segment is vertical that is x1 == x2 y1 < y2 and if it is horizontal x1 < x2 y1 == y2
Take all the lines you have and sort then interlay so that this constraint holds
So if you had a vertical segment were x1 == x2 y1 > y2 was true swap y1 and y2 similarly for the horizontal segments.
Now build a hash table of all your segments. All 4 coordinates need to be used to compute the key. C++ STL unordered set will do this for you but if you had some other language you might just append the bytes in the 4 numbers to make the keys.
Now loop through all your segments
If a segment is vertical search the hash table for the top left and right segments that would make up a square
Increment the count if you find all 3 of them.
This will take O(n) time and O(n) additional space for the table.
If you cannot afford extra space for the table but can rearrange the initial list you can sort it by these keys in O(nlog(n)) time spend O(log(n)) on the O(n) searchers you will need to do.
If you cannot mess up the table then you will need to do O(n) O(n) searches -> (n^2)
If you can have corners where segments cross in the middle, you will either need to compute intersections and create a lot of new overlapping segments of different lengths and use the above algorithm or render each line onto in binary array representing the absence of 1 block long segments that are horizontal and one where they are vertical. In this latter case you will need to scan these arrays for progressively larger emergent squares.

I feel like this problem boils down to finding the sum of all possible square matrices in NxN square matrix

private static int bigSquare(Point []points) {
        ArrayList<Point> starting = new ArrayList<>();
        ArrayList<Point> ending = new ArrayList<>();

        for( int i = 0 ; i < points.length ; ++i ) {
            if( i % 2 == 0 )
                starting.add( points[i] );
            else
                ending.add( points[i] );
        }

        Collections.sort( starting, (a, b)-> a.x == b.x ? a.y - b.y : a.x - b.x );
        Collections.sort( ending, (a, b)-> a.x == b.x ? a.y - b.y : a.x - b.x );

        int s = 0, e = ending.size()-1;
        int cnt=0;
        while (s < e) {
            if( starting.get(s).x - ending.get(e).x == starting.get(s).y - ending.get(e).y ) {
                if( starting.get(e).x == ending.get(e).x &&
                    starting.get(e).y == starting.get(s).y &&
                    ending.get(s).x == starting.get(s).x &&
                    ending.get(s).y == ending.get(e).y
                ) {
                    ++cnt;
                }
            }
            ++s;
            --e;
        }
        return cnt;
    }

private static int bigSquare(Point []points) {
        ArrayList<Point> starting = new ArrayList<>();
        ArrayList<Point> ending = new ArrayList<>();

        for( int i = 0 ; i < points.length ; ++i ) {
            if( i % 2 == 0 )
                starting.add( points[i] );
            else
                ending.add( points[i] );
        }

        Collections.sort( starting, (a, b)-> a.x == b.x ? a.y - b.y : a.x - b.x );
        Collections.sort( ending, (a, b)-> a.x == b.x ? a.y - b.y : a.x - b.x );

        int s = 0, e = ending.size()-1;
        int cnt=0;
        while (s < e) {
            if( starting.get(s).x - ending.get(e).x == starting.get(s).y - ending.get(e).y ) {
                if( starting.get(e).x == ending.get(e).x &&
                    starting.get(e).y == starting.get(s).y &&
                    ending.get(s).x == starting.get(s).x &&
                    ending.get(s).y == ending.get(e).y
                ) {
                    ++cnt;
                }
            }
            ++s;
            --e;
        }
        return cnt;
    }