EASY 0001. Two Sum

Problem Statement

Leetcode Link

Examples

Solution

Solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
"""Solution for the Leetcode problem #0001 Two Sum
https://leetcode.com/problems/two-sum/
"""


def two_sum(nums: list[int], target: int) -> list[int]:
    """Given a list of integers, find two numbers that add up to
    a given target integer."""
    values = {}
    for index, item in enumerate(nums):
        if values.get(item) is None:
            values[item] = [index]
        else:
            values[item].append(index)

    for index, item in enumerate(nums):
        matching_value = target - item
        positions = values.get(matching_value)
        if positions is not None:
            if matching_value == item:
                if len(positions) > 1:
                    return item, matching_value
            else:
                return item, matching_value

    return []
Solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
"""Solution for the Leetcode problem #0001 Two Sum
https://leetcode.com/problems/two-sum/
"""


def two_sum(nums: list[int], target: int) -> list[int]:
    """Given a list of integers, find two numbers that add up to
    a given target integer
    While this solution does have an n.logn Time complexity, it
    has an O(1) space complexity and is a better solution
    when we have memory constraints.
    """

    # sort the array
    array.sort()
    left = 0
    right = len(nums) - 1

    while left < right:
        l_val = nums[left]
        r_val = nums[right]
        if l_val + r_val == target:
            return [l_val, r_val]
        elif l_val + r_val > target:
            right -= 1
        elif l_val + r_val < target:
            l_val += 1

    return []