Check if Duplicates Exist Within K Manhattan Distance in Matrix

Problem

Given an array or a 2D matrix of integers, determine if any value appears at least twice such that the two occurrences are within a distance of at most k (indices for array, Manhattan distance for matrix). Return true if such a duplicate exists, otherwise return false.

Examples

Example 1

Input:
mat = [
  [1, 2],
  [3, 4]
], k = 1
Output: false
Explanation: No duplicates within 1 Manhattan distance.

Example 2

Input:
mat = [
  [1, 1],
  [3, 4]
], k = 1
Output: true
Explanation: 1 is duplicated within 1 Manhattan distance.

Example 3

Input:
mat = [
  [1, 2, 3],
  [3, 4, 1]
], k = 3
Output: true
Explanation: Both 1 and 3 are duplicated within 3 Manhattan distance.

Note: Manhattan Distance between two points (x1, y1) and (x2, y2) is |x1-x2| + |y1-y2|.

Solution

Method 1 – Hash Map with Position Tracking

Intuition

For each value, keep track of all its recent positions. For every new occurrence, check if any previous occurrence is within k Manhattan distance.

Approach

1. Iterate through each cell in the matrix.
2. For each value, maintain a list of its recent positions (row, col).
3. For each previous position, check if the Manhattan distance to the current cell is ≤ k.
4. If yes, return true.
5. Optionally, prune positions that are too far in row to save space.
6. If no duplicates found, return false.

Code

C++

class Solution {
public:
  bool containsNearbyDuplicate(vector<vector<int>>& mat, int k) {
    int n = mat.size(), m = mat[0].size();
    unordered_map<int, vector<pair<int, int>>> pos;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        int val = mat[i][j];
        for (auto& p : pos[val]) {
          if (abs(i - p.first) + abs(j - p.second) <= k) return true;
        }
        pos[val].emplace_back(i, j);
      }
    }
    return false;
  }
};

Go

func containsNearbyDuplicate(mat [][]int, k int) bool {
  n, m := len(mat), len(mat[0])
  pos := map[int][][2]int{}
  for i := 0; i < n; i++ {
    for j := 0; j < m; j++ {
      v := mat[i][j]
      for _, p := range pos[v] {
        if abs(i-p[0])+abs(j-p[1]) <= k {
          return true
        }
      }
      pos[v] = append(pos[v], [2]int{i, j})
    }
  }
  return false
}
func abs(x int) int { if x < 0 { return -x }; return x }

Java

import java.util.*;
class Solution {
  public boolean containsNearbyDuplicate(int[][] mat, int k) {
    int n = mat.length, m = mat[0].length;
    Map<Integer, List<int[]>> pos = new HashMap<>();
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        int v = mat[i][j];
        if (!pos.containsKey(v)) pos.put(v, new ArrayList<>());
        for (int[] p : pos.get(v)) {
          if (Math.abs(i - p[0]) + Math.abs(j - p[1]) <= k) return true;
        }
        pos.get(v).add(new int[]{i, j});
      }
    }
    return false;
  }
}

Python

class Solution:
  def containsNearbyDuplicate(self, mat: list[list[int]], k: int) -> bool:
    from collections import defaultdict
    pos: dict[int, list[tuple[int, int]]] = defaultdict(list)
    n, m = len(mat), len(mat[0])
    for i in range(n):
      for j in range(m):
        v = mat[i][j]
        for pi, pj in pos[v]:
          if abs(i - pi) + abs(j - pj) <= k:
            return True
        pos[v].append((i, j))
    return False

Complexity

• ⏰ Time complexity: O(n * m * d), where d is the number of previous occurrences of a value (worst case O(nmk) if all values are the same, but usually much less).
• 🧺 Space complexity: O(n * m), for storing positions.