1. Two Sum

Python

Solution walkthrough: https://twitter.com/lloydtao/status/1584288569622790145

🥇 Hash table - O(n)

Method: Take each number and check if its complement has been seen before. If not, add it to the list of known complements along with its index.

• Time complexity: O(n)
• Space complexity: O(n)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Take each number and check if its complement has been seen before. If not,
        add it to the list of known complements along with its index.

        Args:
            nums (List[int]): Input array of integers
            target (int): Target integer

        Returns:
            List[int]: Indices of the two integers that sum to target
        """
        # Initialise hash map to store known integers
        complements = {}
        # Iterate through the list
        for i in range(len(nums)):
            # Check if the current number's complement has been seen before
            complement = target - nums[i]
            if complement in complements:
                return [complements[complement], i]
            # Add the current number to the list of known complements
            complements[nums[i]] = i

🥈 Check pairs - O(n²)

Method: Take each pair of numbers and see if they add up to the target.

• Time complexity: O(n²)
• Space complexity: O(1)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Take each pair of numbers and see if they add up to the target.

        Args:
            nums (List[int]): Input array of integers
            target (int): Target integer

        Returns:
            List[int]: Indices of the two integers that sum to target
        """
        # Get length of input array
        n = len(nums)
        # Iterate over all pairs (i,j)
        for i in range(n):
            for j in range(i + 1, n):
                # Check if this pair equals the target
                if nums[i] + nums[j] == target:
                    return [i, j]