Two Sum Test at Testdome for Python

Two Sum Test at Testdome for Python

The "Two Sum" problem is a classic coding interview question. Here's a solution to the problem that you might encounter on TestDome or in similar assessments, along with an explanation:

Problem Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

nums = [2, 7, 11, 15]
target = 9

Expected output:

[0, 1]

Explanation: nums[0] + nums[1] equals 2 + 7 = 9, so we return [0, 1].

Solution

To solve this problem efficiently, we can use a hash map (dictionary in Python) to store the indices of numbers as we iterate through the list. Here's the Python code for the solution:

def two_sum(nums, target):
    num_to_index = {}
    
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_to_index:
            return [num_to_index[complement], i]
        num_to_index[num] = i
    
    return []  # No valid solution found

# Example usage:
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # Output: [0, 1]

Explanation of the Solution

  1. Initialization: Create an empty dictionary num_to_index to store numbers as keys and their indices as values.

  2. Iterate through the list: Use enumerate to loop through each number and its index in the nums list.

  3. Check for complement: For each number num, calculate its complement (target - num). Check if this complement exists in num_to_index. If it does, return the indices [num_to_index[complement], i], where i is the current index.

  4. Store in dictionary: If the complement does not exist in num_to_index, store the current number num in num_to_index with its index i.

  5. Return: If no solution is found during the iteration, return an empty list [].

Time Complexity

The solution has a time complexity of O(n), where n is the number of elements in the nums list. This is because the dictionary operations (insert and lookup) are average O(1) time complexity.

Conclusion

This approach efficiently solves the "Two Sum" problem using a hash map to trade off space for speed. It ensures that the solution is optimal and meets the problem requirements. This solution is suitable for coding assessments and interviews, including those on platforms like TestDome.

Examples

  1. "Python Testdome Two Sum problem explanation"

    Description: This query seeks an explanation of the Two Sum problem on Testdome, including the problem statement and expected input/output.

    Code:

    def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        diff = target - num
        if diff in seen:
            return [seen[diff], i]
        seen[num] = i
    return []

# Example usage
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # Output: [0, 1]

  2. "Python Testdome Two Sum brute force solution"

    Description: This query focuses on a brute force approach to solve the Two Sum problem, which checks all pairs of elements.

    Code:

    def two_sum_brute_force(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# Example usage
nums = [2, 7, 11, 15]
target = 9
print(two_sum_brute_force(nums, target))  # Output: [0, 1]

  3. "Python Testdome Two Sum optimized solution"

    Description: This query aims to find an optimized solution for the Two Sum problem using a hash map to store seen elements.

    Code:

    def two_sum_optimized(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        diff = target - num
        if diff in seen:
            return [seen[diff], i]
        seen[num] = i
    return []

# Example usage
nums = [3, 2, 4]
target = 6
print(two_sum_optimized(nums, target))  # Output: [1, 2]

  4. "Python Testdome Two Sum using dictionary"

    Description: This query focuses on solving the Two Sum problem using a Python dictionary to store the indices of the elements.

    Code:

    def two_sum_dict(nums, target):
    index_map = {}
    for index, number in enumerate(nums):
        complement = target - number
        if complement in index_map:
            return [index_map[complement], index]
        index_map[number] = index
    return []

# Example usage
nums = [3, 3]
target = 6
print(two_sum_dict(nums, target))  # Output: [0, 1]

  5. "Python Testdome Two Sum with input validation"

    Description: This query focuses on adding input validation to the Two Sum problem solution to handle edge cases and invalid inputs.

    Code:

    def two_sum_with_validation(nums, target):
    if not nums or not isinstance(target, int):
        return []

    seen = {}
    for i, num in enumerate(nums):
        if not isinstance(num, int):
            continue
        diff = target - num
        if diff in seen:
            return [seen[diff], i]
        seen[num] = i
    return []

# Example usage
nums = [2, 7, 11, 'a']
target = 9
print(two_sum_with_validation(nums, target))  # Output: [0, 1]

  6. "Python Testdome Two Sum with sorting"

    Description: This query focuses on solving the Two Sum problem by sorting the array first, then using two pointers to find the sum.

    Code:

    def two_sum_sorted(nums, target):
    nums = sorted(enumerate(nums), key=lambda x: x[1])
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left][1] + nums[right][1]
        if current_sum == target:
            return [nums[left][0], nums[right][0]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

# Example usage
nums = [1, 2, 3, 4]
target = 7
print(two_sum_sorted(nums, target))  # Output: [2, 3]

  7. "Python Testdome Two Sum one-pass hash table"

    Description: This query focuses on solving the Two Sum problem using a one-pass hash table approach for efficient lookup and insertion.

    Code:

    def two_sum_one_pass(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i
    return []

# Example usage
nums = [1, 2, 3, 4]
target = 5
print(two_sum_one_pass(nums, target))  # Output: [0, 3]

  8. "Python Testdome Two Sum edge cases handling"

    Description: This query focuses on handling edge cases in the Two Sum problem, such as empty arrays or no solution.

    Code:

    def two_sum_edge_cases(nums, target):
    if len(nums) < 2:
        return []

    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i
    return []

# Example usage
nums = [1]
target = 2
print(two_sum_edge_cases(nums, target))  # Output: []

  9. "Python Testdome Two Sum problem test cases"

    Description: This query focuses on creating multiple test cases to validate the solution for the Two Sum problem.

    Code:

    def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i
    return []

# Test cases
test_cases = [
    ([2, 7, 11, 15], 9, [0, 1]),
    ([3, 2, 4], 6, [1, 2]),
    ([3, 3], 6, [0, 1]),
    ([1, 2, 3, 4], 8, [])
]

for nums, target, expected in test_cases:
    result = two_sum(nums, target)
    assert result == expected, f"Test failed for nums={nums} and target={target}. Expected {expected}, got {result}"
print("All test cases passed!")

  10. "Python Testdome Two Sum performance optimization"

    Description: This query aims to optimize the performance of the Two Sum solution for large input arrays.

    Code:

    def two_sum_optimized_performance(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i
    return []

# Example usage with large input
nums = list(range(1, 10000001))
target = 19999999
print(two_sum_optimized_performance(nums, target))  # Output: [9999998, 9999999]

More Tags

marionette popup-balloons go-reflect jalali-calendar decoding comparator logback rsync super python-unittest

More Programming Questions

More Electrochemistry Calculators

More Other animals Calculators

More Fitness-Health Calculators

More Transportation Calculators