PROBLEM LINK:
Practice
Contest
Author: Siddhartha Paul
Editorialist: Baban Gain
DIFFICULTY:
EASY
PREREQUISITES:
None
PROBLEM:
A 8*8 matrix will be given. Rotate all elements of a selected row or column as specified by input.
EXPLANATION:
Let N = 8
If no. of shifts is greater than N,
then no, of shift N+1, 2N+1, 3N+1… are equivalent to 1 shift
similarly N+2, 2N+, 3N+2… are equivalent to 2 shift and so on.
Initialise an temporary array of size N.
So, if it is a Row operation,
for every element in that row R,
temp[(i + shift) % N] = arr[R][i]
and copy back the temporary array to original matrix’s Rth row.
And it is a Column operation,
for every element in that col C,
temp[(i + shift) % N] = arr[i][C];
and copy back the temporary array to original matrix’s Cth column.
Time Complexity: O(N) for each shift operation
AUTHOR’S SOLUTIONS:
Click for Python
Click for C++
Time Complexity is not O(1) , please take care of such things when you are especially an editorialist of a problem.
Thank you for pointing that out.
Hmmm… sounds cool,
How about making time complexity O(1) from O(N) with the cost of adding a little extra space (4N^2 instead of 2N^2) ?
Sounds interesting ??
The general idea used for cyclic shifts problem is appending the pattern to itself , i.e, string s becomes s+s, let k=s.size( ) now use reference pointing to first element and increase it in case of cyclic shift. If the pattern goes ahead of k , bring it back to index < k.
Similar idea can be used with your matrix, appending it both horizontally and vertically. Suppose your first row is 2 3 4 5, after appending it becomes 2 3 4 5 2 3 4 5, now reference is at index 0 and k is 4, if we shift 1 unit, k remains 4, reference comes at 1, so if someone asks to print it, we start from index 1 and print 4 digits, which would essentially be the cyclic shifted form. Shifting of index takes O(1) time compared to coppying of whole row which takes O(N) time.
This difference would be essential if number of queries is much more.
I leave the implementation part for the reader. 
2 Likes