# Determine Color of a Chessboard Square **Difficulty:** EASY [External](https://leetcode.com/problems/determine-color-of-a-chessboard-square) Canonical: https://scaleengineer.com/dsa/problems/determine-color-of-a-chessboard-square **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math) **Data structures:** String **Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan) --- ## Problem You are given `coordinates`, a string that represents the coordinates of a square of the chessboard. Below is a chessboard for your reference. ![](https://assets.glich.co/dsa/determine-color-of-a-chessboard-square/image0.png) 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 ## Brute-Force using a Lookup Table 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. **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. **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. ### Explanation 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. ```java 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]; } } ``` ### Algorithm 1. Create an 8x8 2D boolean array `isWhite`. 2. Populate the `isWhite` array. For each cell `(i, j)`, set `isWhite[i][j]` to `true` if `(i + j)` is odd, and `false` otherwise. 3. Parse the input `coordinates` string. 4. Convert the file character to a column index: `col = coordinates.charAt(0) - 'a'`. 5. Convert the rank character to a row index: `row = coordinates.charAt(1) - '1'`. 6. Return the value at `isWhite[row][col]`. ## Mathematical Approach using Coordinate Sum 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. **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. **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. ### Explanation 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`. ```java 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; } } ``` ### Algorithm 1. Extract the file character from `coordinates` at index 0. 2. Extract the rank character from `coordinates` at index 1. 3. Convert the file character to a 0-indexed column number: `col = file - 'a'`. 4. Convert the rank character to a 0-indexed row number: `row = rank - '1'`. 5. Calculate the sum of the indices: `sum = col + row`. 6. Check if the `sum` is odd. If it is, the square is white (`true`). Otherwise, it's black (`false`). This is equivalent to `sum % 2 != 0`. ## Optimized Mathematical Approach using ASCII Value Parity 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. **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. **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. ### Explanation 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. ```java 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; } } ``` ### Algorithm 1. Get the file character `c1 = coordinates.charAt(0)`. 2. Get the rank character `c2 = coordinates.charAt(1)`. 3. Check if the parity of the ASCII value of `c1` is different from the parity of the ASCII value of `c2`. 4. If `(c1 % 2) != (c2 % 2)`, return `true` (white). 5. Otherwise, return `false` (black). # Solutions ### Java ```java class Solution { public boolean squareIsWhite ( String coordinates ) { return ( coordinates . charAt ( 0 ) + coordinates . charAt ( 1 )) % 2 == 1 ; } } ``` ### JavaScript ```javascript /** * @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; }; ``` ### CPP ```cpp class Solution { public: bool squareIsWhite ( string coordinates ) { return ( coordinates [ 0 ] + coordinates [ 1 ]) % 2 ; } }; ``` ### Python ```python class Solution : def squareIsWhite ( self , coordinates : str ) -> bool : return ( ord ( coordinates [ 0 ]) + ord ( coordinates [ 1 ])) % 2 == 1 ```