Dual Element Summation — Problem Statement & Solution Guide
Problem Description
You are given a sorted array of distinct integers numbers. Determine whether there exist two elements in the array that add up to a specified target sum targetSum. If such a pair exists, return the indices of these two elements in the array. If the input array contains duplicate elements, return the indices of the first pair of elements that add up to the target sum. Otherwise, return an empty array.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Dual Element Summation"
WHY DOES IT MATTER?
Two‑pointer is a fundamental pattern for any problem that requires pairwise comparison in a sorted structure. It reduces quadratic work to linear, which is critical for scalability in interview settings and production code where input sizes can be massive.
OPTIMIZATION CHALLENGE
The key insight is that the sorted order gives a total ordering of sums; moving the left pointer always increases the sum, moving the right pointer always decreases it. This monotonicity lets us discard entire sub‑ranges after a single comparison.
REAL-WORLD CONNECTION
Think of a warehouse loading dock where the lightest package is paired with the heaviest to fill a truck to a target weight. By always adjusting the lightest or heaviest package based on the current load, you quickly converge to the optimal loading without trying every combination.
During an interview, write the two‑pointer loop first, then add the early‑exit condition for the first pair. Keep the code tight: while (left < right) { const sum = arr[left] + arr[right]; if (sum === target) return [left, right]; sum < target ? left++ : right--; }
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The two‑sum problem on a sorted array can be solved in linear time using the two‑pointer technique. By placing one pointer at the start (the smallest element) and another at the end (the largest element), we can evaluate the sum of the pointed values and adjust pointers based on whether the current sum is less than or greater than the target. This works because the array is sorted: moving the left pointer right increases the sum, while moving the right pointer left decreases it. Naïve brute‑force enumeration of all pairs requires O(n²) time, which quickly becomes prohibitive for large inputs (e.g., n > 10⁵) due to the quadratic explosion of pair checks. The optimal paradigm leverages order information to prune the search space dramatically, achieving O(n) time with O(1) extra space, which is the best possible for this problem when only indices are required.
When duplicate values are present, the same two‑pointer logic still applies, but we must be careful to return the first occurring pair in index order. This can be achieved by stopping the scan as soon as a valid pair is found, because the pointers move monotonically and the first hit corresponds to the smallest left index. The algorithm therefore combines the benefits of sorted‑array properties with a deterministic stopping condition, delivering both correctness and optimal performance.
Interview Questions on This Problem
Q1How would you modify the two‑pointer solution if the array were not sorted?
Use a hash map to store each number and its index while iterating; for each element, check if target‑value‑element exists in the map. This yields O(n) time and O(n) space.
Q2Can you extend the algorithm to find all unique pairs that sum to the target in a sorted array with possible duplicates?
Yes. After finding a valid pair, move both pointers past any duplicate values (skip equal elements) and continue the scan. This ensures each distinct value pair is reported once, still in O(n) time.
Q3Why is the two‑pointer technique considered a "two‑sum on a sorted array" pattern, and where else does this pattern appear in real systems?
The pattern exploits monotonic ordering to eliminate half the search space at each step, similar to merging two sorted streams or finding a meeting point in a distributed log. It appears in problems like finding a pair with a given difference, merging k‑sorted lists, and in load‑balancing where you match smallest and largest tasks to meet a capacity constraint.
Examples
Input
[2, 7, 11, 15], 9
Output
[0, 1]
Explanation: Step-by-step: Given the input array [2, 7, 11, 15] and the target sum 9, we can see that the elements at indices 0 and 1 (2 and 7) add up to 9. Therefore, the output should be [0, 1].
Input
[3, 2, 4], 6
Output
[1, 2]
Explanation: Step-by-step: Given the input array [3, 2, 4] and the target sum 6, we can see that the elements at indices 1 and 2 (2 and 4) add up to 6. Therefore, the output should be [1, 2].
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Use two pointers at the opposite ends of the sorted array, moving them inward based on the comparison of the current sum with the target, achieving linear time.
Brute Force Approach
Check every possible pair of indices with two nested loops and return the first pair whose values add up to the target.
Verified Code Solutions
function twoSum(nums, targetSum) {
const numMap = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = targetSum - nums[i];
if (numMap.has(complement)) {
return [numMap.get(complement), i];
}
numMap.set(nums[i], i);
}
return [];
}class Solution {
public:
vector<int> twoSum(vector<int>& nums, int targetSum) {
unordered_map<int, int> numMap;
for (int i = 0; i < nums.size(); i++) {
int complement = targetSum - nums[i];
if (numMap.find(complement) != numMap.end()) {
return { numMap[complement], i };
}
numMap[nums[i]] = i;
}
return {};
}
};class Solution {
public int[] twoSum(int[] nums, int targetSum) {
Map<Integer, Integer> numMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = targetSum - nums[i];
if (numMap.containsKey(complement)) {
return new int[] { numMap.get(complement), i };
}
numMap.put(nums[i], i);
}
return new int[] {};
}
}def twoSum(nums, targetSum):
num_map = {}
for i in range(len(nums)):
complement = targetSum - nums[i]
if complement in num_map:
return [num_map[complement], i]
num_map[nums[i]] = i
return []function twoSum(nums, targetSum) {
const numMap = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = targetSum - nums[i];
if (numMap.has(complement)) {
return [numMap.get(complement), i];
}
numMap.set(nums[i], i);
}
return [];
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.