## Shashank Sharma

BAN USER
Comments (3)

Reputation 0

Page:

1

Comment hidden because of low score. Click to expand.

Comment hidden because of low score. Click to expand.

0

of 0 vote

Here's a C++ solution that works in O(n^2) time.

- Inputs are in the form for vector of pairs of points (x,y)

- All points are first stored in a hash map

- Now take one point(p1) from the list of points and look a point(p2) that can potentially be the diagonally opposite corner of a rectangle. It(p2) should have both coordinates different from the point in consideration(p1).

- Once we have a pair of diagonally opposite points(p1 & p2), we can look for other two points(p3 & p4) completing a rectangle by looking in the hashmap the points formed by combination of p1 & p2 coordinates.

```
int getRectangles(vector<pair<int,int>>& v){
if(v.size()<=3){
return 0;
}
int numOfRectangles=0;
map<pair<int,int>,bool> m;
for(int i=0;i<v.size();i++){
m[v[i]]=true;
}
for(int i=0;i<v.size();i++){
pair<int,int> p1=v[i];
for(int j=i+!;j<v.size();j++){
pair<int,int> p2=v[j];
if((get<0>(p1) != get<0>(p2)) && (get<0>(p1) != get<0>(p2))){
pair<int,int> p3(get<0>(p1),get<1>(p2));
pair<int,int> p4(get<0>(p2),get<1>(p1));
if(m[p3] && m[p4]){
numOfRectangles++;
}
}
}
}
return numOfRectangles;
}
```

Please do provide comments on the approach.

- Shashank Sharma April 12, 2017Comment hidden because of low score. Click to expand.

0

of 0 vote

How about using long int data type in C++ ?

- Shashank Sharma March 04, 2017Page:

1

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Here's an update to your solution.

I added two loops, first one for palindromes of odd length and second loop for palindromes of even length starting at index 0 in the string. It works irrespective of the length of string input being even or odd.

- Shashank Sharma April 30, 2017