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

Best approachTime O(n)Space O(n)

In Java, equals() and hashCode() must agree: equal objects need equal hash codes. Without them a HashSet treats two equal points as different.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * 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)
  1. What happens if you write equals() but forget hashCode()?