Shashank Sharma
BAN USERHere'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, 2017How about using long int data type in C++ ?
- Shashank Sharma March 04, 2017
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