Problem

On our special chessboard, two bishops attack each other if they share the same diagonal. This includes bishops that have another bishop located between them, i.e. bishops can attack through pieces.

You are given N bishops, represented as (row, column) tuples on an M by M chessboard. Write a function to count the number of pairs of bishops that attack each other. The ordering of the pair doesn’t matter: (1, 2) is considered the same as (2, 1).

Examples

Example 1:

1
2
3
4
5
6
7
8
9

Input: M = 5, bishops =[[0,0], [1,2], [2,2,], [4,0]]
Output: 2
Explanation: Bishops 1 and 3 attack each other, as well as bishops 3 and 4.
This is how the board look with bishops:
[b 0 0 0 0]  
[0 0 b 0 0]  
[0 0 b 0 0]  
[0 0 0 0 0]  
[b 0 0 0 0]

Solution

Bishops can attack diagonally in two directions: from the top-left to the bottom-right (referred to here as positive diagonals, where i - j is constant) and from the top-right to the bottom-left (referred to here as negative diagonals, where i + j is constant).

Method 1 - Using Hashmap

This is the strategy:

  1. Identify Diagonals: We’ll use two hashmaps to track the number of bishops on each of the two types of diagonals.
  2. Count Pairs: For each diagonal, if there are k bishops, the number of pairs of bishops that attack each other on that diagonal is given by the combination formula C(k, 2) = k * (k - 1) / 2.

Here are the steps:

  1. Create two hashmaps:
    • One for the positive diagonals.
    • One for the negative diagonals.
  2. For each bishop, update the count in both hashmaps.
  3. Sum the pairs from both hashmaps using the combination formula.

Code

 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

public class BishopPairs {

	public static int countBishopPairs(int M, List < int[] > bishops) {
		Map<Integer, Integer> positiveDiagonals = new HashMap<>();
		Map<Integer, Integer> negativeDiagonals = new HashMap<>();

		// Process each bishop
		for (int[] bishop: bishops) {
			int row = bishop[0];
			int col = bishop[1];

			int posDiag = row - col;
			int negDiag = row + col;

			positiveDiagonals.put(posDiag, positiveDiagonals.getOrDefault(posDiag, 0) + 1);
			negativeDiagonals.put(negDiag, negativeDiagonals.getOrDefault(negDiag, 0) + 1);
		}

		int pairs = 0;

		// Count pairs for positive diagonals
		for (int count: positiveDiagonals.values()) {
			if (count > 1) {
				pairs += (count * (count - 1)) / 2;
			}
		}

		// Count pairs for negative diagonals
		for (int count: negativeDiagonals.values()) {
			if (count > 1) {
				pairs += (count * (count - 1)) / 2;
			}
		}

		return pairs;
	}
}
 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

from typing import List, Tuple


def count_bishop_pairs(bishops: List[Tuple[int, int]], M: int) -> int:
    positive_diagonals = {}
    negative_diagonals = {}

    for bishop in bishops:
        row, col = bishop

        pos_diag = row - col
        neg_diag = row + col

        if pos_diag in positive_diagonals:
            positive_diagonals[pos_diag] += 1
        else:
            positive_diagonals[pos_diag] = 1

        if neg_diag in negative_diagonals:
            negative_diagonals[neg_diag] += 1
        else:
            negative_diagonals[neg_diag] = 1

    def count_pairs(diagonal_dict):
        count = 0
        for bishops_on_diagonal in diagonal_dict.values():
            if bishops_on_diagonal > 1:
                count += (bishops_on_diagonal * (bishops_on_diagonal - 1)) // 2
        return count

    pairs = count_pairs(positive_diagonals) + count_pairs(negative_diagonals)
    return pairs


# Example usage
M = 5
bishops = [(0, 0), (1, 2), (2, 2), (4, 0)]
print(count_bishop_pairs(bishops, M))  # Output: 2

Complexity

  • ⏰ Time complexity: O(n + m)
    • Loop though bishops takes O(n) time
    • Looping through positive and negative diagonals take 2M - 1 time
  • 🧺 Space complexity: O(n + m)
    • For storing positive and negative diagonals take O(2M - 1) keys in map
    • For storing bishop list, it takes O(n)