5 Best Ways to Check if an Array is Beautiful in Python

Rate this post

πŸ’‘ Problem Formulation: Suppose you’re presented with an array of integers. How do you check if it’s “beautiful,” defined as each element being the sum of two unique preceding elements in the array? This article explores the Pythonic ways to solve this problem, such as an input array [0, 1, 3, 6, 10] and looking for a confirmation that it is indeed beautiful, or not.

Method 1: Brute Force Approach

This method involves checking all possible pairs of previous elements for each element after the first two in the array. It’s straightforward but might be inefficient for large arrays because the check is done in a double-nested loop, which is computationally expensive.

Here’s an example:

def is_beautiful(arr):
    for i in range(2, len(arr)):
        found = False
        for j in range(0, i):
            for k in range(0, i):
                if j != k and arr[j] + arr[k] == arr[i]:
                    found = True
                    break
            if found:
                break
        if not found:
            return False
    return True

print(is_beautiful([0, 1, 3, 6, 10]))

Output: True

This code snippet checks each number (starting from the third) to see if it can be composed as the sum of any two distinct preceding numbers in the array. If it finds such a pair for every number, the function returns True, signifying that the array is beautiful.

Method 2: Using Dictionary for Previous Sums

To optimize the beautiful array check, a dictionary can be employed to store the sums of all pairs of previous elements. This reduces the time complexity by avoiding repetitive addition operations.

Here’s an example:

def is_beautiful(arr):
    prev_sums = set()
    for i in range(1, len(arr)):
        for j in range(0, i):
            prev_sums.add(arr[i] + arr[j])
        if arr[i] not in prev_sums:
            return False
    return True

print(is_beautiful([0, 1, 3, 6, 10]))

Output: True

In this code, every new element’s value is checked against a set of sums of all unique pairs of preceding elements. If the element isn’t found in the set, the array isn’t beautiful, and we return False. Otherwise, we continue and return True if the entire array passes the check.

Method 3: Hash Map with Early Stopping

A hash map (or dictionary in Python) can store encountered sums for quick look-up. Improving upon the previous method, we can include an early stopping mechanism as soon as we identify a non-beautiful element.

Here’s an example:

def is_beautiful(arr):
    prev_sums = set()

    for i in range(len(arr)):
        if i > 1 and arr[i] not in prev_sums:
            return False
        for j in range(i):
            prev_sums.add(arr[i] + arr[j])
            
    return True

print(is_beautiful([0, 1, 3, 6, 10]))

Output: True

This optimized code snippet uses a set to store the sums of all unique pairs of previous elements. We check each element (after the second) to see if it’s in the set of previous sums, returning False immediately if an element fails the checkβ€”which improves performance by halting early if the array is not beautiful.

Method 4: Using itertools.combinations

This method leverages Python’s itertools.combinations to check if any combination of two unique preceding numbers sums up to the current number. It’s more Pythonic and utilizes Python’s standard library for creating combinations.

Here’s an example:

import itertools

def is_beautiful(arr):
    for i in range(len(arr)):
        if i >= 2 and not any(arr[i] == sum(comb) for comb in itertools.combinations(arr[:i], 2)):
            return False
    return True

print(is_beautiful([0, 1, 3, 6, 10]))

Output: True

Using the itertools.combinations function greatly simplifies code readability and provides a powerful built-in method for generating unique pairs, though it might not be the most efficient for large datasets.

Bonus One-Liner Method 5: Lambda and Filter Application

This concise one-liner method involves using a lambda function within a filter to process the array and determine if it is beautiful. It is compact and takes advantage of Python’s functional programming features.

Here’s an example:

arr = [0, 1, 3, 6, 10]
is_beautiful = all(map(lambda i: any(arr[i] == sum(comb) for comb in itertools.combinations(arr[:i], 2)), range(2, len(arr))))

print(is_beautiful)

Output: True

This one-liner performs a check on all elements in the array (after the second one) using map and a lambda function that applies the combination sum check. all is used to ensure each element meets the condition, verifying if the array is beautiful.

Summary/Discussion

  • Method 1: Brute Force. Simple to understand but has a high time complexity for large arrays.
  • Method 2: Using Dictionary for Previous Sums. More efficient than brute force and easy to implement.
  • Method 3: Hash Map with Early Stopping. Offers a balance of readability and efficiency by incorporating an early exit.
  • Method 4: Using itertools.combinations. It is very readable and utilizes a standard library but might not be suitable for very large arrays due to its time complexity.
  • Method 5: Lambda and Filter Application. This method offers a compact solution; however, the condensed syntax might be less readable for some developers.