Leetcode: 1. Two Sum (Brute Force)

 

Efficiently Solving the Two-Sum Problem in C++: A Detailed Walkthrough

Have you ever encountered a situation where you're given an array of integers and a target sum, and you're tasked to find two numbers that add up to the target? If you have, then you've encountered the famous Two-Sum problem. Today, we'll explore how to solve this problem in C++ with a brute force approach. But first, let's understand the problem statement a bit more.

Problem Statement:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. We may assume that each input would have exactly one solution, and we cannot use the same element twice.

Brute Force Solution:

    
#include <vector>

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = i + 1; j < nums.size(); ++j) {
                if (nums[i] + nums[j] == target) {
                    return std::vector<int> {i, j};
                }
            }
        }
        return std::vector<int> {};
    }
};
    
  

To explain this code, we have a function twoSum which receives a vector of integers nums and an integer target. We iterate over nums with two nested loops. The outer loop iterates over all numbers, and the inner loop starts from the next number to avoid using the same element twice. If the sum of the two numbers equals the target, we return their indices in a vector.

For example, let's consider an array nums = [2, 7, 11, 15] and target = 9. The function twoSum(nums, target) would return [0, 1] because nums[0] and nums[1] are 2 and 7 respectively, and they add up to the target sum of 9.

While this brute force solution works perfectly fine for small arrays, it is not efficient for larger ones due to its time complexity of O(n^2). In computer science, time complexity is a measure that describes the amount of computer time taken by an algorithm to run, as a function of the size of the input to the program. A time complexity of O(n^2) means that as the input size (n) increases, the time it takes for the program to run will increase quadratically.

Complexity Analysis:

Time Complexity:

The time complexity of our brute force solution is O(n²). The outer loop runs n times, and for each iteration of the outer loop, the inner loop runs n times in the worst case scenario. Therefore, the total number of iterations in the worst case scenario is n*n = n². This means that as the size of the input increases, the time it takes for our program to run increases quadratically.

Space Complexity:

The space complexity of our solution is O(1), or constant space. This is because the amount of memory used does not change with the size of the input array, and is therefore constant.

Conclusion:

While this solution works for small inputs, it can be very slow for large inputs due to its quadratic time complexity. In a future post, we'll examine a more efficient solution with a linear time complexity of O(n). Stay tuned!