How to 'onion' into NxN array?
This concept arises when you are trying to rotate an N by N square array. Pretty weird at the start. There are mainly two difficult parts to writing an algorithm for this.
1. How do you put top left element to top right element, top right element to bottom right element, bottom right element to bottom left element, bottom left element to top left element - all of them all at once?
2. How do you make an algorithm so that each 'layer' goes through such operations?
Those were very difficult questions for me, and I couldn't find answers myself so I resorted to the answers (cracking the coding interview, chapter 1).
Let's address the first question. We firstly consider sending value of a -> b, b->c, c->d, d->a at once, because that's essentially what we are doing.
public void moveAround(int a, int b, int c, int d){
int tmp = a;
a = d;
d = c;
c = b;
b = tmp;
}Whatever is first overriden will be stored in the tmp variable, and will be used at the end where it's that element's turn to override the next element.
Okay, so now let's write down the algorithm to rotate one layer.
public void rotateOneLayer(int[] top, int[] right, int[] bottom, int[] left){
for(int i = 0; i<top.length; i++){
int tmp = top[i];
top[i] = left[i];
left[i] = bottom[i];
bottom[i] = right[i];
right[i] = tmp;
}
}Okay, so that's one of the difficult part about this question. Next difficult part is "2. How do you make an algorithm so that each 'layer' goes through such operations?"
We can visualize that a sub-problem of this is: given a length n array, make a loop such that it iterates like this in sequence:
- 0 to n-1th element
- 1 to n-2th element
- 2 to n-3th element
- middle element (how to deal with two middles and one?)
This concept of 'middle' has always been confusing to me. In this case the answer depends on if we actually have to touch the middle element in the case that we have odd number of elements. If we don't (and we don't, because we don't have to swap that middle element with itself - that's a redundant operation, and such an odd case):
middle index = array.length/2;
Why is that?
In the case that we have odd number of elements:
Case of odd:
Suppose we have 7 elements. Then the indices are from 0 to 6. If we want the loop such that it goes over elements like:
- 0,1,2,3,4,5,6
- 1,2,3,4,5
- 2,3,4
// note we don't need to go over the middle element
Then the starting points are 0,1,2, which can be given by for(int i = 0; i < (array.length)/2; i++), since array.length/2 = 7/2 = 3.
In the case that we have even number of elements:
Case of even:
Suppose we have 8 elements.
- 0,1,2,3,4,5,6,7
- 1,2,3,4,5,6
- 2,3,4,5
- 3,4
The starting points are given by for(int i = 0; i<array.length/2; i++) because array.length/2 = 8/2 = 4.
Hence, the algorithm for onioning 1D array will look like:
int n = array.length;
for(int i = 0; i < n/2; i++){
// have another for loop that uses i as a starting index, and finishes at the exactly same length from the end
}As written in the comment, we only know that i is the starting index, and we haven't finished yet.
The important part now is to implement "... finishes at the exactly same length from the end". We can think of it inductively.
| iteration | index ranges from... | for loop looks like |
| 1 | 0 to n-1 | int j = 0; j<n |
| 2 | 1 to n-2 | int j = 1; j<n-1 |
| 3 | 2 to n-3 | int j = 2; j<n-2 |
| 4 | 3 to n-4 | int j = 3; j<n-3 |
And we know that the values of j is provided by the outer loop's index i, which are the starting indices. Notice that the RHS of inequalities are always n-i. So:
int n = array.length;
for(int i = 0; i < n/2; i++){
for(int j = i; j<n-i; j++){
//
}
}We finally got it!
Now the difficult part is to get the same logic working for 2D case ('onion'ing)
What we want is, for example:
Given an array that has 4x4:
Firstly iterate over the outer part of that matrix:
| This | This | This | This |
| This | This | ||
| This | This | ||
| This | This | This | This |
Then iterate over the next outermost layer:
| This | This | ||
| This | This | ||
Now, putting everything together, we get
public void onion(int[][] matrix){
int n = matrix.length;
for(int layer = 0; layer < n/2; layer++){
int first = layer;
int last = n-layer;
for(int i = first; i<last; i++){
// note layer and i both start from top left corner,
// but i is a variable that iterates to the limit (just before 'last')
int tmp = matrix[layer][i]; // represents top[]
// if we want to get the bottom left:
// note that (last-1) is the bottom element.
matrix[layer][i] = matrix[last-1-i][layer];
matrix[last-1-i][layer] = matrix[last-1][last-1-i];
matrix[last-1][last-1-i] = matrix[i][last-1];
matrix[i][last-1] = tmp;
}
}
}
Very complicated mess, but if you understand how the swap is working in the background (and exactly which elements are swapped, the direction of the iteration for top, bottom, right, left arrays), it would come to you eventually.
public void onion(int[][] matrix){
int n = matrix.length;
for(int layer = 0; layer < n/2; layer++){
int first = layer;
int last = n-layer;
for(int i = first; i<last; i++){
int inward = last-1-i;
int outward = i;
int tmp = matrix[layer][outward];
matrix[layer][outward] = matrix[inward][layer];
matrix[inward][layer] = matrix[last-1][inward];
matrix[last-1][inward] = matrix[i][last-1];
matrix[i][last-1] = tmp;
}
}
}I'm gonna try to explain the thought behind this.
The variables 'inward' and 'outward' are the ones that actually iterates over the arrays; note that other indices are constant. So the logic is quite simple. For a constant index column/row, iterate over using inward or outward.