Optimized Python Solution for Determining if an Array Contains All Possibilities

Question

Problem:

You have been tasked with writing a method named is_all_possibilities (or IsAllPossibilities, as per your preference) that accepts an integer array and returns True if the array contains all possibilities (i.e., all integers from 0 to the length of the array - 1), otherwise returns False.

My Solution:

def is_all_possibilities(arr):
    if len(arr) == 0:
        return False
    n = len(arr) - 1
    i = 0
    
    for x in sorted(arr):
        if x != i:
            return False
        i += 1
    return True

Could you review and optimize the following Python code used to determine if an integer array contains all possibilities from 0 to the length of the array - 1? The current implementation iterates through the array and checks if each element matches the expected sequence. We're seeking a more efficient solution.

Answer 1

As you've seen in many of the other solutions, it's pretty feasible to re-frame your original implementation as a generator, and this increases legibility.

Add unit tests.

I disregard your memory tag and focus on run-time performance. Importantly, there is no one algorithm that will be the best choice for all inputs; the nature of the inputs will significantly change which method is best-suited. For example, for inputs that have out-of-range values, this simple implementation will perform well as it's suited to early-terminate:

def r_enum(arr: list[int]) -> bool:
    arr.sort()
    return all(
        i == x
        for i, x in enumerate(arr)
    )

(However, your use of sorted - whereas it takes a small performance hit when compared to in-place sorting - is preferable as it reduces side-effects.)

This is equivalent to the marginally faster but more impenetrable

all(
    itertools.starmap(operator.eq, enumerate(arr))
)

The above functional approach may be your best choice as an all-around efficient implementation.

To summarise the input-kind effect over all of the methods we've seen so far:

import itertools
import math
import operator
from collections import Counter
from timeit import timeit
from typing import Callable, Any

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns
from matplotlib.axes import Axes
from numpy.random import default_rng


def op(arr):
    if len(arr) == 0:
        return False
    n = len(arr) - 1
    i = 0

    for x in sorted(arr):
        if x != i:
            return False
        i += 1
    return True


def jh_a(arr: list[int]) -> bool:
    arr.sort()

    return (
        len(set(arr)) == len(arr)
        and arr[0] == 0
        and arr[-1] == len(arr) - 1
        and all(isinstance(x, int) for x in arr)
    )


def jh_c(arr: list[int]) -> bool:
    n = len(arr)
    expected_sum = n * (n - 1) / 2

    return (
        math.prod(filter(lambda x: x > 0, arr)) == factorial(n - 1)
        and sum(arr) == expected_sum
        and min(arr) == 0
        and max(arr) == len(arr) - 1
        and all(isinstance(x, int) for x in arr)
    )


def factorial(n: int) -> int:
    return math.prod(range(1, n + 1))


def jh_d(arr: list[int]) -> bool:
    arr.sort()
    return all(arr[i] == i for i in range(len(arr)))


def jh_e(arr: list[int]) -> bool:
    arr.sort()
    return all(isinstance(arr[i], int) and arr[i] == i for i in range(len(arr)))


def r_enum(arr: list[int]) -> bool:
    arr.sort()
    return all(
        i == x
        for i, x in enumerate(arr)
    )


def r_functional(arr: list[int]) -> bool:
    arr.sort()
    return all(
        itertools.starmap(operator.eq, enumerate(arr))
    )


def harith_a(arr: list[int]) -> bool:
    if len(arr) == 0:
        return False

    for i, x in enumerate(sorted(arr)):
        if x != i:
            return False

    return True


def harith_b(arr: list[int]) -> bool:
    return False if len(arr) == 0 else sorted(arr) == list(range(len(arr)))


def harith_c(arr: list[int]) -> bool:
    return 0 if len(arr) == 0 else Counter(arr) == Counter(range(len(arr)))


def ahall_a(arr: list[int]) -> bool:
    return False if len(arr) == 0 else set(arr) == set(range(len(arr)))


def ahall_b(arr: list[int]) -> bool:
    return bool(arr) and set(arr) == set(range(len(arr)))


def ahall_c(arr: list[int]) -> bool:
    return set(arr) == set(range(len(arr) or 1))


def sudix_b(arr: list[int]) -> bool:
    bit_arr = np.zeros(len(arr),dtype=bool)

    for x in arr:
        if x<0 or x>= len(arr):
            return False
        if bit_arr[x] == True:
            return False
        bit_arr[x] = True

    return True


METHODS = (
    op,
    jh_a,
    # jh_b,  # fails for [0 0 3 3]
    jh_c, jh_d, jh_e,
    harith_a, harith_b, harith_c,
    r_enum, r_functional,
    ahall_a, ahall_b, ahall_c,
    sudix_b,
)


def test() -> None:
    examples = (
        #  (),  # arguably appropriate here, but OP coded the opposite
        (0,),
        (1, 0, 2),
        (2, 1, 0),
        (0, 1, 2, 3, 4),
    )
    counterexamples = (
        (1,),
        (2, 1),
        (1, 2, 3),
        (0, 0, 3, 3),  # This disqualifies jh_b
        (-1, 0, 1, 2),
    )
    for method in METHODS:
        for example in examples:
            assert method(list(example)), f'{method.__name__} failed example'
        for example in counterexamples:
            assert not method(list(example)), f'{method.__name__} failed counterexample'


def benchmark() -> None:
    rand = default_rng(seed=0)

    def make_shuffle(n: int) -> np.ndarray:
        series = np.arange(n)
        rand.shuffle(series)
        return series

    rows = []
    kinds = (
        ('repeated_0', lambda n: np.full(shape=n, fill_value=0)),
        ('repeated_hi', lambda n: np.full(shape=n, fill_value=n + 1)),
        ('sorted', lambda n: np.arange(n)),
        ('shuffled', make_shuffle),
    )
    for kind, make_input in kinds:
        sizes = (10**np.linspace(0, 4, num=6)).astype(int)

        def run_all(
            rep: int,
            n: int,
            inputs: np.ndarray,
            methods: tuple[Callable, ...],
        ) -> list[dict[str, Any]]:
            result = []
            for method in methods:
                inputs_list = inputs.tolist()
                def run() -> bool:
                    return method(inputs_list)
                result.append({
                    'n': n,
                    'kind': kind,
                    'method': method.__name__,
                    'rep': rep,
                    'dur': timeit(stmt=run, number=1),
                })
            return result

        prune_rows = run_all(rep=0, n=sizes[-1], inputs=make_input(sizes[-1]), methods=METHODS)
        prune_rows.sort(key=lambda row: row['dur'])
        pruned_methods = [
            next(
                method
                for method in METHODS
                if method.__name__ == row['method']
            )
            for row in prune_rows[:len(prune_rows)//2][::-1]
        ]

        for n in sizes:
            inputs = make_input(n)
            for rep in range(5):
                rows.extend(run_all(rep=rep, n=n, inputs=inputs, methods=pruned_methods))

    df = pd.DataFrame.from_dict(rows)
    df = df.groupby(['n', 'kind', 'method'])['dur'].min()

    fig, axes = plt.subplots(nrows=2, ncols=2)
    fig.suptitle(f'{len(METHODS)//2} fastest methods, four input kinds')
    axes = [ax for row in axes for ax in row]

    for kind, ax in zip(df.index.unique('kind'), axes):
        ax: Axes
        ax.set_xscale('log')
        ax.set_yscale('log')
        ax.set_title(kind)
        sns.lineplot(
            ax=ax,
            data=df[(slice(None), kind, slice(None))].reset_index(),
            x='n', y='dur', hue='method',
        )

    plt.show()


if __name__ == '__main__':
    test()
    benchmark()

Answer 2

A simple algorithm with runtime complexity of O(n) is:

def lintime(arr: list[int]) -> bool:
    bit_arr = np.zeros(len(arr),dtype=bool)

    for x in arr:
        if x<0 or x>= len(arr):
            return False
        bit_arr[int(x)] = True


    return np.alltrue(bit_arr)

This saves the sorting of the array, which is, at least in Landau notation, the most expensive part, and improves on Harith's method with counters by replacing the Counter's with faster arrays.

Similarly to other answers, one can early-stop if the algorithm ever sets a bit that was already set. In turn, if the array contains n unique numbers in {0,...,n-1}, then it already must contain each number in {0,...,n-1}. So we can improve above algorithm:

def lintime(arr: list[int]) -> bool:
    bit_arr = np.zeros(len(arr),dtype=bool)

    for x in arr:
        if x<0 or x>= len(arr):
            return False
        if bit_arr[x] == True:
            return False
        bit_arr[x] = True

    return True

Answer 3

n goes unused in the function. We can safely elide it.

---

Since it is an array of integers, a type-hint would help the readers and linters:

# def is_all_possibilities(arr):

def is_all_possibilities(arr: list[int]) -> bool:
    ...

---

i = 0
    
for x in sorted(arr):
    if x != i:
        return False
    ...

Since the comparison starts from 0 and number of iterations is equal to the length of the list, we can use enumerate() to get both the value of i and the corresponding item from arr:

for i, x in enumerate(sorted(arr)):
    ...

So your code becomes:

def is_all_possibilities(arr: list[int]) -> bool:
    if len(arr) == 0:
        return False
    
    for i, x in enumerate(sorted(arr)):
        if x != i:
            return False
        
    return True

Or perhaps:

def is_all_possibilities(arr: list[int]) -> bool:
    return len(arr) != 0 and sorted(arr) == list(range(len(arr)))

Or if we use a Counter:

from collections import Counter

def is_all_possibilities(arr: list[int]) -> bool:
    return len(arr) != 0 and Counter(arr) == Counter(range(len(arr)))

Answer 4

This question is tagged memory-optimization. So upon being handed a vector of length N, we wish to compute a boolean with O(1) constant memory complexity, that is, without allocating O(N) bytes.

We could recycle an existing allocation by sorting in-place.

def is_all_possibilities(arr: list[int]) -> bool:
    arr.sort()

    return (
        len(set(arr)) == len(arr)
        and arr[0] == 0
        and arr[-1] == len(arr) - 1
        and all(isinstance(x, int) for x in arr)
    )

But that set() call still doubles the allocation, so no joy.

An analytic formula for the sum of such integers is available. Let's use that.

def is_all_possibilities(arr: list[int]) -> bool:
    n = len(arr)
    expected_sum = n * (n - 1) / 2

    return (
        sum(arr) == expected_sum
        and min(arr) == 0
        and max(arr) == len(arr) - 1
        and all(isinstance(x, int) for x in arr)
    )

The trouble is that it's easily fooled, e.g. by [0, 0, 3, 3].

Incorporating the product will close that loophole, letting us compute the result with O(1) constant memory complexity.

def is_all_possibilities(arr: list[int]) -> bool:
    n = len(arr)
    expected_sum = n * (n - 1) / 2

    return (
        math.prod(filter(lambda x: x > 0, arr)) == math.factorial(n - 1)
        and sum(arr) == expected_sum
        and min(arr) == 0
        and max(arr) == len(arr) - 1
        and all(isinstance(x, int) for x in arr)
    )

Returning to that original "sort in place" idea, we could have gotten away with something as simple as this.

def is_all_possibilities(arr: list[int]) -> bool:
    arr.sort()
    return all(arr[i] == i for i in range(len(arr)))

or, to be picky:

    ...
    return all(isinstance(arr[i], int) and arr[i] == i for i in range(len(arr)))

This of course has the downside that caller might be surprised we trashed his input array, leaving behind a permutation of the original. YMMV.

To take advantage of builtins we make multiple traversals over the input array. Clearly we could implement the same logic with a single for loop and no builtins, if desired.