Posted on For example, a=[1, 2, 3, 1, 3, 5] then for k ≤ 1 return false as no duplicates in k index away. For k=2 we return true as 3 is repeated in 2 distance away. Similarly for k ≥ 3 we return true as both 1 and 3 are repeated. In case of 2D array or matrix, for example, mat = 1 2 3 4 k = 1 Output: false Explanation: no duplicates within 1 manhattan distance. mat = 1 1 3 4 k = 0 Output: false Explanation: within 0 distance there can't be any duplicates trivially mat = 1 1 3 4 k = 1 Output: true Explanation: 1 is duplicated within 1 manhattan distance. mat = 1 2 3 3 4 1 k=3 Output: true Explanation: Both 1 and 3 are duplicated within 3 manhattan distance. mat = 1 2 3 6 1 7 k=1 Output: false Explanation: no duplicates within 1 manhattan distance. mat = 1 2 3 6 1 7 k=2 Output: true Explanation: 1 is duplicated within 2 manhattan distance. Note that Manhattan Distance within two points in an 2-dimensional grid is simply |p1.x-p2.x|+|p1.y-p2.
Read full article from Duplicates Within K Distance in Array/Matrix/2D Array - Algorithms and Problem SolvingAlgorithms and Problem Solving
No comments:
Post a Comment