1. Two Sum

LeetCode 1: Two Sum Solution & Explanation

Problem Overview

TL;DR: Store the original indices, sort the array based on values, and use two converging pointers to find the pair that sums to the target.

The LeetCode 1 problem asks us to identify two distinct numbers in an integer array nums that add up to a specific target value. We must return the original indices of these two numbers. The problem guarantees exactly one valid solution exists, and we cannot use the same element twice. While a brute force approach is intuitive, optimal interview solutions require reducing the time complexity significantly.

Brute Force Approach for Two Sum

The naive approach involves checking every possible pair of numbers in the array to see if they add up to the target. This is typically implemented using nested loops.

Pseudo-code:

for i from 0 to n-1:
    for j from i+1 to n-1:
        if nums[i] + nums[j] == target:
            return [i, j]

Time Complexity: $O(n^2)$ Why it fails: While this solution is correct, the quadratic time complexity makes it inefficient for large inputs ($N \le 10^4$). In an interview context, an $O(n^2)$ solution is rarely considered sufficient when linear or log-linear solutions exist.

Algorithm Strategy: Two Pointers

1. Data Transformation: Create a new list of pairs/objects where each element contains {value, original_index}.
2. Sort: Sort this new list in ascending order based on the value.
3. Initialize Pointers: Set left to 0 (start of list) and right to n - 1 (end of list).
4. Converge: Loop while left < right:
   • Calculate current_sum = sorted_list[left].value + sorted_list[right].value.
   • Match: If current_sum == target, return [sorted_list[left].original_index, sorted_list[right].original_index].
   • Too Low: If current_sum < target, increment left to increase the sum.
   • Too High: If current_sum > target, decrement right to decrease the sum.

Execution Flow

Consider Input: nums = [3, 2, 4], target = 6

1. Map Indices: [(3, 0), (2, 1), (4, 2)] (Format: (value, index))

2. Sort: [(2, 1), (3, 0), (4, 2)]

3. Iteration 1:

   • left points to (2, 1) at index 0.
   • right points to (4, 2) at index 2.
   • current_sum = $2 + 4 = 6$.
   • current_sum equals target.

4. Result: Found match. Return original indices: [1, 2].

Proof of Correctness

The algorithm is correct because the sorted order allows us to eliminate search space deterministically.

• If nums[left] + nums[right] < target, then nums[left] is too small to pair with nums[right]. Since nums[right] is the largest available number, nums[left] cannot pair with any other available number to reach the target. Thus, nums[left] can be safely discarded (increment left).
• Conversely, if nums[left] + nums[right] > target, nums[right] is too large to pair with nums[left] (the smallest available). It can be safely discarded (decrement right).
• Since the problem guarantees a solution exists, the pointers will eventually converge on the correct pair.

Pattern Reuse Notes

The Two Pointers (Converging) pattern used here is foundational for several other array problems.

• 3Sum (LeetCode 15): Reduces to Two Sum after fixing one number.
• 4Sum (LeetCode 18): Reduces to 3Sum, then Two Sum.
• Two Sum II - Input Array Is Sorted (LeetCode 167): Identical to this solution but without the need to store indices or sort (since input is pre-sorted).

Reference Implementation

C++ Solution for LeetCode 1

1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8    vector<int> twoSum(vector<int>& nums, int target) {
9        // Store pairs of (value, original_index)
10        vector<pair<int, int>> nums_with_indices;
11        for (int i = 0; i < nums.size(); ++i) {
12            nums_with_indices.push_back({nums[i], i});
13        }
14        
15        // Sort based on values
16        sort(nums_with_indices.begin(), nums_with_indices.end());
17        
18        int left = 0;
19        int right = nums.size() - 1;
20        
21        // Two Pointers convergence
22        while (left < right) {
23            int sum = nums_with_indices[left].first + nums_with_indices[right].first;
24            
25            if (sum == target) {
26                return {nums_with_indices[left].second, nums_with_indices[right].second};
27            } else if (sum < target) {
28                left++; // Need a larger sum
29            } else {
30                right--; // Need a smaller sum
31            }
32        }
33        
34        return {}; // Should not be reached per problem constraints
35    }
36};

Java Solution for LeetCode 1

1import java.util.Arrays;
2
3class Solution {
4    public int[] twoSum(int[] nums, int target) {
5        // Create a 2D array to store value and original index
6        int[][] numsWithIndices = new int[nums.length][2];
7        
8        for (int i = 0; i < nums.length; i++) {
9            numsWithIndices[i][0] = nums[i]; // Value
10            numsWithIndices[i][1] = i;       // Original Index
11        }
12        
13        // Sort based on values (column 0)
14        Arrays.sort(numsWithIndices, (a, b) -> Integer.compare(a[0], b[0]));
15        
16        int left = 0;
17        int right = nums.length - 1;
18        
19        while (left < right) {
20            int sum = numsWithIndices[left][0] + numsWithIndices[right][0];
21            
22            if (sum == target) {
23                return new int[]{numsWithIndices[left][1], numsWithIndices[right][1]};
24            } else if (sum < target) {
25                left++;
26            } else {
27                right--;
28            }
29        }
30        
31        return new int[]{};
32    }
33}

Python Solution for LeetCode 1

1class Solution:
2    def twoSum(self, nums: List[int], target: int) -> List[int]:
3        # Store pairs of (value, original_index)
4        nums_with_indices = []
5        for i, num in enumerate(nums):
6            nums_with_indices.append((num, i))
7            
8        # Sort based on values (first element of tuple)
9        nums_with_indices.sort(key=lambda x: x[0])
10        
11        left = 0
12        right = len(nums) - 1
13        
14        while left < right:
15            current_sum = nums_with_indices[left][0] + nums_with_indices[right][0]
16            
17            if current_sum == target:
18                return [nums_with_indices[left][1], nums_with_indices[right][1]]
19            elif current_sum < target:
20                left += 1
21            else:
22                right -= 1
23                
24        return []