Twenty Percent Knowledge: Find duplication within k indices in a matrix

Given an array of integer, find duplicates which are within k indices away. Find duplicates within K manhattan distance away in a matrix or 2D array. Return true or false if such elements exists.

Note that Manhattan Distance within two points in an 2-dimensional grid is simply |p1.x-p2.x|+|p1.y-p2.y|

copying from http://www.zrzahid.com/duplicates-within-k-distance-in-arraymatrix2d-array/

Sliding window problem.

it is checking duplication, so a hashset is first thought without thinking.

In order to maintain the sliding window we initially create a hashset of size k from first k indices. Then for each index in the array we slide the window by removing the first element of the window from the hashset and adding the current element to the hashset. Meanwhile we keep testing for any duplicates.

O(n) time and O(k) space.

Below is for flat array.

static boolean checkDuplicatesWithinK(int arr[], int k)
    {
        // Creates an empty hashset
        HashSet<Integer> set = new HashSet<>();
 
        // Traverse the input array
        for (int i=0; i<arr.length; i++)
        {
            // If already present n hash, then we found 
            // a duplicate within k distance
            if (set.contains(arr[i]))
               return true;
 
            // Add this item to hashset
            set.add(arr[i]);
 
            // Remove the k+1 distant item
            if (i >= k)
              set.remove(arr[i-k]);
        }
        return false;
    }

public static boolean checkDuplicateWithinK(int[] a, int k){
 int n = a.length;
 k = Math.min(n, k);
 
 //there are k+1 elements within k induces from an element - so window size is k+1
 Set<Integer> slidingWindow = new HashSet<Integer>(k+1);
 
 //create initial wiindow of size k+1
 int i;
 for(i = 0; i <= k; i++){
  if(slidingWindow.contains(a[i])){
   return true;
  }
  
  slidingWindow.add(a[i]);
 }
 
 //now slide
 for(i = k+1; i < n; i++){
  slidingWindow.remove(a[i-k]);
  if(slidingWindow.contains(a[i])){
   return true;
  }
  slidingWindow.add(a[i]);
 }
 
 return false;
}

For Manhattan distance, using hashmap instead of set.

public static boolean checkDuplicateWithinK(int[][] mat, int k){
 class Cell{
  int row;
  int col;
  public Cell(int r, int c){
   this.row = r;
   this.col = c;
  }
 }
 
 int n = mat.length;
 int m = mat[0].length;
 k = Math.min(k, n*m);
 
 //map from distance to cell postions of the matrix
 Map<Integer, Set<Cell>> slidingWindow = new HashMap<Integer, Set<Cell>>();
 
 for(int i = 0; i < n; i++){
  for(int j = 0; j < m; j++){
   if(slidingWindow.containsKey(mat[i][j])){
    for(Cell c : slidingWindow.get(mat[i][j])){
     int manhattanDist = Math.abs(i - c.row)+Math.abs(j - c.col);
     
     if(manhattanDist <= k){
      return true;
     }
     
     if(i - c.row > k){
      slidingWindow.remove(c);
     }
    }
    
    slidingWindow.get(mat[i][j]).add(new Cell(i, j));
   }
   else{
    slidingWindow.put(mat[i][j], new HashSet<Cell>());
    slidingWindow.get(mat[i][j]).add(new Cell(i, j));
   }
  }
 }
 
 return false;
}

Twenty Percent Knowledge

Sunday, July 10, 2016

Find duplication within k indices in a matrix

No comments: