Creating a more efficient algorithm for taking the third largest difference an element has with another element in the list in python

Question

This is a programming problem activity from my university. I am going to modify the problem to avoid plagiarism.

Let's say you have n people in a group. For each person, we number them from 0 to n−1. Each person has a personality value exhibited in a list. For example, a list [2, 3, 4, 6] exhibits that person 0 has a personality value of 2, person 1 has a personality value of 3, person 2 has a personality value of 3, and person 3 has a personality value of 6.

We define the enjoyment one person has with another person as |pi - pj| where i and j are subscripts of p and are indices of the list.

To better illustrate let us use the list again as the example.

• The enjoyment person 0 feels with person 1 is |2 - 3| which is 1.
• The enjoyment person 0 feels with person 2 is |2 - 4| is 2,
• The enjoyment person 0 feels with person 3 is |2 - 6| which is 4 and this continues for person 1 and so on.

I want to create a function that returns the third largest enjoyment that a person feels toward another person in the group. So for the list above, I should get an output of [1, 1, 1, 2]. It is guaranteed that a group of friends is greater than 4. The personality can also be negative.

Code:

def third_enjoyment(p: list[int]) -> list[int]:
    n: int = len(p)
    e: list[int] = []

    for i in range(n):
        enjoyment = [abs(p[i] - p[j]) for j in range(n) if j != i]
        enjoyment.sort()
        third_enjoyment = enjoyment[-3]
        e.append(third_enjoyment)

    return e

Here is my solution for this problem. I am not sure about the time but I think this solution has a time complexity of O(n^2) (not too sure as we haven't discussed how time complexities works) which is bad as when I try to submit my code to the judge it exceeds the time limit. I want to know a better way to solve this problem that would be faster than this brute force solution.

Answer 1

I think one way you can optimize the algorithm is to sort the personality value list while keeping its original indices by storing the each item in the list in the tuple structure of (<p value>, <original index>)

sp = sorted([(p[i], i) for i in range(len(p))])

For each item with index i in the sorted list, you know that largest difference with its value is either in the left side or the right side of that item in the sorted list. You can use two pointers l, r representing the index of the left and right side of the item in the sorted list respectively and compare its difference with the item's value (abs(value - sp[l][0]) >= abs(sp[i][0] - sp[r][0])). Initially, l and r are initialized with 0 and n-1 respectively, represent the far left and far right end of the item i in the sorted list. If left side has larger difference than the right side, you know the left side has the largest difference so you increase l index by 1, closer to the item's index, to find the second largest difference. If right side has larger difference than the left side, you know the right side has the largest difference so you decrease r index by 1, closer to the to find the second largest difference. You can keep doing this 3 times to get the third largest difference and apply the result to the array at the given original index. One thing to note, is that l boundary can only be [0, i - 1] and r boundary can only be [i + 1, n - 1] so that if l or r hit their boundary first, only the other pointer has the right result and can be continuously increase/decrease until it reaches 3 total iteration

The total time complexity would be O(nlog(n) + n) which is more efficient than O(n^2)

def third_enjoyment(p: list[int]) -> list[int]:
    n: int = len(p)
    e: list[int] = [-1] * n
    
    # sorted data structure of p in the format (<value>, <original index>)
    # O(nlog(n))
    sp = sorted([(p[i], i) for i in range(len(p))])

    # O(n)
    for i in range(len(sp)):
        value, original_index = sp[i]

        # left, right pointer from sorted list
        l, r = 0, n - 1

        for itt in range(3):
            if l < i:
                # left pointer still within bound
                abs_l = abs(value - sp[l][0])

                if r > i:
                    # right pointer still within bound
                    abs_r = abs(value - sp[r][0])
                    if abs_l >= abs_r:
                        e[original_index] = abs_l
                        l += 1
                    else:
                        e[original_index] = abs_r
                        r -= 1
                else:
                    # right pointer out of bound
                    e[original_index] = abs_l
                    l += 1
            elif r > i:
                # left pointer out of bound, right pointer within bound
                e[original_index] = abs(value - sp[r][0])
                r -= 1
            else:
                # both left and right pointers out bound
                break
    return e

p = [2, 3, 4, 6]
print(third_enjoyment(p))

Answer 2

For this specific problem, finding a solution with significantly lower complexity than O(n^2) is challenging due to the need to compute the enjoyment between each pair of individuals to determine the third largest unique value. The requirement to consider all pairwise comparisons inherently implies a quadratic complexity because each individual's enjoyment must be compared with every other individual's enjoyment.

You can simplify the code as follows.

def third_enjoyment_optimized(personalities: list[int]) -> list[int]:
n = len(personalities)
result = []

for i in range(n):
    # Compute a sorted list of unique absolute differences for the current person with everyone else
    unique_diffs = sorted({abs(personalities[i] - personalities[j]) for j in range(n) if i != j})

    # If there are fewer than three unique enjoyments, use the smallest; otherwise, use the third smallest
    third_largest_unique = unique_diffs[2] if len(unique_diffs) >= 3 else unique_diffs[-1]
    result.append(third_largest_unique)

return result

personalities = [2, 3, 4, 6]
print(third_enjoyment_optimized(personalities))

The output is [4, 3, 2, 4]

Answer 3

Here's an O(n) solution.

Call the input array A.

Use quickselect to find the three largest & three smallest elements of A in linear time, and call this array A'. If |A| < 6, then set A' = A.

Sort A' in O(1) (because it's size doesn't grow with the input, A).

For each element in A, the 3rd best match will be one of the 6 people in A'. Find which by comparing the element (say 'x') with the endpoints of A', moving in by one from the direction with the best score twice. We're doing constant work per member of A, so this step is O(n).

Example:

A = [19, 62, 26, 51, 31, 74, 25, 32, 24, 44]
A' sorted = [19, 24, 25, 51, 62, 74]

Parse A. 

A[0] = 19. Score vs A' endpoints is 19-19=0 & 74-19=55, so we move in one from the right & repeat: 19-19=0 & 62-19=43, so we move in one from the right & repeat, this time taking the better result as our answer: 19-19=0 & 51-19=32, so 51 gets us a score of 32.

A[1] = 62. [19, 74] yields [43, 12]
           [24, 74] yields [38, 12]
           [25, 74] yields [37, 12]; pick 25 for a score of 37.

A[2] = 26. [19, 74] yields [7, 48]
           [19, 62] yields [7, 36]
           [25, 51] yields [7, 25]; pick 51 for a score of 12.

A[3] = 51. [19, 74] yields [32, 24]
           [24, 74] yields [27, 24]
           [25, 74] yields [26, 24]; pick 25 for a score of 26.

...and so on