Is there a way to solve this not in linear time?
I did a solution which is taking O(6N) time and O(2C) space, where N is num of days and C is num of prison cells
This is proper solution but failing if N = 10^9.
Not sure if there better solution, or maybe hidden algorithm under it

...
for (int d = 1; d <= n; d++) {
	....
	for (int c = 1; c < cells.length - 1; c++) {
		curr[c] = prev[c - 1] == prev[c + 1] ? 1 : 0;
	}
}
...