2613. Beautiful Pairs

HardGeometryArrayMathDivide and ConquerOrdered SetSorting
Leetcode Link

Problem Description

You are provided with two integer arrays nums1 and nums2 that both have the same length. The task is to find a pair of indices (i, j) where i < j that makes the pair beautiful. A pair is considered beautiful if the expression |nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| results in the smallest possible value when compared to this value for all other pairs of distinct indices. In other words, the Manhattan distance between points (nums1[i], nums2[i]) and (nums1[j], nums2[j]) should be the smallest of all possible pairs.

If there is more than one such beautiful pair, you are asked to return the lexicographically smallest one. Recall that a pair (i1, j1) is said to be lexicographically smaller than another pair (i2, j2) if either i1 < i2, or if i1 == i2 then j1 < j2.

In essence, you are being asked to find the closest two points (in terms of Manhattan distance) in the Cartesian plane, where the x and y coordinates of the points are given by nums1 and nums2 respectively, and if there are several pairs of points with the same smallest distance, return the pair with the smallest indices.

Intuition

The problem at its core is a geometric one: it reduces to finding two points in a plane that are closest to each other in terms of Manhattan distance, which is simply the sum of the absolute differences of their x-coordinates and y-coordinates. If a pair of identical points exists (i.e., points with the same x and y values), then this pair is trivially the closest pair, with a distance of 0, and its indices form the beautiful pair.

When no such identical points exist, the solution is found using the "divide and conquer" technique, frequently used in computational geometry to solve nearest-neighbor problems.

Here's the approach:

  1. Check if there are any duplicate points. If there are duplicates, the problem is trivially solved by returning the indices of the duplicate points since identical points have a distance of 0, which is the smallest possible. This requires the maintenance of a hash map.

  2. If there are no duplicates, sort all points based on their x-coordinates. This ordered arrangement enables us to consider potential nearest neighbors only within a bounded x-coordinate range, regarding the currently found minimum distance as the limit to move in the x-axis direction.

  3. Apply divide and conquer. Divide the set of points into two halves, recursively find the smallest pairs in both halves, and then merge the results, considering pairs that cross the halves. Since points are already sorted by x-coordinate, the cross-pair check only needs to consider a band as wide as the current minimum distance around the midpoint in the x-direction.

  4. When checking cross-pairs, one optimization is to sort these points by their y-coordinates to facilitate early termination during comparisons. This is because once the difference in y-coordinates between a potential pair exceeds the current minimum distance, we can stop considering further pairs since they are guaranteed to have a larger Manhattan distance.

  5. The complexity of this algorithm is time-efficient, taking O(n log n) time, where n is the number of points. It's important to note that the sorting step and the divide and conquer step contribute to this complexity. The space complexity is O(n), primarily for storing the points and their corresponding indices.

Following this intuition and maintaining rigorous checks to determine the lexicographically smallest beautiful pair results in a solution that meets the conditions set forth by the problem.

Learn more about Math, Divide and Conquer and Sorting patterns.

Solution Approach

The solution approach employs divide and conquer as its main algorithm, leveraging sorting and efficient comparison strategies to achieve the overall time complexity of O(n log n).

Here's a step-by-step explanation of the implementation based on the reference solution provided:

  1. Handle Duplicates: Before starting with divide and conquer, it searches for duplicates in the points described by nums1 and nums2. It employs a hash map (pl) to store indices of identical points. If duplicates are found, they instantly form the lexicographically smallest beautiful pair.

  2. Sort and Prepare Points: Points are prepared with their indices attached (x, y, index) and sorted based on their x-coordinates.

  3. Recursive Divide and Conquer (dfs function):

    • Base Case: If the segment of points to consider is size 1 or empty (l >= r), it returns inf to signal that there's no pair of points within this segment.
    • Divide: Find the middle index m between l and r and recursively call the dfs function on the left and right segments to find the smallest distances and the respective pairs for each segment.
    • Conquer: Compare the smallest distances returned from the left and right segments, keeping the lexicographically smallest pair.

  4. Merge Strategy for Cross-Pairs:

    • Prepare a new array t of points within the band of the minimum distance d1 on both sides of the middle x-coordinate. This contains potential candidates for the closest cross-pair.
    • Sort the array t by y-coordinate to optimize further comparisons for cross-pairs.
    • Compare each pair in the sorted array t within d1 distance, looking for a smaller Manhattan distance. If such a distance is found, update the minimum distance and the beautiful pair indices accordingly.

  5. Termination Condition for Y-Axis Comparisons:

    • Utilize the fact that if the y-coordinate difference between two points exceeds the current minimum distance, then subsequent points will not be closer, allowing the algorithm to terminate early for that segment and move on to the next one.

  6. Return Beautiful Pair:

    • After considering all segments and cross-segment pairs, return the indices of the beautiful pair found.
def beautifulPair(self, nums1: List[int], nums2: List[int]) -> List[int]:
    # Reference implementation in python
    # The code uses helper functions like `dfs` and `dist` to perform [divide and conquer](/problems/divide_and_conquer_intro) and compute the Manhattan distance, respectively.

The data structure primarily used is a list to store point coordinates and indices, and a hash map for easy lookup of duplicate points. The algorithm respects the confines of the List data type within the Python language, using it to store and sort points based on coordinates.

This solution approach is meticulous in ensuring that the lexicographically smallest pair is found, by ensuring the correct comparisons are made not only on the Manhattan distance but also on the indices whenever distances are found to be equal.

In essence, the implementation marries the divide and conquer algorithm with sorting and efficient traversal techniques to address the computational geometry problem it represents.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example with the following input arrays nums1 and nums2 to illustrate the solution approach:

nums1 = [1, 3, 2] nums2 = [4, 6, 5]

First, since the solution starts by looking for duplicates and there are none in this trivial case, we do not have an instant solution from step 1. Therefore, we proceed to the next steps.

The points represented by these arrays are (1, 4), (3, 6), and (2, 5). When we prepare these points, we associate each with its index:

points = [(1, 4, 0), (3, 6, 1), (2, 5, 2)]

Following the solution approach:

  1. Sort Points: We sort the points list based on the x-coordinate.

    After sorting: sorted_points = [(1, 4, 0), (2, 5, 2), (3, 6, 1)]

  2. Recursive Divide and Conquer: We call the recursive function dfs for the points, starting with the full array sorted_points.

    • Since the list is of size 3, we have a valid segment to split. We find the middle index, which is m = 1, and consider point (2, 5, 2) to be the middle point.

    • We recursively call dfs on the left segment [(1, 4, 0)] and the right segment [(3, 6, 1)], finding their minimum beautiful pairs and distances (which in this case would be infinity, as they are single points).

  3. Conquer: Now we have to merge the results from the steps taken for the left and right segments. There are no beautiful pairs yet because both segments had only one point.

  4. Merge Strategy for Cross-Pairs:

    • We prepare an array t of points within the minimum distance around the middle point's x-coordinate. However, as we do not have a minimum distance yet (since d1 is infinity from both subarrays), we take all points of the sorted array.

    • We sort t based on the y-coordinate, but since our example is small, the sorting doesn't change the order of points significantly.

    • We now start to compare points to find a smaller Manhattan distance. The pairs we can compare are (0, 2) and (1, 2).

      • Pair (0, 2) gives the Manhattan distance |1-2| + |4-5| = 2.
      • Pair (1, 2) gives the Manhattan distance |3-2| + |6-5| = 2.

      Both pairs yield the same Manhattan distance (2), but pair (0, 2) has the lexicographically smallest index.

  5. Terminate Y-Axis Comparisons: Since we found our possible pairs and none of the y differences exceed our minimum distance, we don't have to terminate early in this example.

  6. Return Beautiful Pair: After all is said and done, the smallest Manhattan distance found is 2, with the pair of indices being (0, 2). This means the beautiful pair based on the provided arrays nums1 and nums2 is [(1, 4), (2, 5)] or more specifically the indices [0, 2]. This is the output the actual implementation aforementioned would provide.

The above steps illustrate how the divide and conquer strategy coupled with a sorting and a smart traversing technique can efficiently find the closest pair of points in a plane, defined by their Manhattan distance.

Solution Implementation

1from typing import List
2from collections import defaultdict
3from math import inf
4
5class Solution:
6    def beautifulPair(self, nums1: List[int], nums2: List[int]) -> List[int]:
7        # Calculates the Manhattan distance between two points (x1, y1) and (x2, y2)
8        def calculate_distance(x1: int, y1: int, x2: int, y2: int) -> int:
9            return abs(x1 - x2) + abs(y1 - y2)
10
11        # The DFS function to find the smallest distance and respective indices.
12        def dfs(left: int, right: int):
13            if left >= right:
14                return inf, -1, -1
15          
16            mid = (left + right) // 2
17            x = points[mid][0]
18            distance_left, left_pi, left_pj = dfs(left, mid)
19            distance_right, right_pi, right_pj = dfs(mid + 1, right)
20          
21            # Choose the smaller distance or, in case of a tie, the smaller index pair.
22            if distance_left > distance_right or (distance_left == distance_right and (left_pi > right_pi or (left_pi == right_pi and left_pj > right_pj))):
23                distance_left, left_pi, left_pj = distance_right, right_pi, right_pj
24              
25            # Include points with x-coordinate differences within the minimum distance.
26            candidates = [p for p in points[left : right + 1] if abs(p[0] - x) <= distance_left]
27            candidates.sort(key=lambda p: p[1])
28          
29            # Consider all candidate pairs within the required range.
30            for i in range(len(candidates)):
31                for j in range(i + 1, len(candidates)):
32                    if candidates[j][1] - candidates[i][1] > distance_left:
33                        break
34                    index_i, index_j = sorted([candidates[i][2], candidates[j][2]])
35                    distance = calculate_distance(candidates[i][0], candidates[i][1], candidates[j][0], candidates[j][1])
36                  
37                    # If a smaller distance or lexicographically smaller pair of indices is found, update values.
38                    if distance < distance_left or (distance == distance_left and (index_i < left_pi or (index_i == left_pi and index_j < left_pj))):
39                        distance_left, left_pi, left_pj = distance, index_i, index_j
40            return distance_left, left_pi, left_pj
41
42        # Store points and their index positions
43        point_location = defaultdict(list)
44        for idx, (x, y) in enumerate(zip(nums1, nums2)):
45            point_location[(x, y)].append(idx)
46      
47        points = []
48        for idx, (x, y) in enumerate(zip(nums1, nums2)):
49            # If we have more than one of the same point, return the indices.
50            if len(point_location[(x, y)]) > 1:
51                return [idx, point_location[(x, y)][1]]
52            points.append((x, y, idx))
53      
54        points.sort()
55      
56        # Find the pair with the smallest distance using recursive subdivision.
57        _, index1, index2 = dfs(0, len(points) - 1)
58        return [index1, index2]
59
60# Example usage:
61# solution = Solution()
62# print(solution.beautifulPair([1, 2, 3], [2, 3, 4]))  # Output: The indices of the 'beautiful pair'
63
1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5
6class Solution {
7    private List<int[]> points = new ArrayList<>();
8
9    // Main method to find the 'beautiful pair' according to the problem statement
10    public int[] beautifulPair(int[] nums1, int[] nums2) {
11        int length = nums1.length;
12        Map<Long, List<Integer>> pairsList = new HashMap<>();
13        for (int i = 0; i < length; ++i) {
14            long compositeNum = computeCompositeNumber(nums1[i], nums2[i]);
15            // Map the composite number to its indices in the arrays
16            pairsList.computeIfAbsent(compositeNum, k -> new ArrayList<>()).add(i);
17        }
18        for (int i = 0; i < length; ++i) {
19            long compositeNum = computeCompositeNumber(nums1[i], nums2[i]);
20            // Quick check for a beautiful pair if more than one occurrence is found
21            if (pairsList.get(compositeNum).size() > 1) {
22                return new int[] {i, pairsList.get(compositeNum).get(1)};
23            }
24            // Store points along with their original indexes for later processing
25            points.add(new int[] {nums1[i], nums2[i], i});
26        }
27        // Sort points based on the value of the first element
28        points.sort((a, b) -> a[0] - b[0]);
29        // Recursively find the beautiful pair by using divide-and-conquer strategy
30        int[] answer = findClosestPair(0, points.size() - 1);
31        // Return the indices of the pair found
32        return new int[] {answer[1], answer[2]};
33    }
34
35    // Helper method to create a composite number for easy mapping
36    private long computeCompositeNumber(int x, int y) {
37        return x * 100000L + y;
38    }
39
40    // Method to calculate Manhattan distance between two points
41    private int distance(int x1, int y1, int x2, int y2) {
42        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
43    }
44
45    // Helper method that implements the divide-and-conquer approach to find the closest pair
46    private int[] findClosestPair(int left, int right) {
47        if (left >= right) {
48            // Return maximum possible value if no pair found
49            return new int[] {Integer.MAX_VALUE, -1, -1};
50        }
51        int middle = (left + right) >> 1; // Find the midpoint
52        int pivotX = points.get(middle)[0];
53        // Recursive calls to find the smallest pair in each half
54        int[] resultLeft = findClosestPair(left, middle);
55        int[] resultRight = findClosestPair(middle + 1, right);
56        // Determine the smaller distance of the pairs found
57        if (resultLeft[0] > resultRight[0]
58            || (resultLeft[0] == resultRight[0] && (resultLeft[1] > resultRight[1]
59            || (resultLeft[1] == resultRight[1] && resultLeft[2] > resultRight[2])))) {
60            resultLeft = resultRight;
61        }
62        List<int[]> filteredPoints = new ArrayList<>();
63        for (int i = left; i <= right; ++i) {
64            // Filtering points that can possibly form the closest pair
65            if (Math.abs(points.get(i)[0] - pivotX) <= resultLeft[0]) {
66                filteredPoints.add(points.get(i));
67            }
68        }
69        // Sort the filtered points based on the second dimension
70        filteredPoints.sort((a, b) -> a[1] - b[1]);
71        for (int i = 0; i < filteredPoints.size(); ++i) {
72            for (int j = i + 1; j < filteredPoints.size(); ++j) {
73                // No farther points need to be checked after a certain threshold
74                if (filteredPoints.get(j)[1] - filteredPoints.get(i)[1] > resultLeft[0]) {
75                    break;
76                }
77                int firstIndex = Math.min(filteredPoints.get(i)[2], filteredPoints.get(j)[2]);
78                int secondIndex = Math.max(filteredPoints.get(i)[2], filteredPoints.get(j)[2]);
79                // Calculate the Manhattan distance between the pair of points
80                int d = distance(filteredPoints.get(i)[0], filteredPoints.get(i)[1],
81                                 filteredPoints.get(j)[0], filteredPoints.get(j)[1]);
82                // Update the result if a closer pair is found
83                if (d < resultLeft[0] || (d == resultLeft[0] && (firstIndex < resultLeft[1]
84                    || (firstIndex == resultLeft[1] && secondIndex < resultLeft[2])))) {
85                    resultLeft = new int[] {d, firstIndex, secondIndex};
86                }
87            }
88        }
89        return resultLeft;
90    }
91}
92
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4#include <functional>
5#include <tuple>
6#include <cmath>
7
8using namespace std;
9
10class Solution {
11public:
12    // Function to compute a unique hash for a pair of numbers
13    long long hashPair(int x, int y) {
14        return static_cast<long long>(x) * 100000LL + y;
15    }
16
17    // Function to calculate manhattan distance between two points
18    int manhattanDistance(int x1, int y1, int x2, int y2) {
19        return abs(x1 - x2) + abs(y1 - y2);
20    }
21
22    // Function to find a beautiful pair in two vectors
23    vector<int> beautifulPair(vector<int>& nums1, vector<int>& nums2) {
24        int n = nums1.size(); // The length of the input vectors
25        unordered_map<long long, vector<int>> pairsLocation;
26      
27        // map each pair to its indices in nums1 and nums2
28        for (int i = 0; i < n; ++i) {
29            pairsLocation[hashPair(nums1[i], nums2[i])].push_back(i);
30        }
31      
32        vector<tuple<int, int, int>> points; // Store nums1[i], nums2[i], and index i as a tuple
33      
34        // Search for an immediate beautiful pair with more than one occurrence
35        for (int i = 0; i < n; ++i) {
36            long long hashValue = hashPair(nums1[i], nums2[i]);
37            if (pairsLocation[hashValue].size() > 1) {
38                return {i, pairsLocation[hashValue][1]};
39            }
40            points.emplace_back(nums1[i], nums2[i], i);
41        }
42      
43        // Recursive Divide and Conquer approach to find a beautiful pair
44        function<tuple<int, int, int>(int, int)> findBeautifulPair = [&](int left, int right) -> tuple<int, int, int> {
45            // Base case for recursion
46            if (left >= right) {
47                return {INT_MAX, -1, -1};
48            }
49            int mid = (left + right) / 2;
50            int pivotX = get<0>(points[mid]);
51          
52            // Find the best pair in the left and right intervals
53            auto leftPair = findBeautifulPair(left, mid);
54            auto rightPair = findBeautifulPair(mid + 1, right);
55          
56            // Choose the better pair based on Manhattan distance and index ordering
57            if (get<0>(leftPair) > get<0>(rightPair) || 
58                (get<0>(leftPair) == get<0>(rightPair) && 
59                (get<1>(leftPair) > get<1>(rightPair) || 
60                (get<1>(leftPair) == get<1>(rightPair) && get<2>(leftPair) > get<2>(rightPair))))) {
61                swap(leftPair, rightPair);
62            }
63          
64            // Check the cross-boundary pairs and try to find a better pair
65            vector<tuple<int, int, int>> temp;
66            for (int i = left; i <= right; ++i) {
67                if (abs(get<0>(points[i]) - pivotX) <= get<0>(leftPair)) {
68                    temp.emplace_back(points[i]);
69                }
70            }
71            // Sort the potential pairs based on Y coordinate
72            sort(temp.begin(), temp.end(), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {
73                return get<1>(a) < get<1>(b);
74            });
75
76            // Evaluate cross-boundary pairs to see if a better pair exists
77            for (int i = 0; i < temp.size(); ++i) {
78                for (int j = i + 1; j < temp.size(); ++j) {
79                    if (get<1>(temp[j]) - get<1>(temp[i]) > get<0>(leftPair)) {
80                        break;
81                    }
82                    int indexI = min(get<2>(temp[i]), get<2>(temp[j]));
83                    int indexJ = max(get<2>(temp[i]), get<2>(temp[j]));
84                    int currentDist = manhattanDistance(get<0>(temp[i]), get<1>(temp[i]), get<0>(temp[j]), get<1>(temp[j]));
85                  
86                    // Update the best pair if a better one is found
87                    if (currentDist < get<0>(leftPair) || 
88                        (currentDist == get<0>(leftPair) && 
89                        (indexI < get<1>(leftPair) || 
90                        (indexI == get<1>(leftPair) && indexJ < get<2>(leftPair))))) {
91                        leftPair = {currentDist, indexI, indexJ};
92                    }
93                }
94            }
95            return leftPair;
96        };
97
98        // Sort the points based on X coordinate to prepare for divide and conquer
99        sort(points.begin(), points.end());
100      
101        // Find the beautiful pair using the divide and conquer approach
102        auto [_, pairIndex1, pairIndex2] = findBeautifulPair(0, points.size() - 1);
103        return {pairIndex1, pairIndex2};
104    }
105};
106
1// Calculates the distance between two points on a coordinate plane.
2function calculateDistance(x1: number, y1: number, x2: number, y2: number): number {
3    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
4}
5
6// Combines two numbers into one unique number.
7function combineNumbers(x: number, y: number): number {
8    return x * 100000 + y;
9}
10
11// Finds a beautiful pair of points based on the input arrays.
12function findBeautifulPair(nums1: number[], nums2: number[]): number[] {
13    // Maps a combined number to an array holding indices of pairs.
14    const pairedIndices: Map<number, number[]> = new Map();
15    const n = nums1.length;
16
17    // Stores initial pairs and their indices.
18    for (let i = 0; i < n; ++i) {
19        const combined = combineNumbers(nums1[i], nums2[i]);
20        if (!pairedIndices.has(combined)) {
21            pairedIndices.set(combined, []);
22        }
23        pairedIndices.get(combined)!.push(i);
24    }
25
26    // Early return if a beautiful pair is found.
27    for (let i = 0; i < n; ++i) {
28        const combined = combineNumbers(nums1[i], nums2[i]);
29        if (pairedIndices.get(combined)!.length > 1) {
30            return [i, pairedIndices.get(combined)![1]];
31        }
32    }
33
34    // Transform point information into an array for sorting.
35    const points: number[][] = nums1.map((num, index) => ([num, nums2[index], index]));
36    points.sort((a, b) => a[0] - b[0]);
37
38    // Divide and conquer approach to find the most beautiful pair.
39    function divideAndConquer(left: number, right: number): number[] {
40        if (left >= right) {
41            return [Infinity, -1, -1];
42        }
43        const mid = (left + right) >> 1;
44        const pivot = points[mid][0];
45        let bestPairLeft = divideAndConquer(left, mid);
46        let bestPairRight = divideAndConquer(mid + 1, right);
47        let bestPair = bestPairLeft[0] <= bestPairRight[0] ? bestPairLeft : bestPairRight;
48
49        // Merge step to consider cross-boundary pairs.
50        const tempPoints: number[][] = [];
51        for (let i = left; i <= right; ++i) {
52            if (Math.abs(points[i][0] - pivot) <= bestPair[0]) {
53                tempPoints.push(points[i]);
54            }
55        }
56        tempPoints.sort((a, b) => a[1] - b[1]);
57
58        for (let i = 0; i < tempPoints.length; ++i) {
59            for (let j = i + 1; j < tempPoints.length; ++j) {
60                if (tempPoints[j][1] - tempPoints[i][1] > bestPair[0]) {
61                    break;
62                }
63              
64                // If a closer pair is found, update the best pair.
65                const pointIndexI = Math.min(tempPoints[i][2], tempPoints[j][2]);
66                const pointIndexJ = Math.max(tempPoints[i][2], tempPoints[j][2]);
67                const currentDistance = calculateDistance(tempPoints[i][0], tempPoints[i][1], tempPoints[j][0], tempPoints[j][1]);
68              
69                if (currentDistance < bestPair[0] || 
70                    (currentDistance === bestPair[0] && (pointIndexI < bestPair[1] || (pointIndexI === bestPair[1] && pointIndexJ < bestPair[2])))) {
71                    bestPair = [currentDistance, pointIndexI, pointIndexJ];
72                }
73            }
74        }
75        return bestPair;
76    }
77
78    // Initiate the divide and conquer process and return the indices of the best pair, excluding the distance.
79    return divideAndConquer(0, n - 1).slice(1);
80}
81

Time and Space Complexity

The given code is a Python class method solving a problem similar in nature to the closest pair of points problem, but with the added goal of finding the "beautiful" pair with the smallest indices. The beautifulPair function implements a divide-and-conquer strategy with additional sorting and filtering. It is important to note that the problem has been slightly modified to find a pair within two lists of integers with additional adherence to the index-based constraints.

Time Complexity:

  • The initial sorting of points has a time complexity of O(N log N), where N is the length of the list nums1 (and nums2, which is assumed to be the same length).
  • In the first loop to populate the points list and find duplicates, each iteration has constant time complexity, O(1), so the entire loop has a time complexity of O(N).
  • The dfs function represents a modified version of the divide-and-conquer algortihm to find the closest pair of points, with the recursive calls happening twice for each level of recursion, and an additional step to filter and sort t :
    • The recursive division of the dataset occurs log N times since the dataset is halved each time.
    • The filtering of points (within the dist threshold) and sorting of subarray t will have a worst-case complexity of O(N log N).
    • The nested loop comparison within the local sorted subset of points is O(N) in the worst case, as the inner loop breaks once d1 is exceeded. However, due to geometry, it is often seen as O(1) on average.
  • The overall time complexity of the dfs function is thus O(N log^2 N) due to the combination of recursive splitting (logarithmic) and sorting within each recursive call (logarithmic).

So, the total time complexity, taken by the sum of all contributing factors, is O(N log N) + O(N) + O(N log^2 N), which simplifies to O(N log^2 N) for large N.

Space Complexity:

  • Intermediate lists such as t in the dfs function can potentially store all points, leading to a space complexity of O(N).
  • The points list which stores the input points with their indices incurs a space complexity of O(N).
  • The recursion stack of the dfs function will use O(log N) space due to the divide-and-conquer approach.

The total space complexity is therefore the sum of these, dominated by the space required for storage of point information, resulting in O(N) space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Divide and Conquer Intro

https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Want a Structured Path to Master System Design Too? Don’t Miss This!