5
\$\begingroup\$

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.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Is it actually memory optimisation you're looking for? In the vast majority of problems like this, the problem typically wants run-time optimisation, which is not the same thing. \$\endgroup\$
    – Reinderien
    Feb 25 at 17:08
  • 2
    \$\begingroup\$ There is a "trick" to solving this problem: iterate through the array, and on iteration i, try to swap the value at index i into position a[i]. If the array contains the elements 0...(n-1) this will just work. If it contains any duplicates or out-of-bounds elements, you can detect this when doing the swap. Honestly, problems like this are poorly suited for this site. The answer is less about writing good code and more about figuring out a neat trick. \$\endgroup\$ Feb 26 at 3:20
  • \$\begingroup\$ @BenjaminKuykendall Doesn't that still require O(n) space, since you have to make a modifiable copy of the array? \$\endgroup\$ Feb 26 at 22:30
  • \$\begingroup\$ @2012rcampion the input arr is mutable as the OP presented it. I don't see any constraints on modifying the input in the question. Users might not like you permuting their input... but that's okay because it's a made up algorithms question and there aren't any real users! \$\endgroup\$ Feb 26 at 23:58
  • 1
    \$\begingroup\$ @BenjaminKuykendall The original also works if arr is immutable, e.g. a tuple or bytes. In fact it even works with range, which only uses constant space. So to guarantee that you can modify the input you'd have to start with arr = list(arr). \$\endgroup\$ Feb 27 at 1:52

4 Answers 4

4
\$\begingroup\$

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()

benchmarks

\$\endgroup\$
3
  • \$\begingroup\$ A method that's even faster on the shuffled benchmark is return False if len(arr) == 0 else set(arr) == set(range(len(arr))). Or return bool(arr) and set(arr) == set(range(len(arr))) or return set(arr) == set(range(len(arr) or 1)) to deal with the empty case more efficiently. \$\endgroup\$
    – Alex Hall
    Feb 25 at 23:23
  • 1
    \$\begingroup\$ @AlexHall You're welcome to file an answer \$\endgroup\$
    – Reinderien
    Feb 25 at 23:28
  • \$\begingroup\$ More penetrable variation? all(map(operator.eq, arr, itertools.count())) \$\endgroup\$
    – no comment
    Mar 1 at 5:41
4
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ The first method does not actually work. Try for input [0]. \$\endgroup\$
    – Reinderien
    Feb 26 at 13:31
  • \$\begingroup\$ @Reinderien It returns true for this case, which it should as the array is sorted. If you plugged it into your test, be aware that np.all sometimes returns np.bool_ instead of bool, so the boolean test using is doesn't work as False and True in this case aren't Singletons anymore. \$\endgroup\$
    – Sudix
    Feb 26 at 20:55
  • \$\begingroup\$ That's true; thanks for clarifying! \$\endgroup\$
    – Reinderien
    Feb 27 at 13:04
2
\$\begingroup\$

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)))
\$\endgroup\$
0
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Timsort costs O(n) in space complexity for allocation of a temp array. \$\endgroup\$
    – blhsing
    Feb 26 at 9:40
  • \$\begingroup\$ The math module contains a factorial function: docs.python.org/3/library/math.html#math.factorial \$\endgroup\$
    – rdesparbes
    Feb 27 at 13:02
  • \$\begingroup\$ Factorial takes O(n log n) space, not O(1). \$\endgroup\$
    – no comment
    Mar 1 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.