Box ‘o Numbers

Arrange the numbers 1 to 8 in the grid below such that adjacent numbers are not in adjacent boxes (horizontally, vertically, or diagonally):

       ___
      | 1 |
  =============
  | 6 | 4 | 3 |
  =============
  | 2 | 7 | 5 |
  =============
      | 8 |
      =====

The arrangement above, for example, is wrong because 3 & 4, 4 & 5, 6 & 7, and 7 & 8 are adjacent.

Solution

The key is putting the 1 & 8 in the center spots – which is required, because those spots both border all but one of the other spots, and 1 & 8 are the only numbers that are only adjacent to one number.

From there, the 2 & 7 are forced, then you have your choice of the next number, which then forces the rest. Really, though there are only two valid solutions, and they are mirror images of each other.

2026 Update: Number Box Puzzles — Matrix Operations and Latin Squares

Box-of-numbers puzzles (fill a grid with numbers satisfying constraints) generalize to Latin squares, magic squares, and Sudoku — all constraint satisfaction problems at their core.

def is_magic_square(grid: list) -> bool:
    """
    Check if n×n grid is a magic square.
    All rows, columns, and both diagonals sum to same value.
    """
    n = len(grid)
    target = n * (n * n + 1) // 2  # Magic constant for 1..n^2

    # Check all rows
    for row in grid:
        if sum(row) != target:
            return False

    # Check all columns
    for col in range(n):
        if sum(grid[row][col] for row in range(n)) != target:
            return False

    # Check main diagonal
    if sum(grid[i][i] for i in range(n)) != target:
        return False

    # Check anti-diagonal
    if sum(grid[i][n-1-i] for i in range(n)) != target:
        return False

    return True

def generate_magic_square_odd(n: int) -> list:
    """
    Siamese method for odd-sized magic squares.
    Places 1..n^2 using step pattern.
    """
    assert n % 2 == 1, "Siamese method only works for odd n"
    grid = [[0] * n for _ in range(n)]
    row, col = 0, n // 2

    for num in range(1, n * n + 1):
        grid[row][col] = num
        new_row = (row - 1) % n
        new_col = (col + 1) % n
        if grid[new_row][new_col]:  # Cell occupied
            row = (row + 1) % n
        else:
            row, col = new_row, new_col

    return grid

# Generate and verify 3×3 magic square
magic3 = generate_magic_square_odd(3)
print("3×3 Magic Square:")
for row in magic3:
    print(f"  {row}")
print(f"Is magic: {is_magic_square(magic3)}")
print(f"Magic constant: {3 * (9 + 1) // 2}")  # 15

# Latin square check
def is_latin_square(grid: list) -> bool:
    """Each row and column contains each symbol exactly once."""
    n = len(grid)
    symbols = set(range(1, n + 1))
    for row in grid:
        if set(row) != symbols:
            return False
    for col in range(n):
        if set(grid[row][col] for row in range(n)) != symbols:
            return False
    return True

# Sudoku is a 9×9 Latin square with additional box constraints
latin = [
    [1, 2, 3],
    [3, 1, 2],
    [2, 3, 1],
]
print(f"nLatin square valid: {is_latin_square(latin)}")

Interview connection: Magic square construction (Siamese method) is a beautiful example of an algorithm that works by invariant — the “up-right” step pattern guarantees all numbers 1..n² are placed without collision. Latin squares underlie Sudoku, experimental design (balanced incomplete block designs), and error-correcting codes. The constraint that each symbol appears exactly once in each row/column is a key structure in database normalization (functional dependencies).

function maxSubarraySum(nums) {
    if (nums.length === 0) return 0;

    let maxEndingHere = nums[0];
    let maxSoFar = nums[0];

    for (let i = 1; i < nums.length; i++) {
        // Either extend current subarray or start new one
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

// Tests
console.log(maxSubarraySum([-2, 1, -3, 4, -1, 2, 1, -5, 4]));  // 6 ([4,-1,2,1])
console.log(maxSubarraySum([1, 2, 3, 4]));                     // 10
console.log(maxSubarraySum([-1, -2, -3]));                     // -1

function productExceptSelf(nums) {
    const n = nums.length;
    const output = Array(n).fill(1);

    // Calculate prefix products
    let prefix = 1;
    for (let i = 0; i < n; i++) {
        output[i] = prefix;
        prefix *= nums[i];
    }

    // Calculate suffix products and multiply
    let suffix = 1;
    for (let i = n - 1; i >= 0; i--) {
        output[i] *= suffix;
        suffix *= nums[i];
    }

    return output;
}

// Tests
console.log(productExceptSelf([1, 2, 3, 4]));     // [24, 12, 8, 6]
console.log(productExceptSelf([2, 3, 4, 5]));     // [60, 40, 30, 24]
console.log(productExceptSelf([1, 0, 3, 4]));     // [0, 12, 0, 0]

function equilibriumIndex(nums) {
    const totalSum = nums.reduce((sum, num) => sum + num, 0);
    let leftSum = 0;

    for (let i = 0; i < nums.length; i++) {
        // Check if left sum equals right sum
        // Right sum = totalSum - leftSum - nums[i]
        if (leftSum === totalSum - leftSum - nums[i]) {
            return i;
        }

        leftSum += nums[i];
    }

    return -1;  // No equilibrium found
}

// Tests
console.log(equilibriumIndex([-7, 1, 5, 2, -4, 3, 0]));  // 3 (left: -1, right: -1)
console.log(equilibriumIndex([1, 2, 3]));                 // -1
console.log(equilibriumIndex([1, 3, 5, 2, 2]));           // 2

function findPairWithSum(nums, target) {
    const seen = new Set();

    for (const num of nums) {
        if (seen.has(target - num)) {
            return [target - num, num];
        }
        seen.add(num);
    }

    return null;
}

console.log(findPairWithSum([1, 2, 3, 4, 5], 7));  // [3, 4] or [2, 5]

function maxProductSubarray(nums) {
    if (nums.length === 0) return 0;

    let maxSoFar = nums[0];
    let minSoFar = nums[0];  // Track min for negative numbers
    let result = nums[0];

    for (let i = 1; i < nums.length; i++) {
        const num = nums[i];

        // If negative, swap max and min
        if (num < 0) {
            [maxSoFar, minSoFar] = [minSoFar, maxSoFar];
        }

        maxSoFar = Math.max(num, maxSoFar * num);
        minSoFar = Math.min(num, minSoFar * num);

        result = Math.max(result, maxSoFar);
    }

    return result;
}

console.log(maxProductSubarray([2, 3, -2, 4]));     // 6 ([2,3])
console.log(maxProductSubarray([-2, 0, -1]));       // 0
console.log(maxProductSubarray([-2, 3, -4]));       // 24 (all)