anyone in O(1) extra space?

Is there a O(1) extra space solution? I tried looking up for patterns but it didn't help. Can we have a function f such that matrix[i][j] = f(i, j, n) for all valid i and j?

Re: anyone in O(1) extra space?

Posted by

Paul 24 Feb 2023 23:41

Still takes more space than some O(N^2) solution i've found for some reasons. I am not really familiar with cpp compiler optimizations, so that might be linked !

#include <iostream>

int main(int argc, char* argv[]) {

int size;

if (argc != 2) {

scanf("%d",&size);

} else {

size = std::atoi(argv[1]);

}

int halfSquare = (size * size) / 2;

int half = size / 2;

int previousY0 = halfSquare - (half) - size;

int previous;

for (int y = 0; y < size; y++) {

previous = previousY0 + (size + 1 - y);

printf("\n%d ", previous);

for (int x = 1; x < size; x++) {

previous = previous - (size - 1 - std::max(std::abs(x - y), 1) + (x >= y));

printf("%d ", previous);

}

previousY0 = previousY0 + (size + 1 - y);

}

return 0;

}