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);
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;
}
What is the space complexity for your 2D matrix one?
ReplyDeleteAnd time complexisyt?
Deletetime: the O(matrix-size) which is a upper bound.
Deletespace: O(matrix-size) which is also upper bound, i can shrink the hash when loop through the matrix by removing the rows which is above i-k, but it may not gain too much, which depends on k.
Deleteyou have below code inside the loop. You think this going to be O(1) time?
Deletefor(Pos p: set){
if(Math.abs(p.getRow() - row) + Math.abs(p.getCol()-col) <=k ){
return true;
}
}
I agree with your space complexity. I think you should try this way.
it is under condition:
Deleteif(store.containsKey(val)){
Set set = store.get(val);
for(Pos p: set){
if(Math.abs(p.getRow() - row) + Math.abs(p.getCol()-col) <=k ){
return true;
}
}
set.add(new Pos(row, col));
}.
that "for" loop would not equal to matrix size, smaller than size of each row or column, i believe.
now I think the for loop could be very expensive. i need to optimize it.
Deleteu can refer my blog. but the logic could be a bit complex.
Deleteuh... we can simply remove the element during the for(Pos p:set) loop.
Deletei don't understand. do you have updated code?
Deletefor(Pos p: set){
Deleteif(Math.abs(p.getRow() - row) + Math.abs(p.getCol()-col) <=k ){
return true;
}
if(row - p.getRow() > k)
set.remove(p);
}
by the way, the above code is not 100% safe, it should use iterator to do the remove.
Delete