0

I have a LeetCode problem:

Given an M x N matrix, return True if and only if the matrix is Toeplitz.

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

My solution is (Swift):

func isToeplitzMatrix(_ matrix: [[Int]]) -> Bool {
    if matrix.count == 1 { return true }

    for i in 0 ..< matrix.count - 1 {
        if matrix[i].dropLast() != matrix[i + 1].dropFirst() { return false }
    }

    return true
}

As I understood Big O notation, my algorithm's time complexity is O(n), while LeetCode top answers' is O(n^2).

Top answers example:

func isToeplitzMatrix(_ matrix: [[Int]]) -> Bool {
    for i in 0..<matrix.count-1 {
      for j in 0..<matrix[0].count-1 {
          if (matrix[i][j] != matrix[i+1][j+1]) {
              return false;
          }
      }
    }

     return true;
}

Still, my algorithm takes 36ms (according to LeetCode), while top answer takes 28ms.

When I commented out if matrix.count == 1 { return true } it took even more time to run - 56ms.

melpomene
  • 84,125
  • 8
  • 85
  • 148
  • Possible duplicate of [Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?](https://stackoverflow.com/questions/22594174/can-an-on-algorithm-ever-exceed-on2-in-terms-of-computation-time) – Patrick May 25 '18 at 16:56
  • 1
    What's the time complexity of `dropFirst()` and `dropLast()`? What's the time complexity of `!=` on arrays? – melpomene May 25 '18 at 16:57
  • What is `n` here? The number of rows in the matrix or the number of ints? Either way both pieces of code look to have the same complexity (`O(n)` for number of ints; or `O(n^2)` if `n` is the number of rows, which is also the number of columns). – sepp2k May 25 '18 at 17:03

1 Answers1

3

Your time complexity for the function is also O(n^2) because the function call dropLast is O(n).

Edit: Also mentioned by Rup and melpomene, the comparison of arrays also takes the complexity up to O(n^2).

Also, Big O notation describes how the algorithm scales in response to n, the number of data. It takes away any constants for brevity. Therefore, an algorithm with O(1) can be slower than an algorithm with O(n^3) if the input data is small enough.

Hyrial
  • 1,728
  • 3
  • 15
  • 27
  • 1
    As well as dropLast, as melpomene points out in the comments there's also an array compare per row which is also going to be O(n) per row. – Rup May 25 '18 at 17:03
  • @MartinR Only dropFirst has O(1) while dropLast has O(n). https://developer.apple.com/documentation/swift/array/1689669-droplast – Hyrial May 25 '18 at 17:30
  • Actually dropLast() is O(1) as well for arrays, but the documentation is wrong: https://forums.swift.org/t/droplast-vs-droplast-1-for-arrays/12977 – Martin R May 26 '18 at 18:53