Determines whether a 2d-integer array contains duplicate values within k | allenlipeng47

Determines whether a 2d-integer array contains duplicate values within k | allenlipeng47
determines whether a 2d m*n integer array contains duplicate values within k indices of each other.

For example:
1 2
3 4
k = 1
Outout: no

1 1
3 4
k=0
Output: no

1 1
3 4
k=1
Output: Yes

1 2 3
3 4 1
k=3
Output: Yes

Let’s think about 1-d array [1  2  3  4  5  4  6 ]. Let k=2. An O(n) solution would be use a 2-size window to slide over  the array. Use hashset to store the elements in window:

Then, let’s think about 2-d array like below. And we know arr[1][4]==arr[3][4]==99

In this case, we can use a ‘+’ shape 2-d window to scan array. The whole process will be like below:

When k is odd, let’s say k=5. We can’t use regular ‘+’ shape window. Instead, we use similar one. A similar move will be like below:

A problem of this unregular shape window is that it will miss elements 22, which both stay in the same column and length is 5. It is easy to solve this issue. Every time when a new window is moved, we just check if there are elements equal in same column which has length 5.

The time complexity of this solution is O(m*n*k), space complexity is O(k^2).

Read full article from Determines whether a 2d-integer array contains duplicate values within k | allenlipeng47