2 Sum Problem

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9

Thought Process

The simplest way to solve this problem is by checking every possible pair of numbers in the array to see if their sum equals the given target. Since we don’t have any constraints on efficiency yet, we can use a nested loop to iterate through all possible pairs.

Step-by-Step Explanation

1. We iterate over the array using an outer loop (variable i), selecting one element at a time.

2. Inside this loop, we use an inner loop (variable j) to iterate over the remaining elements after i.

3. For each pair (nums[i], nums[j]), we check if their sum is equal to the target.

4. If we find a valid pair, we return their indices [i, j].

5. If no such pair is found, we return an empty list (or handle it accordingly).

Code Implementation in C++:

#include <bits/stdc++.h>
using namespace std;

vector twoSum(vector& nums, int target){

int n = nums.size();

for (int i = 0; i < n ; i++) {      // Outer loop (choosing first number)

for (int j = i + 1; j < n; j++) {  // Inner loop (choosing second number)

if (nums[i] + nums[j] == target) { return {i, j}; // Return indices if sum matches target

}

}

}

return {}; // Return empty vector if no pair found

}

int main() {

vector nums = {2, 7, 11, 15};

int target = 9;

vector result = twoSum(nums, target);

cout << result[0] << " " << result[1] << endl;

return 0;

}

Understanding the Time Complexity (O(n²))

To determine the time complexity, let's analyze how the loops behave:

• The outer loop (i) runs from 0 to n-1, meaning it executes n times.

• The inner loop (j) starts from i + 1 and runs up to n, meaning for each value of i, the inner loop executes at most (n-1), then (n-2), and so on.

This results in:

∑_(i=0)^(n-1)(n−i−1)=(n−1)+(n−2)+...+2+1 (sigma i=0 to n-1 (n-i-1))

This is the sum of the first (n-1) natural numbers, which is given by the formula:

((n−1)×n)/2=O(n^2)

Thus, the overall time complexity is O(n²), meaning that as the input size (n) grows, the execution time increases quadratically.

Why is O(n²) Considered Inefficient?

For small input sizes, this approach works fine. However, as n gets large (e.g., n = 10⁶ in competitive programming), the solution becomes too slow. The reason is that for large values of n, O(n²) computations take significantly longer than O(n) or O(log n) approaches.

Key Takeaways

✔ Easy to understand and implement
✔ Works well for small input sizes
❌ Becomes too slow for large arrays
❌ Not optimal in terms of efficiency

To improve this, we need a more optimized approach, which we’ll explore in the next solution using HashMaps (O(n)).

Problem link:https://leetcode.com/problems/two-sum/description/