CareerCup

I think of multiple ways to solve this.
1) start traversing matrix, insert k node into binary tree and keep it balanced.Create queue and add the element in that as well.
Before adding new element, search binary tree if element with same value found thats the answer. If not then continue.
After k elements, when new elements comes,dequeue from queue, remove that element from binary search tree, search inside binary search tree for same value elements, if not found add element in queue and binary search tree as well.
Time Complexity nlong
N for traversing matrix elements (here n is total number of elements in matrix)
logn for insertion, deletion in binary search tree (insertion and search can be done on one go)

2) Same approach can be done using hash table for insertion n deletion. Hashtable will contain k elements.

LinkedHashSet (window size = k)
remove element when window reaches size k

I think using a HashSet (java) will do the trick. It implements the Set interface so uniqueness is guaranteed.
The code below will run in worst case O(i*j) time, but I THINK this is a mandatory step anyway to read the matrix. All other functions are O(1) time.
Note: no -ve K or other error condition checks.

public boolean findDuplicateWithinIndex(int[][] input, int k)
	{
		int currentK = 0;
		for(int i = 0; i < input.length-1; i++)
		{
			for(int j=0; j < input[i].length-1; j++)
			{
				Integer cell = input[i][j];
				System.out.println(cell.hashCode());
				
				if(!hs.add(cell)) //collision
				{
					if(currentK < k) //found collision within k indices
						return true;
				}
				if(currentK < k)
					currentK++;
				else
					currentK = 0; //reset if we've surpassed K
			}
		}
		return false; //no collision within K indices.

Sample input:

int[][] findDuplicateInput = new int[][] { { 1,2,3,4} , { 5, 6, 3, 8 }, {9, 2, 11, 12 } };
		DuplicateEntriesWithinIndex duplicate = new DuplicateEntriesWithinIndex();
		int k = 9;
		boolean found = duplicate.findDuplicateWithinIndex(findDuplicateInput, k);//no collision
		if(found)
			System.out.println("Find duplicate: " + k);
		else
			System.out.println("No dupes.");

Output:
Dupe found at 9