Skip to main content

Daily Coding Problem: Find Two Numbers That Add to a Target

Problem

Given a list of integers and a target, return two distinct indices whose values add to the target. Return None in Python or null in Java if no pair exists.

Worked example

For [4, 1, 6, 2] with target 8, return (2, 3).

Insert 4 at index 0 and 1 at index 1. At index 2, 6 needs 2, which has not appeared yet. At index 3, 2 needs 6, and the map returns index 2.

How the solution works

The map contains only earlier indices, so the first match gives two distinct indices. Every pair can be found when the algorithm visits its later index.

Checking the map before insertion prevents a single 4 from being used twice when the target is 8. The Java version uses long for the complement so integer overflow cannot produce a false match.

Python solution

def two_sum(nums, target):
    seen = {}
    for index, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return seen[complement], index
        seen[value] = index
    return None

Java solution

import java.util.*;
class Solution {
    static int[] twoSum(int[] nums, int target) {
        Map<Long, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            long value = nums[i];
            Integer earlier = seen.get((long) target - value);
            if (earlier != null) return new int[]{earlier, i};
            seen.put(value, i);
        }
        return null;
    }
}

Complexity and edge cases

Expected O(n) time and O(n) space. [3, 3] with target 6 returns (0, 1); [3] with target 6 has no pair; [−4, 1, 5] with target 1 returns (0, 2).

Related exercise: Find the First Unique Character.

Comments

Popular posts from this blog

Minimum Window Substring: Efficient Algorithm for Finding the Shortest Substring

The Minimum Window Substring problem is a classic string manipulation challenge that tests our algorithmic skills. In this blog, we will explore an efficient solution to find the minimum window substring in a given string. We will provide implementation examples in both Java and Python, enabling you to grasp the concepts and apply them to your own coding projects.   Understanding the Problem: Given a string and a target pattern, our objective is to find the minimum window substring in the given string that contains all the characters of the target pattern. The minimum window substring refers to the shortest possible substring that satisfies this condition.   Approach: To solve the Minimum Window Substring problem, we can use the sliding window technique. This approach involves maintaining a window of characters in the string and adjusting its size based on certain conditions. The key steps of the algorithm are as follows: Create two pointers, left and right, to define the windo...