Determine Color of a Chessboard Square
EasyPrompt
You are given coordinates, a string that represents the coordinates of a square of the chessboard. Below is a chessboard for your reference.
Return true if the square is white, and false if the square is black.
The coordinate will always represent a valid chessboard square. The coordinate will always have the letter first, and the number second.
Example 1:
Input: coordinates = "a1"
Output: false
Explanation: From the chessboard above, the square with coordinates "a1" is black, so return false.Example 2:
Input: coordinates = "h3"
Output: true
Explanation: From the chessboard above, the square with coordinates "h3" is white, so return true.Example 3:
Input: coordinates = "c7"
Output: false
Constraints:
coordinates.length == 2'a' <= coordinates[0] <= 'h''1' <= coordinates[1] <= '8'
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves pre-defining the color of each square on the chessboard and storing it in a data structure like a 2D array. When given a coordinate, we parse it to determine the row and column index and then simply look up the pre-computed color from our data structure.
Algorithm
- Create an 8x8 2D boolean array
isWhite. - Populate the
isWhitearray. For each cell(i, j), setisWhite[i][j]totrueif(i + j)is odd, andfalseotherwise. - Parse the input
coordinatesstring. - Convert the file character to a column index:
col = coordinates.charAt(0) - 'a'. - Convert the rank character to a row index:
row = coordinates.charAt(1) - '1'. - Return the value at
isWhite[row][col].
Walkthrough
We can represent the chessboard as an 8x8 2D boolean array, say isWhite[8][8]. We would initialize this array based on the chessboard pattern. For example, isWhite[0][0] (for "a1") would be false, isWhite[0][1] (for "b1") would be true, and so on. The input coordinates string is parsed. The first character determines the column index, and the second character determines the row index. The column index can be calculated as col = coordinates.charAt(0) - 'a', and the row index as row = coordinates.charAt(1) - '1'. The result is then retrieved directly from isWhite[row][col]. While this approach works and has a constant time complexity for the lookup, it requires significant setup and memory to store the entire board state.
class Solution { private static final boolean[][] isWhite = new boolean[8][8]; static { for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { // If (i+j) is odd, it's white. if ((i + j) % 2 != 0) { isWhite[i][j] = true; } else { isWhite[i][j] = false; } } } } public boolean squareIsWhite(String coordinates) { int col = coordinates.charAt(0) - 'a'; int row = coordinates.charAt(1) - '1'; return isWhite[row][col]; }}Complexity
Time
O(1). The lookup operation is constant time. The initialization happens once and can be considered a pre-computation step.
Space
O(1). We use a fixed-size 8x8 array, which requires 64 booleans of storage. This is constant space, but it's more space than other approaches that don't require auxiliary data structures.
Trade-offs
Pros
Simple lookup logic.
Constant time complexity for the lookup itself.
Cons
Requires extra memory (64 booleans) compared to other approaches.
Verbose to set up the lookup table.
Less flexible if the board size were to change.
A more elegant solution observes the mathematical pattern of the chessboard. By converting the algebraic coordinates (e.g., 'a', '1') into numerical indices (e.g., 0, 0), we can determine the color based on the parity of the sum of these indices.
Algorithm
- Extract the file character from
coordinatesat index 0. - Extract the rank character from
coordinatesat index 1. - Convert the file character to a 0-indexed column number:
col = file - 'a'. - Convert the rank character to a 0-indexed row number:
row = rank - '1'. - Calculate the sum of the indices:
sum = col + row. - Check if the
sumis odd. If it is, the square is white (true). Otherwise, it's black (false). This is equivalent tosum % 2 != 0.
Walkthrough
On a standard chessboard, the color of a square depends on its row and column. If we assign 0-indexed numerical values to both rows and columns, we find a consistent pattern. Let's map the files 'a' through 'h' to columns 0 through 7. This can be done by col = coordinates.charAt(0) - 'a'. Similarly, let's map the ranks '1' through '8' to rows 0 through 7, via row = coordinates.charAt(1) - '1'. The square 'a1' (indices 0, 0) is black, and the sum of its indices is 0 + 0 = 0 (even). The square 'a2' (indices 0, 1) is white, and the sum is 0 + 1 = 1 (odd). The pattern is: if the sum of the 0-indexed row and column is odd, the square is white. If the sum is even, the square is black. Therefore, the function can simply return (row + col) % 2 != 0.
class Solution { public boolean squareIsWhite(String coordinates) { // 'a' -> 0, 'b' -> 1, etc. int col = coordinates.charAt(0) - 'a'; // '1' -> 0, '2' -> 1, etc. int row = coordinates.charAt(1) - '1'; // If the sum of 0-indexed coordinates is odd, the square is white. // e.g., a1 -> (0,0) -> sum=0 (even) -> black // e.g., h3 -> (7,2) -> sum=9 (odd) -> white return (col + row) % 2 != 0; }}Complexity
Time
O(1). The process involves a few character accesses, subtractions, an addition, and a modulo operation, all of which are constant time operations.
Space
O(1). No extra space is used besides a few variables to store the intermediate results.
Trade-offs
Pros
No extra memory required.
The logic is clear and directly models the chessboard's structure.
More efficient than a lookup table in terms of memory and setup.
Cons
Involves slightly more arithmetic than the most optimal approach.
This is the most efficient approach, building upon the mathematical pattern but simplifying the calculation. Instead of converting characters to 0-indexed coordinates, we can directly use the parity of the ASCII values of the coordinate characters.
Algorithm
- Get the file character
c1 = coordinates.charAt(0). - Get the rank character
c2 = coordinates.charAt(1). - Check if the parity of the ASCII value of
c1is different from the parity of the ASCII value ofc2. - If
(c1 % 2) != (c2 % 2), returntrue(white). - Otherwise, return
false(black).
Walkthrough
This approach optimizes the mathematical logic. We know a square is white if (col_index + row_index) is odd, where col_index = coordinates.charAt(0) - 'a' and row_index = coordinates.charAt(1) - '1'. Let c1 = coordinates.charAt(0) and c2 = coordinates.charAt(1). We are checking the parity of (c1 - 'a') + (c2 - '1'). This is equivalent to checking the parity of c1 + c2 - 'a' - '1'. The ASCII sum 'a' + '1' is 97 + 49 = 146, which is an even number. So, we are checking the parity of (c1 + c2 - even_number). This has the same parity as (c1 + c2). A sum of two integers c1 + c2 is odd if and only if one integer is odd and the other is even. This is true if and only if their parities are different, i.e., c1 % 2 != c2 % 2. This check is computationally simpler as it avoids subtraction operations.
class Solution { public boolean squareIsWhite(String coordinates) { // A square is white if the sum of its 0-indexed coordinates is odd. // Let c1 = coordinates.charAt(0) and c2 = coordinates.charAt(1). // We check if (c1 - 'a' + c2 - '1') % 2 != 0. // This is equivalent to (c1 + c2 - ('a' + '1')) % 2 != 0. // 'a' + '1' = 97 + 49 = 146 (even). // So we check if (c1 + c2 - even) % 2 != 0, which is (c1 + c2) % 2 != 0. // The sum of two numbers is odd iff their parities are different. // Thus, we check if c1 % 2 != c2 % 2. return coordinates.charAt(0) % 2 != coordinates.charAt(1) % 2; }}Complexity
Time
O(1). This is the most efficient constant time solution, involving only two character reads, two modulo operations, and one comparison.
Space
O(1). No auxiliary space is required.
Trade-offs
Pros
Most computationally efficient due to minimal arithmetic operations.
Extremely concise and elegant code.
No extra memory usage.
Cons
The logic might be less intuitive at first glance compared to the direct coordinate sum approach.
Solutions
Solution
class Solution { public boolean squareIsWhite ( String coordinates ) { return ( coordinates . charAt ( 0 ) + coordinates . charAt ( 1 )) % 2 == 1 ; } }/** * @param {string} coordinates * @return {boolean} */ var squareIsWhite = function (coordinates) { const x = coordinates.charAt(0).charCodeAt(); const y = coordinates.charAt(1).charCodeAt(); return (x + y) % 2 == 1; };class Solution { public: bool squareIsWhite ( string coordinates ) { return ( coordinates [ 0 ] + coordinates [ 1 ]) % 2 ; } };class Solution : def squareIsWhite ( self , coordinates : str ) -> bool : return ( ord ( coordinates [ 0 ]) + ord ( coordinates [ 1 ])) % 2 == 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.