Problem 6.18 (Java version) variant 6: kth element in spiral ordering in O(1)

#1

Hi guys,

First post here. I’m trying to solve the problem above from the Java version but I don’t think I have an O(1) solution.

The variant before this asked to compute the last element in spiral ordering in O(1) and I think I got it, just need some paper to try it.

Regarding variant 6, the first issue is with k. First you check if k>2col+2row. That is the perimeter of the outermost rectangle. Then you proceed for the next rectangle and so on until k would be negative and you just found the perimeter where k lies.

Only the operations above are O(n) complexity.

If you have precomputed perimeters for the given number of decreasing rows and columns you can perform a binary search to find the (inner) rectangle where k would fit. This is O(log n). With this information, you still have to find element number k-t, where t = sum of all the perimeters of the previous outer rectangles (which you already have, the precomputed perimeters). This can still lead to O(n) time complexity, plus O(n) space complexity.

Maybe there’s another way to tackle this problem, completely different.

0 Likes
#2

Hey Bogdan,

Thanks for your question, and I think you are on the right track of solving this problem, and let me give yo some more hints on solving this.

Basically, as we go through the spiral order of this 2D array, the first-level perimeter has 2(n-1) + 2(m-1) elements, and the second-level perimeter has 2(n-2) + 2(m-2) elements. Similarly, you can deduct the number of elements in the deeper levels easily. Eventually, those things for an arithmetic sequence which can be computed in O(1) time with close form equation.

With that equation, we can quickly compute the level of the kth element shall fall.

0 Likes
#3

Thank you. I am working on a solution right now.

0 Likes
#4

Could you please share any solution for this? I could not get the answer for the m x n matrix (rectangular matrix) in O(1) time.

0 Likes
#5

@tobhaveshpatel,

The idea is to use math to calculate which row and which column you shall go to. This problem is easier to think first if we limit the scenario in m * m matrix. You can start from that and try to generalize the idea later.

0 Likes
#6

@tsunghsienlee: I am trying to come up the close form equation that you mentioned. It is currently in the form of 2*x(n+m-y) where x is the level (e.g. 1, 2, 3) and y is x + 1. Replace y with x+1, the equation becomes 2*x(n+m-x-1). This is where I am stuck being unable to figure out how to compute the perimeter level with the equation. Please help!!

0 Likes
#7

does not second level has 2(n-3) + 2(m-3) = 4m - 12
for example for 4x4 ( second perimeter has 12 in first perimeter and second level has 4 only)

Am I missing anything here?.

0 Likes