algoadvance

Leetcode 3142. Check if Grid Satisfies Conditions

Problem Statement

You are given a 2D grid grid of size m x n containing integers. You need to check whether the grid satisfies the following conditions:

  1. Strictly Increasing Rows: Each row in the grid must have strictly increasing values from left to right.
  2. Strictly Increasing Columns: Each column in the grid must have strictly increasing values from top to bottom.

Return true if the grid satisfies both conditions, and false otherwise.

Clarifying Questions

  1. Input Range: What are the constraints on the dimensions of the grid (m and n) and the values within the grid?
    • Usually, constraints on the dimensions and values would determine the efficiency of the solution.
  2. Edge Cases: Should we handle cases when the grid is empty or has only one row/column?
    • Specifically, grids with dimensions 0 x 0, 1 x n, and m x 1.

Strategy

  1. Strictly Increasing Rows:
    • Iterate through each row and check if every subsequent element is greater than the previous one.
  2. Strictly Increasing Columns:
    • Iterate through each column and ensure that every subsequent element is greater than the one above it.
  3. Edge Cases:
    • If the grid has only one row or one column, it trivially satisfies the conditions.

Code

Here is the C++ implementation to solve the problem:

#include <vector>

bool checkGridConditions(const std::vector<std::vector<int>>& grid) {
    int m = grid.size();
    if (m == 0) return true; // An empty grid trivially satisfies the conditions
    int n = grid[0].size();
    if (n == 0) return true; // An empty grid trivially satisfies the conditions

    // Check strictly increasing rows
    for (int i = 0; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            if (grid[i][j] <= grid[i][j-1]) {
                return false;
            }
        }
    }

    // Check strictly increasing columns
    for (int j = 0; j < n; ++j) {
        for (int i = 1; i < m; ++i) {
            if (grid[i][j] <= grid[i-1][j]) {
                return false;
            }
        }
    }

    return true;
}

Time Complexity

This solution iterates through each element of the grid a constant number of times, making it efficient and appropriate even for larger grids within typical competitive programming constraints.

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