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.