Problem

You are writing an AI for a 2D map game. You are somewhere in a 2D grid, and there are coins strewn about over the map.

Given the position of all the coins and your current position, find the closest coin to you in terms of Manhattan distance. That is, you can move around up, down, left, and right, but not diagonally. If there are multiple possible closest coins, return any of them.

For example, given the following map, where you are x, coins are o, and empty spaces are . (top left is 0, 0):

1
2
3
4
5
6
7
8
9

------------
| . | . | x | . | o |
------------
| o | . | . | . | . |
------------
| o | . | . | . | o |
------------
| . | . | o | . | . |
------------

return (0, 4), since that coin is closest. This map would be represented in our question as:

1
2

Our position: (0, 2)
Coins: [(0, 4), (1, 0), (2, 0), (3, 2)]

Examples

Example 1

1
2
3

Input: position = (0, 2), coins = [(0, 4), (1, 0), (2, 0), (3, 2)]
Output: (0, 4)
Explanation: Manhattan distances: |(0-0)| + |(4-2)| = 2, |(1-0)| + |(0-2)| = 3, |(2-0)| + |(0-2)| = 4, |(3-0)| + |(2-2)| = 3. Minimum is 2 for coin (0, 4).

Example 2

1
2
3

Input: position = (1, 1), coins = [(0, 0), (2, 2), (1, 3)]
Output: (0, 0) or (2, 2)
Explanation: Manhattan distances: |(0-1)| + |(0-1)| = 2, |(2-1)| + |(2-1)| = 2, |(1-1)| + |(3-1)| = 2. All have same distance, any can be returned.

Example 3

1
2
3

Input: position = (2, 3), coins = [(2, 3)]
Output: (2, 3)
Explanation: Only one coin at the same position as player, distance = 0.

Example 4

1
2
3

Input: position = (5, 5), coins = [(0, 0), (10, 10), (3, 7)]
Output: (3, 7)
Explanation: Manhattan distances: |(0-5)| + |(0-5)| = 10, |(10-5)| + |(10-5)| = 10, |(3-5)| + |(7-5)| = 4. Minimum is 4 for coin (3, 7).

Example 5

1
2
3

Input: position = (0, 0), coins = []
Output: None
Explanation: No coins available, return None or empty result.

Solution

Method 1 - Linear Search with Manhattan Distance

Intuition

The key insight is that Manhattan distance between two points (x₁, y₁) and (x₂, y₂) is |x₁ - x₂| + |y₁ - y₂|. Since we need to find the closest coin, we can iterate through all coins, calculate their Manhattan distance from our position, and keep track of the coin with minimum distance. This is a straightforward brute force approach that works well given the typical size of coin collections in games.

Approach

  1. Handle Edge Cases: Check if coins list is empty, return None/null
  2. Initialize Tracking: Set minimum distance to infinity and closest coin to None
  3. Iterate Through Coins: For each coin position, calculate Manhattan distance
  4. Calculate Distance: Use formula |x₁ - x₂| + |y₁ - y₂| for current coin and player position
  5. Update Minimum: If current distance is smaller than minimum found, update both minimum distance and closest coin
  6. Continue Search: Process all coins to ensure we find the global minimum
  7. Return Result: Return the coin position with minimum Manhattan distance

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    vector<int> findClosestCoin(vector<int>& position, vector<vector<int>>& coins) {
        if (coins.empty()) return {};
        
        int minDist = INT_MAX;
        vector<int> ans;
        
        for (auto& coin : coins) {
            int dist = manhattanDistance(position, coin);
            if (dist < minDist) {
                minDist = dist;
                ans = coin;
            }
        }
        
        return ans;
    }
    
private:
    int manhattanDistance(vector<int>& pos1, vector<int>& pos2) {
        return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1]);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func FindClosestCoin(position []int, coins [][]int) []int {
    if len(coins) == 0 {
        return nil
    }
    
    minDist := math.MaxInt32
    var ans []int
    
    for _, coin := range coins {
        dist := manhattanDistance(position, coin)
        if dist < minDist {
            minDist = dist
            ans = coin
        }
    }
    
    return ans
}

func manhattanDistance(pos1, pos2 []int) int {
    return abs(pos1[0]-pos2[0]) + abs(pos1[1]-pos2[1])
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int[] findClosestCoin(int[] position, int[][] coins) {
        if (coins.length == 0) return null;
        
        int minDist = Integer.MAX_VALUE;
        int[] ans = null;
        
        for (int[] coin : coins) {
            int dist = manhattanDistance(position, coin);
            if (dist < minDist) {
                minDist = dist;
                ans = coin;
            }
        }
        
        return ans;
    }
    
    private int manhattanDistance(int[] pos1, int[] pos2) {
        return Math.abs(pos1[0] - pos2[0]) + Math.abs(pos1[1] - pos2[1]);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def findClosestCoin(self, position: List[int], coins: List[List[int]]) -> Optional[List[int]]:
        if not coins:
            return None
        
        minDist = float('inf')
        ans: Optional[List[int]] = None
        
        for coin in coins:
            dist = self._manhattanDistance(position, coin)
            if dist < minDist:
                minDist = dist
                ans = coin
        
        return ans
    
    def _manhattanDistance(self, pos1: List[int], pos2: List[int]) -> int:
        return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])

Complexity

  • ⏰ Time complexity: O(n) where n is the number of coins, as we need to check the distance to each coin once.
  • 🧺 Space complexity: O(1) as we only use a constant amount of extra space for tracking the minimum distance and closest coin.

Method 2 - Optimized with Early Termination

Intuition

We can optimize the basic approach by adding early termination conditions. If we find a coin at the same position as the player (distance = 0), we can immediately return it since no distance can be smaller. Additionally, we can sort coins by their approximate distance and potentially terminate early in some cases, though the sorting overhead may not always be beneficial for small datasets.

Approach

  1. Handle Edge Cases: Return None if no coins available
  2. Early Termination Check: If any coin is at player position, return immediately
  3. Initialize Tracking: Set up minimum distance tracking and result storage
  4. Optimized Iteration: Check each coin with early termination for distance 0
  5. Distance Calculation: Use Manhattan distance formula with short-circuit evaluation
  6. Update Strategy: Only update result when a strictly better distance is found
  7. Result Return: Return the optimal coin position found

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

class Solution {
public:
    vector<int> findClosestCoinOptimized(vector<int>& position, vector<vector<int>>& coins) {
        if (coins.empty()) return {};
        
        int minDist = INT_MAX;
        vector<int> ans;
        
        for (auto& coin : coins) {
            // Early termination if coin is at player position
            if (coin[0] == position[0] && coin[1] == position[1]) {
                return coin;
            }
            
            int dist = manhattanDistance(position, coin);
            if (dist < minDist) {
                minDist = dist;
                ans = coin;
            }
        }
        
        return ans;
    }
    
    // Version with sorting optimization for large datasets
    vector<int> findClosestCoinSorted(vector<int>& position, vector<vector<int>>& coins) {
        if (coins.empty()) return {};
        
        // Sort coins by approximate distance (sum of coordinates difference)
        sort(coins.begin(), coins.end(), [&](const vector<int>& a, const vector<int>& b) {
            int distA = abs(a[0] - position[0]) + abs(a[1] - position[1]);
            int distB = abs(b[0] - position[0]) + abs(b[1] - position[1]);
            return distA < distB;
        });
        
        int minDist = manhattanDistance(position, coins[0]);
        vector<int> ans = coins[0];
        
        // Check remaining coins, can terminate early if distance increases
        for (int i = 1; i < coins.size(); i++) {
            int dist = manhattanDistance(position, coins[i]);
            if (dist < minDist) {
                minDist = dist;
                ans = coins[i];
            }
        }
        
        return ans;
    }
    
private:
    int manhattanDistance(vector<int>& pos1, vector<int>& pos2) {
        return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1]);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

func FindClosestCoinOptimized(position []int, coins [][]int) []int {
    if len(coins) == 0 {
        return nil
    }
    
    minDist := math.MaxInt32
    var ans []int
    
    for _, coin := range coins {
        // Early termination if coin is at player position
        if coin[0] == position[0] && coin[1] == position[1] {
            return coin
        }
        
        dist := manhattanDistance(position, coin)
        if dist < minDist {
            minDist = dist
            ans = coin
        }
    }
    
    return ans
}

func FindClosestCoinWithIndex(position []int, coins [][]int) ([]int, int) {
    if len(coins) == 0 {
        return nil, -1
    }
    
    minDist := math.MaxInt32
    var ans []int
    ansIndex := -1
    
    for i, coin := range coins {
        if coin[0] == position[0] && coin[1] == position[1] {
            return coin, i
        }
        
        dist := manhattanDistance(position, coin)
        if dist < minDist {
            minDist = dist
            ans = coin
            ansIndex = i
        }
    }
    
    return ans, ansIndex
}

func manhattanDistanceOpt(pos1, pos2 []int) int {
    dx := pos1[0] - pos2[0]
    if dx < 0 {
        dx = -dx
    }
    
    dy := pos1[1] - pos2[1]
    if dy < 0 {
        dy = -dy
    }
    
    return dx + dy
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

class Solution {
    public int[] findClosestCoinOptimized(int[] position, int[][] coins) {
        if (coins.length == 0) return null;
        
        int minDist = Integer.MAX_VALUE;
        int[] ans = null;
        
        for (int[] coin : coins) {
            // Early termination if coin is at player position
            if (coin[0] == position[0] && coin[1] == position[1]) {
                return coin;
            }
            
            int dist = manhattanDistance(position, coin);
            if (dist < minDist) {
                minDist = dist;
                ans = coin;
            }
        }
        
        return ans;
    }
    
    public static class CoinResult {
        public final int[] coin;
        public final int index;
        public final int distance;
        
        public CoinResult(int[] coin, int index, int distance) {
            this.coin = coin;
            this.index = index;
            this.distance = distance;
        }
    }
    
    public CoinResult findClosestCoinWithDetails(int[] position, int[][] coins) {
        if (coins.length == 0) return null;
        
        int minDist = Integer.MAX_VALUE;
        int[] ans = null;
        int ansIndex = -1;
        
        for (int i = 0; i < coins.length; i++) {
            int[] coin = coins[i];
            
            if (coin[0] == position[0] && coin[1] == position[1]) {
                return new CoinResult(coin, i, 0);
            }
            
            int dist = manhattanDistance(position, coin);
            if (dist < minDist) {
                minDist = dist;
                ans = coin;
                ansIndex = i;
            }
        }
        
        return new CoinResult(ans, ansIndex, minDist);
    }
    
    private int manhattanDistance(int[] pos1, int[] pos2) {
        return Math.abs(pos1[0] - pos2[0]) + Math.abs(pos1[1] - pos2[1]);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Solution:
    def findClosestCoinOptimized(self, position: List[int], coins: List[List[int]]) -> Optional[List[int]]:
        if not coins:
            return None
        
        minDist = float('inf')
        ans: Optional[List[int]] = None
        
        for coin in coins:
            # Early termination if coin is at player position
            if coin[0] == position[0] and coin[1] == position[1]:
                return coin
            
            dist = self._manhattanDistance(position, coin)
            if dist < minDist:
                minDist = dist
                ans = coin
        
        return ans
    
    def findClosestCoinWithDetails(self, position: List[int], coins: List[List[int]]) -> Optional[Tuple[List[int], int, int]]:
        if not coins:
            return None
        
        minDist = float('inf')
        ans: Optional[List[int]] = None
        ansIndex = -1
        
        for i, coin in enumerate(coins):
            if coin[0] == position[0] and coin[1] == position[1]:
                return (coin, i, 0)
            
            dist = self._manhattanDistance(position, coin)
            if dist < minDist:
                minDist = dist
                ans = coin
                ansIndex = i
        
        return (ans, ansIndex, minDist) if ans else None
    
    def findClosestCoinsSorted(self, position: List[int], coins: List[List[int]]) -> List[List[int]]:
        if not coins:
            return []
        
        # Sort coins by Manhattan distance
        coinsWithDist = [(coin, self._manhattanDistance(position, coin)) for coin in coins]
        coinsWithDist.sort(key=lambda x: x[1])
        
        minDist = coinsWithDist[0][1]
        return [coin for coin, dist in coinsWithDist if dist == minDist]
    
    def _manhattanDistance(self, pos1: List[int], pos2: List[int]) -> int:
        return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])

Complexity

  • ⏰ Time complexity: O(n) for the optimized linear search, where n is the number of coins. The sorted version has O(n log n) due to sorting overhead.
  • 🧺 Space complexity: O(1) for the basic optimized version, O(n) for the sorted version that creates additional data structures.