find duplicate elements k indices away in matrix

There are two problems which are quite similar to each other.

Given an array of integer, find duplicates which are within k indices away.  See this link for reference:
http://www.geeksforgeeks.org/check-given-array-contains-duplicate-elements-within-k-distance/

Given a 2D array of integer, find duplicates which are within k indices away.

Both can be solved by using a sliding window of k indicies, maintain a hash storing the elements seen so far then check if the next element is in the hash, if not, remove the element at the start of sliding window and continue.

//for list of integers

public static boolean hasKDistanceDuplicate(int[] array, int k){

Set<Integer> store = new HashSet<Integer>();

for(int i=0, j=0; i<array.length; i++){

//maintain a sliding window of k size

while(j<array.length && j-i<=k){

if(store.contains(array[j])){

return true;

}else{

store.add(array[j]);

j++;

}

}

if(j<array.length)

store.remove(array[i]);

}

return false;

}

//for 2D matrix of integers

public static boolean determineKIndices(int[][] matrix, int k){

Map<Integer, Set<Pos>> store = new HashMap<Integer, Set<Pos>>();

for(int row=0; row<matrix.length; row++){

for(int col=0; col<matrix[0].length; col++){

int val = matrix[row][col];

if(store.containsKey(val)){

Set<Pos> set = store.get(val);

for(Pos p: set){

if(Math.abs(p.getRow() - row) + Math.abs(p.getCol()-col) <=k ){

return true;

}

      if(row - p.getRow() >k)
        set.remove(p);

}

set.add(new Pos(row, col));

}else{

Set<Pos> set = new HashSet<Pos>();

set.add(new Pos(row, col));

store.put(val, set);

}

}

}

return false;

}

Matrix rotation

There are two kinds of matrix rotation problems: one is to rotate the whole matrix clock-wise by 90 degree,

Input:
1 2 3
4 5 6
7 8 9

Output:
7 4 1
8 5 2
9 6 3

Think about the above a graph process software to rotate the pixels in an image. See this link:
http://www.programcreek.com/2013/01/leetcode-rotate-image-java/

Another way is to shift the elements clock-wise:


Input:
1 2 3
4 5 6
7 8 9

Output:
4 1 2
7 5 3
8 9 6

Here I present solutions to both:
/*
* essentially we treat elements in the matrix as circles, there are total Math.ceil(matrix.length/2) circles.
* However if matrix length is odd, the most inner circle contains one element, we don't need to rotate it.
* so we can deal with Math.floor(matrix.length/2) circles.
*/

public static void rotateMatrix(int[][] matrix){

int num = matrix.length;

for(int i=0; i<num/2; i++){

for(int j=i; j<num-i-1; j++){

int temp = matrix[i][j];

matrix[i][j] = matrix[num-j-1][i];

matrix[num-j-1][i] = matrix[num-i-1][num-j-1];

matrix[num-i-1][num-j-1] = matrix[j][num-i-1];

matrix[j][num-i-1] = temp;

}

}

for(int i=0; i<num; i++)

System.out.println(Arrays.toString(matrix[i]));

}

/*

 * shifting is similar above, we shift Math.floor(matrix.length/2) circle one by one

 */

public static void rotateMatrixByShiftElements(int[][] matrix){

int num = matrix.length;

for(int i=0; i<num/2; i++){

int start = matrix[i][i];

//shift up on column i

for(int row=i; row<num-i-1; row++){

matrix[row][i] = matrix[row+1][i];

}

//shift left on row num-i-1

for(int col=i; col<num-i-1; col++){

matrix[num-i-1][col] = matrix[num-i-1][col+1];

}

//shift down on column num-i-1

for(int row=num-i-1; row>i; row--){

matrix[row][num-i-1] = matrix[row-1][num-i-1];

}

//shift right on row i

for(int col=num-i-1; col>i; col--){

matrix[i][col] = matrix[i][col-1];

}

//the last one!

matrix[i][i+1] = start;

}

for(int i=0; i<num; i++)

System.out.println(Arrays.toString(matrix[i]));

}