Two Sum Problem Brute Force Approach

Problem Statement❯

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.

Examples❯

Input Array	Target	Output	Description
[2, 7, 11, 15]	9	[0, 1]	2 + 7 = 9
[3, 2, 4]	6	[1, 2]	2 + 4 = 6
[3, 3]	6	[0, 1]	3 + 3 = 6 (duplicate numbers allowed)
[1, 2, 3, 4, 5]	10	[]	No two numbers add up to 10
[]	5	[]	Empty array, no elements to check
[5]	5	[]	Only one element, cannot form a pair

Visualization Player

Solution❯

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:

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

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²).

Algorithm Steps❯

Given an array of numbers nums and a target.
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.
For each pair (i, j), calculate the sum of nums[i] and nums[j].
If the sum equals the target, return the indices [i, j].

Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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]

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(1)	If the required pair is found in the very first iteration.
Average Case	O(n^2)	Each element is compared with every other element after it, resulting in a nested loop.
Worst Case	O(n^2)	In the worst case, all pairs must be checked before a match is found or concluded none exists.

Space Complexity❯

O(1)

Explanation: No additional data structures are used beyond a few variables.

⬅ Previous TopicSort an Array of 0s, 1s, and 2s

Next Topic ⮕Three Sum Problem

Comments

Loading comments...