Python Beginner Algorithms Tutorial

Check if Double of Value Exists (via Leetcode)

This problem can be found on Leetcode.

Problem statement:

Given a list of integers, check if an integer in the list called M has a value that's exactly double of a different integer N in the list.

Test Cases

In [4]:
# assert check_if_double_exists([10, 1, 3, 6]) == True

In the list, 6 is twice the value of 3 so return True.

In [5]:
# assert check_if_double_exists([8, 5, 3]) == False

In the list, no value is twice the value of another one.

Pseudocode

In [6]:
# create a function that takes as an input a list of integers

    # keep track of items iterated over in a set to allow for O(1) comparison lookups
    # assign covered_items_set to be empty set
    # iterate over items in input list:
        # if item*2 in set or item/2 in set:
            # return True
        # else:
            # add item to set
    # finished iteration and coudn't find a double or half equivalent value...
    # return False

Code

In [9]:
def check_if_double_exists(integers_list):
    covered_items_set = set()
    for number in integers_list:
        if number*2 in covered_items_set or number/2 in covered_items_set:
            return True
        else:
            covered_items_set.add(number)
    return False

Complexity

Let n be the count of items in the input list.

Time complexity is O(n) because at worst case, there's a single iteration over all values in the integer list.

Space complexity is O(n) because at worst case, all values in the integer list are added to a set of n length.

Verify Code with Test Cases

In [10]:
assert check_if_double_exists([10, 1, 3, 6]) == True
In [11]:
assert check_if_double_exists([8, 5, 3]) == False