Algorithms

transpose.js

/**
* Question - Given an image represented by an N x N matrix, where 
* each pixel in the image is 4 bytes, write a method to rotate the
* image by 90 degress. Can you do this in place?
*
* rotateCopy() method is a brute force method to transpose one item 
* at a time and return a new array. It is very slow. The time 
* complexity is O(N^2), and it take as N^2 * [0-2^32) bits of memory.
* 
* rotate() method performs a cyclic swap on the edges on each layer.
* In the first for loop, we rotate the first layer (outermost edges).
* We rotate the edges by doing a four-way swap first on the corners,
* then on the element clockwise from the edges, then on the element
* three steps away.
* Once the exterior elements are rotated, we then rotate the interior
* region's edges.
* It is about 4 times less slow, but is still quite slow because of 
* the time complexity is still O(N^2), and it takes less than 
* N^2 * [0-2^32) bits of memory.
*
*/

function rotate(A) {
  var n = A.length;
  for (var i = n; i > 1; i = i -2) {
    var tmp;
    var s = i - 1;
    var d = Math.floor((n - i) /2);
    for (var j = 0; j < s; j++) {
      tmp = A[j+d][s+d];
      A[j+d][s+d] = A[d][j+d];
      A[d][j+d] = A[s-j+d][d];
      A[s-j+d][d] = A[s+d][s-j+d];
      A[s+d][s-j+d] = tmp;
    }
  }
}

function rotateCopy(A) {
  var m = A.length;
  var n = A[0].length;
  var AT = new Array(n);
  for (var i = 0; i < n; i++) {
    AT[i] = new Array(m);
  }
  for(var i = 0; i< m; i++) {
    var row = A[i];
    for (var j = 0; j < n; j++) {
      AT[j][m-1-i] = row[j];
    }
  }
  return AT;
}

function createRandomMatrix(size) {
  var arr = new Array(size);
  for (var i = 0; i < size; i++) {
    arr[i] = new Array(size);
    for (var j = 0; j < size; j++) {
      arr[i][j] = generateRandomInt(0, Math.pow(2, 4 * 8));
    }  
  }
  return arr;
}

function generateRandomInt(min, max) {
  var floor = Math.floor(min);
  var ceil = Math.ceil(max);
  return Math.floor(Math.random()*(ceil - floor)) + floor;
}

var arr = createRandomMatrix(20000);


var startTime = new Date().getTime();
// rotateCopy(arr);
rotate(arr);
var endTime = new Date().getTime();
console.log(endTime - startTime);