TWO SUM PROBLEM

 

Two Sum Problem – Explanation with Approach (Brute Force)

Introduction

The Two Sum problem is a common programming question where we are given an array of integers and a target value. The goal is to find the indices of two numbers such that their sum equals the target.

This problem helps in understanding basic concepts like loops, condition checking, and array traversal.

Problem Statement

Given an array nums and an integer target, return the indices of two numbers such that:

• nums[i] + nums[j] = target

• Each input has exactly one solution

• The same element cannot be used twice

Solution Code

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

Approach Used: Brute Force

Idea

The approach used here is to check all possible pairs of elements in the array and find the pair whose sum equals the target.

How it Works

1. Loop through each element using index i

2. For every element, check the next elements using index j

3. If the sum of nums[i] and nums[j] equals the target:

   • Return their indices immediately

Why This Approach Was Chosen

• It is simple and easy to understand, especially for beginners

• No additional data structures are required

• Guarantees finding the solution since all pairs are checked

Alternative Approaches

• HashMap approach (Optimal)
  Uses extra space but reduces time complexity

• Two-pointer approach
  Works only if the array is sorted

Why not used here?
Since this is a basic implementation, the brute force approach is chosen for clarity and simplicity.

Time and Space Complexity

• Time Complexity: O(n²)
  Because of two nested loops

• Space Complexity: O(1)
  No extra space is used

Example

Input:

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

Output:

[0, 1]

Explanation:
nums[0] + nums[1] = 2 + 7 = 9

Conclusion

The brute force approach is a straightforward way to solve the Two Sum problem. While it may not be the most efficient solution, it is useful for understanding the logic behind the problem. Once the concept is clear, more optimized approaches like HashMap can be implemented.