Count shortest distance in array

Question

Given an array of integers, write a function to calculate the shortest distance between any two occurrences of the same integer. The function should return the minimum distance found, or -1 if no integer appears more than once. The input will be an array of integers, and the output should be a single integer representing the shortest distance.

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 recognize that a hash map (or dictionary) serves as the optimal data structure here. The problem can be analyzed as follows:

1. **Repeated Elements**: We need to track each integer's previous index to calculate distances when we encounter the same integer again.
2. **Linear Scan**: A single pass through the array allows us to update our hash map with the most recent index of each integer and compute distances on-the-fly, making this a good candidate for a hash map solution.
3. **Optimality**: The hash map allows O(1) average time complexity for insert and lookup operations, which is crucial to maintain efficiency while iterating through the array.

We will implement the solution as follows:

1. **Initialize a Hash Map**: This will store each integer as the key and its last seen index as the value.
2. **Initialize Variables**: Set a variable to track the minimum distance found (`min_distance`) and initialize it to a large value (e.g., infinity).
3. **Iterate Through the Array**: For each integer in the array:
   - If it is already in the hash map, calculate the distance from the last recorded index to the current index.
   - Update `min_distance` if the calculated distance is smaller.
   - Update the hash map with the current index of the integer.
4. **Final Check**: If `min_distance` remains unchanged (still infinity), return -1. Otherwise, return `min_distance`.

**Example Walkthrough**:
For the array `[1, 2, 3, 1, 2, 3]`, the process would unfold like this:
- At index 0: `1` seen, store {1: 0}
- At index 1: `2` seen, store {1: 0, 2: 1}
- At index 2: `3` seen, store {1: 0, 2: 1, 3: 2}
- At index 3: `1` seen again, calculate distance = 3 - 0 = 3, update `min_distance` = 3
- At index 4: `2` seen again, calculate distance = 4 - 1 = 3, `min_distance` remains 3
- At index 5: `3` seen again, distance = 5 - 2 = 3, `min_distance` remains 3
Final result is 3.

Here’s the Python implementation of the solution:
```python
def shortest_distance(arr):
    index_map = {}
    min_distance = float('inf')

for i, num in enumerate(arr):
        if num in index_map:
            distance = i - index_map[num]
            min_distance = min(min_distance, distance)
        index_map[num] = i

return min_distance if min_distance != float('inf') else -1
```
This code efficiently calculates the shortest distance between duplicate integers while maintaining clarity and conciseness.

The time and space complexity of our solution is as follows:
- **Time Complexity**: O(n), where n is the length of the array. We make a single pass through the array, and each operation involving the hash map (insertion and lookup) is O(1) on average.
- **Space Complexity**: O(n) in the worst case, where all elements are unique. The hash map could potentially store all elements of the array.

Consider the following edge cases:
1. **No Duplicates**: An array like `[1, 2, 3]` should return -1 since there are no repeating integers.
2. **All Identical Elements**: An array like `[4, 4, 4, 4]` should return 1, since the distance between the first two occurrences of 4 is 1.
3. **Single Element**: An array with a single element `[5]` should return -1.
4. **Empty Array**: An empty array `[]` should also return -1. These edge cases help ensure the robustness of our solution.

Count shortest distance in array

Elastic

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

Elastic 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