Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 15, 2016 01:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/4d719488e378aeb498d4cb363cbd1f7d to your computer and use it in GitHub Desktop.
Save jianminchen/4d719488e378aeb498d4cb363cbd1f7d to your computer and use it in GitHub Desktop.
Rotate Array k steps - run time error - https://www.hackerrank.com/challenges/matrix-rotation-algo
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace RotateArray2
{
class Program
{
static void Main(string[] args)
{
string s1 = Console.ReadLine();
string[] sA = s1.Split(' ');
int row = Convert.ToInt16(sA[0].Trim());
int col = Convert.ToInt16(sA[1].Trim());
int T = Convert.ToInt16(sA[2].Trim());
int[][] arr = new int[row][];
for (int i = 0; i < row; i++)
arr[i] = new int[col];
for (int i = 0; i < row; i++)
{
string s = Console.ReadLine();
string[] aA = s.Split(' ');
if (aA.Length != col)
return;
for (int j = 0; j < col; j++)
arr[i][j] = Convert.ToInt16(aA[j].Trim());
}
for (int i = 0; i < T; i++)
rotateArrayOneStepAntiClockwise(arr);
for (int i = 0; i < row; i++)
{
string s = "";
for (int j = 0; j < col; j++)
s += arr[i][j].ToString() + " ";
Console.WriteLine(s);
}
}
/*
* Do it in place
*/
public static bool rotateArrayOneStepAntiClockwise(int[][] arr)
{
if (arr == null) return false;
int row = arr.Length; // row
int col = arr[0].Length; // column
int start = 0;
int end = col - 1;
while (start <= end && start < row / 2 && start < col / 2)
{
int totalRow = row - 2 * start;
int totalCols = col - 2 * start;
int firstRow = start;
//int LastRow = totalRow - 1; // math is wrong for last row
int lastRow = row - start - 1;
int firstCol = start;
int lastCol = end;
int totalSwap = 2 * (totalRow + totalCols) - 4 - 1;
swap(arr, start, start, start + 1, start, row, col);
totalSwap--;
// for up row Direction: L -> R
for (int i = firstCol + 1; i <= lastCol; i++, totalSwap--)
{
int[] node = new int[2] { firstRow, i };
int[] node2 = new int[2] { firstRow, i - 1 }; // left node
swap(arr, node[0], node[1], node2[0], node2[1], row, col);
}
// for right column Direction: top -> down
for (int i = firstRow + 1; i <= lastRow; i++, totalSwap--)
{
int[] node = new int[2] { i, lastCol };
int[] node2 = new int[2] { i - 1, lastCol }; // up node
swap(arr, node[0], node[1], node2[0], node2[1], row, col);
}
// for down row - Direction: R -> L
for (int i = lastCol; i > firstCol && totalSwap>=0; i--, totalSwap--)
{
int[] node = new int[2] { lastRow, i };
int[] node2 = new int[2] { lastRow, i - 1 }; // left node
if(isSameNode(node2, start, start) || isSameNode(node2, start+1, start))
break;
swap(arr, node[0], node[1], node2[0], node2[1], row, col);
}
// for left column - Direction: Down -> up first 2 rows - no touch
for (int i = lastRow; i >= firstRow + 3 && totalSwap>=0; i--, totalSwap--) //
{
int[] node = new int[2] { i, firstCol };
int[] node2 = new int[2] { i - 1, firstCol }; // up node
swap(arr, node[0], node[1], node2[0], node2[1], row, col);
}
start++;
end--;
}
return true;
}
/*
*
*/
private static bool isSameNode(int[] node, int x, int y)
{
return Math.Abs(node[0] - x) + Math.Abs(node[1] - y) == 0;
}
private static void swap(int[][] arr, int x1, int y1, int x2, int y2, int maxRow, int maxCol)
{
if (!(x1 < maxRow && y1 < maxCol && x2 < maxRow && y2 < maxCol))
return;
if (!(x1 >= 0 && y1 >= 0 && x2 >= 0 && y2 >= 0))
return;
int tmp = arr[x1][y1];
arr[x1][y1] = arr[x2][y2];
arr[x2][y2] = tmp;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment