Untitled — Python Coding — Nerchuko Academy

Euclidean Distance

EASY

Write a Python function to calculate the Euclidean distance between two points (P and Q) in N-dimensional space. The points can be represented as lists or tuples of numbers (e.g., p1 = [x1, y1, z1], p2 = [x2, y2, z2]).

The formula for Euclidean distance between points P=(p₁, p₂, ..., p_n) and Q=(q₁, q₂, ..., q_n) is:

Distance(P, Q) = √ [ ∑_i=1ⁿ (p_i - q_i)² ]

Discuss both a solution using basic Python loops and a more efficient solution using NumPy.

Examples:

Example 1 (2D):

Input: p1 = [1, 2], p2 = [4, 6]
Output: 5.0
Explanation: sqrt((4-1)^2 + (6-2)^2) = sqrt(3^2 + 4^2) = sqrt(9 + 16) = sqrt(25) = 5.0

Example 2 (3D):

Input: p1 = (0, 0, 0), p2 = (3, 4, 5)
Output: 7.0710678118654755
Explanation: sqrt(3^2 + 4^2 + 5^2) = sqrt(9 + 16 + 25) = sqrt(50)

Constraints:

Input points p1 and p2 will be lists or tuples of numbers.
p1 and p2 will have the same length (number of dimensions).
The number of dimensions will be at least 1.

Function Signature (Python):

from typing import List, Tuple, Union
import math
import numpy as np # For NumPy solution

class Solution:
    def euclidean_distance(self, 
                             p1: Union[List[float], Tuple[float, ...]], 
                             p2: Union[List[float], Tuple[float, ...]]) -> float:
        # Your code here (e.g., using loops)
        pass

    def euclidean_distance_numpy(self, 
                                 p1: np.ndarray, 
                                 p2: np.ndarray) -> float:
        # Your NumPy-based code here
        pass

Solution: Euclidean Distance

The Goal: We want to calculate the "straight-line" distance between two points. If you have points (x1, y1) and (x2, y2) on a 2D plane, you might remember the distance formula from school: √((x2-x1)² + (y2-y1)²). Euclidean distance generalizes this to any number of dimensions.

For each dimension, we find the difference between the coordinates of the two points, square that difference, sum up all these squared differences, and finally take the square root of that sum.

Approach 1: Using Basic Python Loops

This approach iterates through the coordinates of the two points, calculates the squared difference for each dimension, sums them up, and then takes the square root.

import math
from typing import List, Tuple, Union

class Solution:
    def euclidean_distance_loop(self, 
                                  p1: Union[List[float], Tuple[float, ...]], 
                                  p2: Union[List[float], Tuple[float, ...]]) -> float:
        if len(p1) != len(p2):
            raise ValueError("Points must have the same number of dimensions.")
        
        sum_of_squared_differences = 0.0
        for coord1, coord2 in zip(p1, p2):
            difference = coord1 - coord2
            sum_of_squared_differences += difference ** 2
            
        return math.sqrt(sum_of_squared_differences)

# Example Usage (Loop):
# sol = Solution()
# print(sol.euclidean_distance_loop([1, 2], [4, 6]))  # Output: 5.0
# print(sol.euclidean_distance_loop((0,0,0), (3,4,5))) # Output: 7.071...

Complexity Analysis (Loop approach):

Time Complexity: O(N), where N is the number of dimensions. We iterate through the dimensions once.

Space Complexity: O(1), as we only use a few variables for the sum and loop.

Approach 2: Using NumPy (Optimal for Performance)

NumPy is optimized for numerical operations on arrays. It can perform element-wise operations much faster than Python loops for large arrays.

import numpy as np

class Solution:
    def euclidean_distance_numpy(self, 
                                 p1: np.ndarray, # Expects NumPy arrays
                                 p2: np.ndarray) -> float:
        # Convert to NumPy arrays if they are not already (optional, depends on function contract)
        # p1_arr = np.array(p1) 
        # p2_arr = np.array(p2)
        
        if p1.shape != p2.shape or p1.ndim != 1: # Assuming 1D arrays for points
            raise ValueError("Points must be 1D NumPy arrays of the same shape.")

        # Element-wise subtraction
        difference_vector = p1 - p2 
        # Or: np.subtract(p1, p2)
        
        # Square each element
        squared_differences = np.square(difference_vector)
        # Or: difference_vector ** 2
        
        # Sum of squared differences
        sum_squared_diff = np.sum(squared_differences)
        
        # Square root of the sum
        distance = np.sqrt(sum_squared_diff)
        
        return distance

    # More compact NumPy version:
    def euclidean_distance_numpy_compact(self, p1_in, p2_in) -> float:
        p1_arr = np.array(p1_in, dtype=np.float64) # Ensure float for operations
        p2_arr = np.array(p2_in, dtype=np.float64)
        if p1_arr.shape != p2_arr.shape or p1_arr.ndim != 1:
             raise ValueError("Points must be convertible to 1D NumPy arrays of the same shape.")
        return np.sqrt(np.sum(np.square(p1_arr - p2_arr)))
        # Also, np.linalg.norm(p1_arr - p2_arr) calculates the L2 norm (Euclidean distance)

# Example Usage (NumPy):
# sol = Solution()
# p1_np = np.array([1, 2])
# p2_np = np.array([4, 6])
# print(sol.euclidean_distance_numpy_compact(p1_np, p2_np)) # Output: 5.0

# p3_list = [0,0,0]
# p4_tuple = (3,4,5)
# print(sol.euclidean_distance_numpy_compact(p3_list, p4_tuple)) # Output: 7.071...

Complexity Analysis (NumPy approach):

Time Complexity: O(N), where N is the number of dimensions. NumPy operations (subtraction, squaring, sum, sqrt) are implemented in C and operate efficiently on entire arrays. Converting lists to NumPy arrays also takes O(N).

Space Complexity: O(N) if new arrays are created for intermediate results (like difference_vector, squared_differences). If inputs are already NumPy arrays and operations can be optimized, it might be lower for auxiliary space, but generally, new arrays are formed.

Key Takeaways for Interviews:

Formula Understanding: Clearly state or write down the Euclidean distance formula.
Loop-based (Brute Force): Show the basic Python loop implementation first. This demonstrates fundamental programming skills. Using zip() is a Pythonic way to iterate over pairs.
NumPy for Efficiency (Optimal): Then, present the NumPy solution, highlighting its conciseness and performance benefits due to vectorized operations. Mention functions like np.array(), np.subtract() (or -), np.square() (or **2), np.sum(), and np.sqrt().
np.linalg.norm(): For bonus points, mention that np.linalg.norm(p1 - p2) directly calculates the L2 norm (which is the Euclidean distance) and is often the most idiomatic NumPy way for this specific task.
Input Validation: Discuss the importance of checking if the input points have the same dimensions.
Data Types: For the NumPy solution, ensuring data is in a numeric (preferably float) NumPy array format is important for calculations.