Posts Count Right Triangles
Post
Cancel

Count Right Triangles

Problem Description

Given two arrays of integers A and B of size N each, where each pair (A[i], B[i]) for 0 <= i < N represents a unique point (x, y) in 2D Cartesian plane.

Find and return the number of unordered triplets (i, j, k) such that (A[i], B[i]), (A[j], B[j]) and (A[k], B[k]) form a right-angled triangle with the triangle having one side parallel to the x-axis and one side parallel to the y-axis.

NOTE: The answer may be large so return the answer modulo (109 + 7).

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {

    int m = 1000000007;

    public int solve(int[] A, int[] B) {

        Map<Integer, Integer> setx = new HashMap<>();
        Map<Integer, Integer> sety = new HashMap<>();

        for(int i=0; i<A.length; i++){
            if(setx.containsKey(A[i])){
                setx.put(A[i], setx.get(A[i])+1);
            }else{
                setx.put(A[i], 1);
            }
        }

        for(int i=0; i<B.length; i++){
            if(sety.containsKey(B[i])){
                sety.put(B[i], sety.get(B[i])+1);
            }else{
                sety.put(B[i], 1);
            }
        }

        long total = 0;

        for(int i=0; i<A.length; i++){
            int x = A[i];
            int y = B[i];
            int countX = setx.get(x) - 1;
            int countY = sety.get(y) - 1;
            total = (total%m + (countX%m * countY%m)%m)%m;
        }

        return (int)total%m;

    }
}
This post is licensed under CC BY 4.0 by the author.