Count Unique Points (equals and hashCode)
Problem
Each input line has two integers x and y: a point. Print how many different points there are. Two points are the same when both x and y are the same. Write a Point class with correct equality.
Constraints
- 1 <= lines <= 10^5
Examples
Input
1 2 1 2 3 4
Output
2
Solutions
In Java, equals() and hashCode() must agree: equal objects need equal hash codes. Without them a HashSet treats two equal points as different.
/*
* Problem : Count unique points.
* Input : Lines of x y.
* Output : The count.
* Approach: Point class with equality.
* Time : O(n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// Step 1: Two points are equal when x and y are equal. So we write equals() and hashCode() together.
static final class Point {
private final int x;
private final int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object other) {
if (this == other) {
return true;
}
if (!(other instanceof Point)) {
return false;
}
Point point = (Point) other;
return x == point.x && y == point.y;
}
// Step 2: Equal points must give the same hash code. Otherwise a HashSet cannot find them.
@Override
public int hashCode() {
return 31 * x + y;
}
}
// This method solves the task. It receives the input and returns the answer.
static int solve(String[] lines) {
// Step 3: A HashSet uses hashCode() to find a bucket and equals() to compare. Equal points are stored once.
java.util.Set<Point> points = new java.util.HashSet<>();
for (String line : lines) {
String[] parts = line.split(" ");
points.add(new Point(Integer.parseInt(parts[0]), Integer.parseInt(parts[1])));
}
return points.size();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
java.util.List<String> all = new java.util.ArrayList<>();
while (scanner.hasNextLine()) {
String line = scanner.nextLine().trim();
if (!line.isEmpty()) {
all.add(line);
}
}
String[] lines = all.toArray(new String[0]);
System.out.println(solve(lines));
}
}
Hints (1)
- What happens if you write equals() but forget hashCode()?