Problem Statement:

Given an array of integers nums and an integer target, find two different numbers in the array that add up to the target. Return their indices.

You are guaranteed that exactly one solution exists, and you cannot use the same element twice.

🔍 Example:

🎯 Goal

1. Find two numbers that add up to a given target.
2. For each number, find target - current number.
3. Check if this value exists elsewhere in the array.
4. If found, return the indices.

🗾 Algorithm Steps (Simple Logic)

1.Loop through the array.

2.For each number, find target - current number.

3.Check if this value exists elsewhere in the array.

4.If found, return the indices.

🔄 Brute Force Approach

Idea: Try every pair of numbers and check if their sum equals the target.

Time Complexity: O(n²)

✨ C++ Code:

#include <iostream>
#include <vector>
using namespace std;

vector<int> twoSum(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 {i, j};
            }
        }
    }
    return {};
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSum(nums, target);
    if (!result.empty()) {
        cout << "Indices: " << result[0] << ", " << result[1] << endl;
    } else {
        cout << "No solution found." << endl;
    }
    return 0;
}

📄 C Code:

#include <stdio.h>
#include <stdlib.h>

// Function to find two indices such that nums[i] + nums[j] == target
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] + nums[j] == target) {
                int* res = (int*)malloc(2 * sizeof(int));
                res[0] = i;
                res[1] = j;
                *returnSize = 2;
                return res;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int returnSize;
    int* result = twoSum(nums, 4, target, &returnSize);

    if (result != NULL) {
        printf("Indices: %d, %d
", result[0], result[1]);
        free(result);
    } else {
        printf("No solution found.
");
    }

    return 0;
}
        }
    }
    *returnSize = 0;
    return NULL;
}

📄 Java Code:

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

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        if (result.length == 2) {
            System.out.println("Indices: " + result[0] + ", " + result[1]);
        } else {
            System.out.println("No solution found.");
        }
    }
}
   

⚡ Optimized Approach Using Hash Map (Best for Unsorted)

Idea: Store each number's index in a hash map while traversing. For each number, check if target - number exists in the map.

Time: O(n), Space: O(n)

✨ Java Code:

import java.util.HashMap;
import java.util.Map;

public class TwoSumHashMap {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];
            if (map.containsKey(diff)) {
                return new int[]{map.get(diff), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{};
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        if (result.length == 2) {
            System.out.println("Indices: " + result[0] + ", " + result[1]);
        } else {
            System.out.println("No solution found.");
        }
    }
}

C++ Code:

unordered_map<int, int> numMap;
for (int i = 0; i < nums.size(); i++) {
    int diff = target - nums[i];
    if (numMap.find(diff) != numMap.end()) {
        return {numMap[diff], i};
    }
    numMap[nums[i]] = i;
}

⚖️ Optimized Without Hash Map (Two Pointers)

📌 Requirements:

Array must be sorted.

Idea: Use two pointers from both ends.

✨ C++ Code:

vector<int> twoSum(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return {left, right};
        else if (sum < target) left++;
        else right--;
    }
    return {};
}

✨ Java Code:

public int[] twoSumSorted(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;
        else right--;
    }
    return new int[]{};
}

3Sum

Problem:

Given an integer array nums, return all the unique triplets [nums[i], nums[j],

nums[k]] such that i != j != k and nums[i] + nums[j] + nums[k] == 0.

✅ Optimal Approach (Two Pointers)

1.Sort the array.

2.Iterate through the array, fixing one number at a time.

3.Use two pointers (left and right) to find the remaining two numbers that sum to the negative of the fixed number.

4.Skip duplicates to ensure unique triplets.

📦 Time Complexity:

O(n^2) – Sorting takes O(n log n), and each pair search takes O(n).

✨ C++ Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                res.push_back({nums[i], nums[left], nums[right]});
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++; right--;
            }
        }
    }
    return res;
}

int main() {
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> result = threeSum(nums);
    for (auto triplet : result) {
        for (int num : triplet) cout << num << " ";
        cout << endl;
    }
    return 0;
}

✨ Java Code:

public class ThreeSum {
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) left++;
                else if (sum > 0) right--;
                else {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++; right--;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> result = threeSum(nums);
        for (List<Integer> triplet : result) {
            System.out.println(triplet);
        }
    }
}

Summary Table

📊 Advanced Questions on Time and Space Complexity

1. Can you solve Two Sum in O(n log n) time without using extra space?

Answer:

Yes. First, sort the array (O(n log n)). Then use the two-pointer approach (O(n)) to find the pair.

Time Complexity: O(n log n) (due to sorting)

Space Complexity: O(1) (no extra space if sorting is done in-place)

Tradeoff: You lose the original indices unless tracked separately.

2. Why does 3Sum have O(n²) time complexity?

Answer:

Sort the array (O(n log n)).

Then fix one element and apply the Two Sum with two-pointer approach for the rest (O(n²) overall because of the nested loop).

Time Complexity: O(n²)

Space Complexity: O(1) (excluding the output list)

3. What is the most space-efficient way to solve 3Sum?

Answer:

Using the two-pointer approach after sorting the array.

No need for hash maps.

Time Complexity: O(n²)

Space Complexity: O(1) (excluding output)

4. Can 4Sum be solved in O(n²) time?

Answer:

No.

4Sum requires at least two nested loops, each with a two-pointer approach.

Best Time Complexity: O(n³)

Space Complexity: O(1) (excluding output)

5. Why is the Two Pointer method not always usable?

Answer:

Because it needs the array to be sorted. If input is unsorted and you need original indices, sorting breaks that unless you store index pairs.

6. What’s the difference in output between 2Sum and 3Sum problems?

2Sum: Return one pair of indices.

3Sum: Return all unique triplets; requires duplicate handling.

7. Can we reduce the space complexity of 4Sum?

Answer:

Yes, by avoiding hash maps and using sorting + two-pointers:

Time: O(n³)

Space: O(1) (excluding output)

However, code is more complex, and runtime might increase due to more nested loops.

8. Why do some variants (like 4Sum II) use hash maps while others don't?

Answer:

In 4Sum II (Leetcode #454), we split the problem into 2 + 2 and use hash maps to store combinations of A and B.

It drastically reduces complexity from O(n⁴) to O(n²).

Time: O(n²)

Space: O(n²)