Press "Enter" to skip to content

Posts tagged as “matrix”

花花酱 LeetCode 766. Toeplitz Matrix

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.
Example 1:

Example 2:

Note:

  1. matrix will be a 2D array of integers.
  2. matrix will have a number of rows and columns in range [1, 20].
  3. matrix[i][j] will be integers in range [0, 99].

Idea:

Check m[i][j] with m[i-1][j-1]

Solution: Brute Force

Time complexity: O(n*m)

Space complexity: O(1)

C++

Java

Python3

 

 

花花酱 LeetCode 221. Maximal Square

Problem:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

 

Idea:

Dynamic programming



Solution 0: O(n^5)

 

Solution 1: O(n^3)

Solution 2: O(n^2)

 

Solution 1:

 

Solution 2: