Find shortest distance in array

Question

Given an array of integers, write a function to find the shortest distance between any two occurrences of the same integer. The function should return the minimum distance as an integer, or -1 if no such occurrences exist.

Codemia · Accepted Answer

To solve the problem of finding the shortest distance between any two occurrences of the same integer in an array, we can leverage the **hash map** (dictionary in Python) approach. This is optimal because it allows us to keep track of the last seen index of each integer in a single pass through the array. The pattern here is akin to the **sliding window** technique, where we maintain a dynamic set of previously seen elements and their indices, allowing us to calculate distances efficiently. By using this approach, we can avoid the O(n^2) complexity of a naive solution that checks every pair of occurrences.

1. Initialize an empty dictionary to store the last seen index of each integer.
2. Initialize a variable to store the minimum distance, set it to infinity initially.
3. Iterate through the array with an index:
   - For each integer, check if it exists in the dictionary:
     - If it does, calculate the distance from its last seen index to the current index.
     - Update the minimum distance if this distance is smaller.
     - Update the integer's last seen index in the dictionary to the current index.
4. After finishing the iteration, check if the minimum distance was updated:
   - If it remained as infinity, return -1 (indicating no duplicates were found).
   - Otherwise, return the minimum distance found.

**Example:** For the array `[1, 2, 1, 3, 2, 1]`,
- At index 0, we see `1`, store it.
- At index 1, we see `2`, store it.
- At index 2, we see `1` again; distance = 2 - 0 = 2, update min distance to 2.
- Continue this until we find the shortest distance.

```python
def shortest_distance(arr):
    last_seen = {}
    min_distance = float('inf')

for index, value in enumerate(arr):
        if value in last_seen:
            distance = index - last_seen[value]
            min_distance = min(min_distance, distance)
        last_seen[value] = index

return min_distance if min_distance != float('inf') else -1
```

The time complexity of this solution is O(n), where n is the number of elements in the array, since we make a single pass through the array. The space complexity is O(k), where k is the number of unique integers in the array, due to the storage in the dictionary. This is efficient given the problem constraints, as we are leveraging the properties of hash maps for quick lookups.

1. **All Unique Elements**: If the array contains all unique integers, e.g., `[1, 2, 3, 4]`, the function should return -1.
2. **Single Element Array**: An array like `[1]` should also return -1 since there are no duplicates.
3. **Multiple Duplicates**: Arrays like `[1, 1, 1, 1]` should return 1, as the closest duplicates are adjacent.
4. **Negative or Large Integers**: The algorithm should handle negative integers or very large integers properly, e.g., `[-1, -2, -1]` should return 2.

Find shortest distance in array

Airbnb

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Airbnb Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string