algorithm - traverse a range in n*m 2D array with linear Time complexity(less than n*m)

Question

The time complexity of traversing an n by m 2d array is O(nm). Consider we are given a range in an array, let's say it is (t,t) where 1<t<n and 1<t<m.( we want to traverse array starting (0,0) and to end at (t,t).

Is there any way to traverse the array in linear time? How about space complexity?

Answer 1

Any way you implement the array, you will need to visit each space sequentially in order to traverse it from (0,0) to (t,t).

Using a 1 dimensional array would allow you to implement the matrix using the least amount of space.