algoadvance

Leetcode 3142. Check if Grid Satisfies Conditions

Problem Statement

We are given a grid of size n x n and our task is to determine if this grid satisfies the following conditions:

  1. All integers in the grid are distinct.
  2. Each integer in the grid lies in the range [1, n^2].
  3. The sum of the integers in each row is equal to the sum of the integers in each column.

Clarifying Questions

  1. Input format:
    • Is the grid guaranteed to be a square matrix?
    • What are the constraints on the value of n?
  2. Output format:
    • What should be returned if the conditions are satisfied? What should be returned if they are not?
  3. Edge cases:
    • Should we handle edge cases where n is minimum, such as n = 1?
    • Do we need to validate the integer ranges explicitly or can we assume the input will contain integers in the expected range?

Assumptions Based on Clarifying Questions

  1. The grid is guaranteed to be an n x n matrix.
  2. We assume that the value of n is reasonable, as typically given in competitive programming constraints.
  3. If conditions are satisfied, we return true, otherwise false.

Strategy

The strategy to solve this problem involves three main checks:

  1. Distinct Elements Check: Use a set to ensure all elements in the grid are distinct and fall within the range [1, n^2].
  2. Sum Check: Calculate the sum of elements in each row and each column and verify all row sums and column sums are equal.
  3. Combine both checks to determine if the grid satisfies the given conditions.

Code

import java.util.HashSet;
import java.util.Set;

public class GridChecker {
    public boolean checkGrid(int[][] grid) {
        int n = grid.length;
        if (n == 0) return false;  // Sanity check
        
        Set<Integer> seen = new HashSet<>();
        int expectedSum = 0;
        
        // Calculate the sum of the first row to use as a reference
        for (int i = 0; i < n; i++) {
            expectedSum += grid[0][i];
        }
        
        // Validate all numbers in range and distinct, also check the sums of rows and columns
        for (int i = 0; i < n; i++) {
            int rowSum = 0;
            int colSum = 0;
            
            for (int j = 0; j < n; j++) {
                int num = grid[i][j];
                
                // Check if the number is in the valid range
                if (num < 1 || num > n * n) {
                    return false;
                }
                
                // Check if the number is distinct
                if (!seen.add(num)) {
                    return false;
                }
                
                rowSum += num;
                colSum += grid[j][i];
            }
            
            // Check if the current row sum and column sum match the expected sum
            if (rowSum != expectedSum || colSum != expectedSum) {
                return false;
            }
        }
        
        return true;
    }

    public static void main(String[] args) {
        GridChecker checker = new GridChecker();
        int[][] grid1 = {
            {1, 2},
            {3, 4}
        };
        int[][] grid2 = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        
        System.out.println(checker.checkGrid(grid1)); // true
        System.out.println(checker.checkGrid(grid2)); // false
    }
}

Time Complexity

Given n x n grid, the overall time complexity is O(n^2).

This solution is efficient because each element is processed a constant number of times, making it well-suited for reasonably large n.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI