Two Sum Problem Brute Force Approach

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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

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❯

  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].

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)If the required pair is found in the very first iteration.
Average CaseO(n^2)Each element is compared with every other element after it, resulting in a nested loop.
Worst CaseO(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.

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

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❯

  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].

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)If the required pair is found in the very first iteration.
Average CaseO(n^2)Each element is compared with every other element after it, resulting in a nested loop.
Worst CaseO(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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...