(Problem 6.18 variant) The last element in spiral order for a m x n 2D array

#1

Hi All,
All solutions and thoughts about “last element in spiral order for m x n 2D array” are welcome. I have spent a whlie on that.

Thanks,
yh

0 Likes
#2

Could you mention your idea first? Because in the worst case you can solve it still by simulating it.

0 Likes
#3

I know the O(n) solution. I am looking for the O(1) solution.
My idea for getting the last element is as following, but has some bugs for some case
1). get how many row and col needed to walk. steps = min(m, n), the cols should be steps - 1 when m <= n
2). based on the odd or even of the row steps, get the final col, and based on the odd or even of col steps, get the final row.

void lastSpiral(int m, int n, int &x, int &y) {
     int row_s = 0, col_s = 0;
     row_s = col_s = min(m, n);

    if (m <= n )  col_s--;

  //  x = row_s / 2;
  //  y = (col_s - 1) / 2;

   if (col_s & 0x1) x = m - row_s/2;
   else x = row_s/2;
   if (row_s & 0x1) y = n - 1 - col_s/2;
    else y =(col_s - 1)/2;
 }

Thanks!

0 Likes
#4

I think your direction is totally correct and you just block yourself by assuming that getting to know how many rows and columns is O(1) instead of O(n). In this problem, we give you the input 2D array which will provide O(1) method to get m and n efficiently (e.g., .size() method if it is C++ vector.).

0 Likes