613. Shortest Distance in a Line
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 79.9%
Problem Breakdown
The problem asks us to find the shortest distance between any two points on a line given an array of integers representing the positions of these points. The input is an array of integers where each integer represents a point on a number line. The output should be a single integer representing the minimum distance between any two points in the array.
Inputs:
- An array of integers
pointswhere each element represents a position on a number line.
Outputs:
- A single integer representing the shortest distance between any two points.
Implicit Constraints or Tricky Edge Cases:
- The array can be empty, in which case the output should be 0 since there are no points to measure distance between.
- The array can contain duplicate values, meaning multiple points can occupy the same position on the line.
- Negative numbers are allowed, so the positions can be negative integers.
Intuition
The brute-force approach would involve checking every possible pair of points and calculating their distances. This would have a time complexity of O(n^2), which is inefficient for large arrays. The key insight to improve this is to sort the array first. Once sorted, the shortest distance will always be between two consecutive elements in the sorted array because sorting arranges the numbers in increasing order, minimizing the gap between adjacent numbers.
Approach
- Sort the Array: Sort the input array
pointsto arrange the positions in ascending order. - Initialize Minimum Distance: Set a variable
min_distanceto a large value (e.g., infinity) to keep track of the smallest distance found. - Iterate Through Consecutive Elements: Loop through the sorted array and calculate the distance between each pair of consecutive elements. Update
min_distanceif the current distance is smaller than the previously recorded minimum distance. - Return Result: After iterating through all pairs, return the value of
min_distance.
Complexity Analysis
- Time Complexity: O(n log n) due to the sorting step. The loop that follows has a linear time complexity of O(n).
- Space Complexity: O(1) if we sort the array in place (e.g., using Python’s built-in
sort()method). If we need to create a sorted copy, it would be O(n).
Solution
def shortest_distance(points):
if not points or len(points) < 2:
return 0
# Sort the points array
points.sort()
# Initialize minimum distance to infinity
min_distance = float('inf')
# Iterate through consecutive elements in the sorted array
for i in range(1, len(points)):
# Calculate distance between consecutive points
current_distance = points[i] - points[i - 1]
# Update minimum distance if current distance is smaller
if current_distance < min_distance:
min_distance = current_distance
return min_distance
Edge Cases Handled
- Empty Array: The function returns 0 immediately if the input array is empty.
- Single Element Array: The function also returns 0 if there’s only one element since no distance can be calculated.
- Duplicate Values: Sorting handles duplicates naturally, and the loop will correctly identify the smallest non-zero distance between any two identical points.
- Negative Numbers: The sorting and subtraction operations work correctly with negative numbers, ensuring accurate distance calculations.