1. Two Sum (Easy)

Pyodide

Editor (session: default) Run

# Type here

Output Clear

Run

Editor (session: default) Run

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        num_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_map:
                return [num_map[complement], i]
            num_map[num] = i

        return []

#if __name__ == "__main__":
print(Solution().twoSum([0,1,2,3,4,5],2))

Output Clear

Solution

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        num_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_map:
                return [num_map[complement], i]
            num_map[num] = i

        return []

Function Description

Source code in python/_1.py

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        """
        Finds two unique numbers in the input list that sum up to a specific target 
        value and returns the 0-based indices of those two numbers. The function 
        uses a hash map to achieve a time complexity of $O(n)$ by storing each 
        number and its index as it iterates through the list, then checking if 
        the required complement (target - current number) already exists in the map.

        Args:
            nums: A list of integers where exactly one valid solution exists.
            target: The target integer sum.

        Returns:
            A list containing the indices of the two numbers that sum up to the target, 
            e.g., [index1, index2].
        """
        num_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_map:
                return [num_map[complement], i]
            num_map[num] = i

        return []

twoSum(nums, target)

Finds two unique numbers in the input list that sum up to a specific target value and returns the 0-based indices of those two numbers. The function uses a hash map to achieve a time complexity of \(O(n)\) by storing each number and its index as it iterates through the list, then checking if the required complement (target - current number) already exists in the map.

Parameters:

Name	Type	Description	Default
nums	list[int]	A list of integers where exactly one valid solution exists.	required
target	int	The target integer sum.	required

Returns:

Type	Description
list[int]	A list containing the indices of the two numbers that sum up to the target,
list[int]	e.g., [index1, index2].

Source code in python/_1.py

def twoSum(self, nums: list[int], target: int) -> list[int]:
    """
    Finds two unique numbers in the input list that sum up to a specific target 
    value and returns the 0-based indices of those two numbers. The function 
    uses a hash map to achieve a time complexity of $O(n)$ by storing each 
    number and its index as it iterates through the list, then checking if 
    the required complement (target - current number) already exists in the map.

    Args:
        nums: A list of integers where exactly one valid solution exists.
        target: The target integer sum.

    Returns:
        A list containing the indices of the two numbers that sum up to the target, 
        e.g., [index1, index2].
    """
    num_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i

    return []

Explanation

The "Two Sum" problem is universally recognized as the introductory problem in algorithmic interviews and a foundational concept for understanding time complexity trade-offs. The requirement is straightforward: given an array of integers, nums, and a specific target integer, identify and return the indices of the two numbers within the array that sum up exactly to the target. The problem is generally constrained by the guarantee that exactly one valid solution exists, and the same element cannot be used twice.

A simple, though professionally unacceptable, solution involves a brute-force approach using nested loops. The outer loop iterates over each element \(nums[i]\), and the inner loop checks every subsequent element \(nums[j]\) to see if \(nums[i] + nums[j]\) equals the target. While correct, this method results in a quadratic time complexity of \(O(n^2)\). This inefficiency means the execution time increases dramatically as the input array size grows, failing to meet the performance standards required in production systems.

The definitive, industry-standard solution achieves linear time complexity, \(O(n)\), by utilizing a hash map (or dictionary). This method performs a single pass through the array. For each number \(nums[i]\), the algorithm calculates the complement needed to reach the target (\(complement = target - nums[i]\)). Before inserting the current element into the hash map, the algorithm checks if the required \(complement\) already exists as a key in the map. If the complement is found, the current index \(i\) and the index stored in the map (which belongs to the complement) are returned. If not found, the number \(nums[i]\) and its index \(i\) are added to the map. This leverages the \(O(1)\) average-time complexity of hash map lookups to ensure maximum efficiency.