Two Sum Problem

Given an array of integers nums and a target number, your task is to find the indices of two numbers in the array that add up exactly to the target.

• Each input will have exactly one solution.
• You may not use the same element twice.

If no such pair exists, return an empty result.

Understanding the Problem

The Two Sum problem asks us to find two numbers in a given array that add up to a specific target value. Our goal is to return the indices of these two numbers.

For example, if the array is [2, 7, 11, 15] and the target is 9, then 2 + 7 = 9, so we return the indices [0, 1].

Step-by-Step Solution for Beginners

Step 1: Loop through each element

We’ll use a loop to go through each element in the array one by one.

Step 2: For each element, check all elements after it

This helps us avoid repeating the same pairs and ensures we check each possible combination of two numbers.

Step 3: Add the two numbers and check if they equal the target

If they do, we immediately return their indices.

Step 4: Stop once a valid pair is found

The problem guarantees that only one solution exists, so we can stop as soon as we find it.

Let’s Walk Through an Example

Input:

Steps:

• Start with index 0: value is 2
• Check with index 1: 2 + 7 = 9 ✅ → Match found
• Return [0, 1]

Handling Edge Cases

Case 1: Duplicate Numbers

If array is [3, 3] and target is 6, the same number can be used as long as the indices are different. Return [0, 1].

Case 2: No Valid Pair

If no combination adds up to the target, like [1, 2, 3] with target 10, return [].

Case 3: Empty Array

With input [], there are no elements to form a pair. Return [].

Case 4: Single Element

With input [5], one element cannot form a pair. Return [].

Finally

This brute force method is simple and ideal for learning. It helps build an intuitive understanding of how nested loops can be used to compare all pairs.

However, it is not efficient for large arrays since its time complexity is O(n²).

1. Given an array of numbers nums and a target.
2. For each element at index i from 0 to n-2 (where n is the array length), iterate over every element with index j from i+1 to n-1.
3. For each pair (i, j), calculate the sum of nums[i] and nums[j].
4. If the sum equals the target, return the indices [i, j].

#include <stdio.h>
#include <stdlib.h>

int* twoSum(int* nums, int n, int target) {
    int* result = malloc(2 * sizeof(int));
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) {
                result[0] = i;
                result[1] = j;
                return result;
            }
        }
    }
    free(result);
    return NULL;
}

int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int n = sizeof(nums) / sizeof(nums[0]);
    int* indices = twoSum(nums, n, target);
    if (indices != NULL) {
        printf("[%d, %d]\n", indices[0], indices[1]);
        free(indices);
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

vector<int> twoSum(const vector<int>& nums, int target) {
    for (int i = 0; i < nums.size() - 1; i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] + nums[j] == target) {
                return {i, j};
            }
        }
    }
    return {};
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSum(nums, target);
    if (!result.empty()) {
        cout << "[" << result[0] << ", " << result[1] << "]" << endl;
    }
    return 0;
}

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

# Example usage
sol = Solution()
result = sol.twoSum([2, 7, 11, 15], 9)
print(result)

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] result = sol.twoSum(new int[]{2, 7, 11, 15}, 9);
        if (result != null) {
            System.out.println("[" + result[0] + ", " + result[1] + "]");
        }
    }
}

function twoSum(nums, target) {
    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
}

// Example usage:
const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target));

package main

import "fmt"

func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums) - 1; i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    result := twoSum(nums, target)
    fmt.Println(result)
}

fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    for i in 0..nums.len() - 1 {
        for j in i + 1..nums.len() {
            if nums[i] + nums[j] == target {
                return Some((i, j));
            }
        }
    }
    None
}

fn main() {
    let nums = vec![2, 7, 11, 15];
    let target = 9;
    if let Some((i, j)) = two_sum(&nums, target) {
        println!("[{}, {}]", i, j);
    }
}

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray? {
        for (i in 0 until nums.size - 1) {
            for (j in i + 1 until nums.size) {
                if (nums[i] + nums[j] == target) {
                    return intArrayOf(i, j)
                }
            }
        }
        return null
    }
}

fun main() {
    val sol = Solution()
    val nums = intArrayOf(2, 7, 11, 15)
    val target = 9
    val result = sol.twoSum(nums, target)
    if (result != null) {
        println("[${result[0]}, ${result[1]}]")
    }
}

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int]? {
        for i in 0..<nums.count - 1 {
            for j in i+1..<nums.count {
                if nums[i] + nums[j] == target {
                    return [i, j]
                }
            }
        }
        return nil
    }
}

let sol = Solution()
if let result = sol.twoSum([2, 7, 11, 15], 9) {
    print(result)
}

function twoSum(nums: number[], target: number): number[] | null {
    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return null;
}

const nums: number[] = [2, 7, 11, 15];
const target: number = 9;
console.log(twoSum(nums, target));

Time complexity

Space complexity

O(1)

No additional data structures are used beyond a few variables.