Coding Algorithms — Modify Array in Place
One of the common problems asked in coding interviews is to rotate or modify an array (or matrix) in place. These kind of problems can be tricky to implement if you do not know the strategy. Without a strategy, candidates are stuck in solving the problem case by case and handling corner cases.
While it is an easy problem if we are allowed to use extra space or create an entirely new array (or matrix) with the new changes but the hard part is implementing in place (and/or without using extra space).
Lets look at few problems that deals with such scenarios and solve them using some simple strategies:
Problem 1:
Given 2 arrays A and B of the same length. Array B is a permutation of the indices of the array. Sort the array A in-place according to B. For e.g. A=[100, 24, 96, 13, 245, 1] and B = [3, 0, 5, 2, 1, 4], then A should be modified to [13, 100, 1, 96, 24, 245].
Solution:
The inefficient way to do so is to create a new array C and copy the elements of the array A according to the corresponding index in B. Both space and time complexity is O(N).
But we can also do it in place without using that extra array. One thing to remember is to understand use cases where we can do it in place. Because that will modify the original array and it could not be used elsewhere.
The above method is more generic.
The idea to do it in place is that if we observe carefully, we will see that if we create a graph of the shifts happening then there will be one or more cycles representing the shifts.
For e.g. if we plot the shifts in the array B above we see the following (where x->y implies that index ‘x’ in original array is mapped to index ‘y’ in new array):
{3->0, 0->1, 5->2, 2->3, 1->4, 4->5}
Then we can see the cycle {3->0->1->4->5->2->3}.
Similarly if array B was [3, 2, 5, 0, 1, 4]
The the shifts are: {3->0, 2->1, 5->2, 0->3, 1->4, 4->5} and if we connect them we will see 2 cycles forming: {3->0->3, 2->1->4->5->2}.
If the cycle length is > 1, and is represented as say {i1->i2->i3->…i1}, then we first swap i1 and i2, that will bring i1 in its correct place i.e. i2, but i2 is still not correctly placed because it is at i1 and it should be at i3. Next we swap i1 and i3 and so on until all the elements are in their correct positions. To mark that we have already put the correct element at a position we set the value at that index to -1, so that we do not again swap that element.
In our example:
A=[100, 24, 96, 13, 245, 1]
B=[3, 0, 5, 2, 1, 4]
Cycle is {3->0->1->4->5->2->3}.
Step 1: Swap index 3 with index 0 and set -1 at index 0: A=[13, 24, 96, 100, 245, 1], B=[-1, 0, 5, 2, 1, 4]
Step 2: Swap index 3 with index 1 and set -1 at index 1: A=[13, 100, 96, 24, 245, 1], B=[-1, -1, 5, 2, 1, 4]
Step 3: Swap index 3 with index 4 and set -1 at index 4: A=[13, 100, 96, 245, 24, 1], B=[-1, -1, 5, 2, -1, 4]
Step 4: Swap index 3 with index 5 and set -1 at index 5: A=[13, 100, 96, 1, 24, 245], B=[-1, -1, 5, 2, -1, -1]
Step 5: Swap index 3 with index 2 and set -1 at index 2: A=[13, 100, 1, 96, 24, 245], B=[-1, -1, -1, 2, -1, -1]
Step 6: Swap index 3 with index 3 and set -1 at index 3: A=[13, 100, 1, 96, 24, 245], B=[-1, -1, -1, -1, -1, -1]
We have successfully modified the array in place. But note that to know the next position in the cycle we have to store a map in memory which will be O(N).
We can overcome this problem by going in the cycle backwards (anticlockwise) instead of clockwise. i.e. after we swap index 3 and index 0, we swap index 2 and index 3, then index 5 and 2 and so on.
Additional space complexity is O(1).
For multiple cycles scenario, we have to start swapping from only one element of that cycle.
Problem 2:
Given an array, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]Solution:
Similar to the 1st problem, we identify the shifts happening here. So the shifts looks like i->(i+k)%N, i.e. index i is shifted to index (i+k)%N where N is the total number of elements. As before, we can have multiple cycles.
Since we already know the mapping of the shifts by a formula, we do not need to store them explicitly in a map.
Also to track which all elements has been placed correctly or which all cycles has been completed, so we do not visit those again, we observe that shifts are “linear” i.e. for each cycle of shift, the maximum index in that cycle increases as we move from left to right in the array.
Thus if the maximum index in a cycle we have seen is the last index, then this is the last cycle and we do not need to shift anymore.
Additional space complexity is O(1).
Problem 3:
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]Solution:
Similar to the rotate array problem, we first identify the shifts in this problem, which is also given by the formula:
(i, j)->(j, n-i-1) where ’n’ is the number of columns.
Thus we do not need to keep an explicit map in memory to store the shifts.
Also note that the pattern of the shift cycles, each cycle is either of length 0 or length 4 because the shifts happen for a cycle along the boundaries. If we draw a line along the outermost rows and columns i.e. row and column number is either 1 or n, then all shifts in this line will happen within this line, similarly if we draw a line along the 2nd layer of rows and columns i.e. either row or column number is 2 or n-1, then all shifts in this line will happen within this line. Thus we do not need to explicitly keep a visited set to track which all indexes has been visited.
Additional space complexity is O(1).
