Constant Down Every Diagonal

EasyMatrix

Problem

A wallpaper printer only works with patterns in which every diagonal running from top-left to bottom-right holds a single repeated value. Given an m × n pattern grid, return true if every such diagonal is constant, and false otherwise.

Example 1

Input:
grid = [[1, 2, 3, 4], [5, 1, 2, 3], [9, 5, 1, 2]]
Output:
true

The diagonals are [9], [5, 5], [1, 1, 1], [2, 2, 2], [3, 3] and [4]; each holds one value.

Example 2

Input:
grid = [[1, 2], [2, 2]]
Output:
false

The main diagonal holds 1 and 2.

Constraints

  • 1 ≤ m, n ≤ 1000
  • 0 ≤ grid[i][j] ≤ 10^4

Hint

Show the first hint

Two cells lie on the same top-left to bottom-right diagonal exactly when r - c is the same.

Walkthrough

How to approach it

01Clarify before coding

  • Which diagonals: top-left to bottom-right? Yes.
  • Is a single row or column valid? Yes, every diagonal then has one cell.
  • Can the grid be rectangular? Yes, m and n are independent.

02Brute force

Group all values by r - c in a hash map of sets, then check that every set has size 1.

Cost: O(m · n) time but O(m · n) extra memory for the groups.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.