Two Sum Solution for Accenture

Company: Accenture · Difficulty: Easy · Topics: Array, Hash Table

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.

Key Understanding:

We need to find exactly two numbers that sum to the target
We must return the indices (positions) of these numbers, not the numbers themselves
There is exactly one valid answer (guaranteed by constraints)
The same element cannot be used twice (must be different indices)
The order of indices doesn't matter

Examples

Example 1:

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

Output: [0,1]

Explanation:

nums[0] = 2, nums[1] = 7
2 + 7 = 9 (target)
Return indices [0,1]
Visual representation: [2,7,11,15] → indices 0 and 1 sum to 9

Example 2:

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

Output: [1,2]

Explanation:

nums[1] = 2, nums[2] = 4
2 + 4 = 6 (target)
Return indices [1,2]
Visual representation: [3,2,4] → indices 1 and 2 sum to 6

Example 3:

Input: nums = [3,3], target = 6

Output: [0,1]

Explanation:

nums[0] = 3, nums[1] = 3
3 + 3 = 6 (target)
Return indices [0,1]
Note: Same value but different indices

Example 4:

Input: nums = [1,5,8,10,13], target = 18

Output: [2,4]

Explanation:

nums[2] = 8, nums[4] = 10
8 + 10 = 18 (target)
Return indices [2,4]

Intuition

The key insight is that for each number, we need to find its complement (target - current_number) in the array. If we can find this complement efficiently, we've solved the problem.

Core Concept:

For any number x in the array, we need to find if (target - x) exists
If we find the complement, we have our answer
We can use a hash table to store numbers we've seen and their indices
This allows us to check for complements in O(1) time

Why Hash Table Works:

Hash table provides O(1) average time for insert and lookup
We can store each number and its index as we process the array
For each new number, we check if its complement is already in the hash table
If found, we have our answer; if not, we add the current number to the hash table

Approach

Approach 1: Hash Table (Optimal)

Algorithm:

1. Create an empty hash table to store numbers and their indices

2. Iterate through the array from left to right

3. For each number nums[i]:

Calculate complement = target - nums[i]
Check if complement exists in hash table
If found, return [complement_index, i]
If not found, add {nums[i]: i} to hash table

4. If no solution found, return empty array (shouldn't happen per constraints)

Why This Works:

We process each element exactly once
For each element, we check if we've seen its complement before
If we find the complement, we have our answer
If not, we store the current element for future lookups

Complexity Analysis:

Time: O(n) - Single pass through the array
Space: O(n) - Hash table stores at most n elements

Approach 2: Two Pointer (Requires Sorting)

Algorithm:

1. Create pairs of (value, original_index) for each element

2. Sort these pairs by value

3. Use two pointers: left at start, right at end

4. While left < right:

Calculate sum = left_value + right_value
If sum == target, return [left_index, right_index]
If sum < target, move left pointer right
If sum > target, move right pointer left

5. If no solution found, return empty array

Why This Works:

After sorting, we can use two pointers to find pairs efficiently
If sum is too small, we need a larger left value
If sum is too large, we need a smaller right value
This approach works because the array is sorted

Complexity Analysis:

Time: O(n log n) - Due to sorting
Space: O(n) - To store pairs with original indices

Approach 3: Brute Force

Algorithm:

1. Use nested loops to check all possible pairs

2. Outer loop: i from 0 to n-2

3. Inner loop: j from i+1 to n-1

4. For each pair (i, j):

Check if nums[i] + nums[j] == target
If yes, return [i, j]

5. If no solution found, return empty array

Why This Works:

We check every possible pair of elements
Guaranteed to find the solution if it exists
Simple but inefficient approach

Complexity Analysis:

Time: O(n²) - We check n(n-1)/2 pairs
Space: O(1) - No extra space needed

Dry Run

Let's trace through Example 1: nums = [2,7,11,15], target = 9

Hash Table Approach:

Initial State: hash_table = {}, i = 0

Step 1: i = 0, num = 2

complement = target - num = 9 - 2 = 7
Check if 7 exists in hash_table: No
Add {2: 0} to hash_table
hash_table = {2: 0}

Step 2: i = 1, num = 7

complement = target - num = 9 - 7 = 2
Check if 2 exists in hash_table: Yes (at index 0)
Found solution: [0, 1]
Return [0, 1]

Two Pointer Approach:

Step 1: Create pairs with original indices

pairs = [(2,0), (7,1), (11,2), (15,3)]

Step 2: Sort pairs by value

pairs = [(2,0), (7,1), (11,2), (15,3)] (already sorted)

Step 3: Two pointer search

left = 0, right = 3
sum = 2 + 15 = 17 > 9, move right to 2
left = 0, right = 2
sum = 2 + 11 = 13 > 9, move right to 1
left = 0, right = 1
sum = 2 + 7 = 9 == target
Return [0, 1]

Brute Force Approach:

Step 1: Check all pairs

(0,1): nums[0] + nums[1] = 2 + 7 = 9 ✓
Found solution: [0, 1]
Return [0, 1]

Key Insights

1. Complement Strategy: For each number, look for its complement (target - number)

2. Hash Table Efficiency: O(1) average time for insert and lookup

3. Single Pass: Hash table approach requires only one pass through the array

4. Index Preservation: Need to store both values and their original indices

5. Unique Solution: Problem guarantees exactly one valid answer

Edge Cases

1. Two Same Numbers: nums = [3,3], target = 6 → [0,1] (same value, different indices)

2. Large Numbers: Handle integer overflow in calculations

3. Negative Numbers: Hash table approach works with negative numbers

4. Single Element: Not possible (constraints: 2 ≤ nums.length)

5. No Solution: Not possible (constraints: exactly one valid answer exists)

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: Hash Table (Optimal)

Time Complexity: O(n) - We traverse the array once

Space Complexity: O(n) - We store at most n elements in hash table

Advantages:

Most efficient time complexity
Single pass through array
Works with any input array (no sorting required)
Handles all edge cases

Disadvantages:

Uses extra space for hash table
Requires hash table implementation
May have hash collisions (though rare with good hash function)

Solution 2: Two Pointer (Requires Sorting)

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

Space Complexity: O(n) to store original indices

Advantages:

No hash table required
Can be extended to find all pairs
Good for understanding two pointer technique

Disadvantages:

Requires sorting (modifies original array or needs extra space)
Higher time complexity
More complex implementation

Solution 3: Brute Force

Time Complexity: O(n²) - We check n(n-1)/2 pairs

Space Complexity: O(1) - No extra space needed

Advantages:

Simple and straightforward
No extra space required
Easy to understand and implement

Disadvantages:

Highly inefficient for large arrays
Time complexity grows quadratically
Not suitable for production use