Definition
- Two-pointer technique – place
leftat index 0 andrightat the last index of a sorted array, then move them toward each other. - Sum comparison – compute
arr[left] + arr[right]; if it equals the target, return both indices; if it exceeds the target, decrementright; if it falls short, incrementleft. - Correctness – the sorted order ensures that when the sum is too large,
rightcan never be part of the answer with thisleft, so it is safely discarded. - Complexity – O(n) time because each element is visited at most once; O(1) extra space.
- Precondition – the array must be sorted for the two-pointer elimination logic to work.
Rajesh at the National Bank of India has a sorted list of pending settlement amounts and needs to find exactly two settlements that together clear a target obligation. Instead of checking every possible pair, Priya stands at the smallest amount and Rajesh at the largest. If their two amounts add up to more than the target, Rajesh steps down. If they add up to less, Priya steps up. They walk toward each other until the two amounts hit the target exactly.
Understanding the Concepts
What is the pair with target sum problem?
Given a sorted array and a target sum, find two elements that add up exactly to the target and return their indices. The brute-force approach checks every pair in O(n^2) time. On a sorted array the two-pointer technique solves it in O(n) time and O(1) space.
package com.bank.core;
public class PairTargetSum {
public static int[] findPair(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
return new int[]{left, right};
} else if (sum > target) {
right--;
} else {
left++;
}
}
return new int[]{-1, -1};
}
public static void main(String[] args) {
int[] settlements = {150, 300, 450, 700, 950};
int target = 750;
int[] result = findPair(settlements, target);
System.out.println("Indices: [" + result[0] + ", " + result[1] + "]");
System.out.println("Values: " + settlements[result[0]] + " + "
+ settlements[result[1]] + " = " + target);
}
}
Indices: [1, 2]
Values: 300 + 450 = 750
Why does the two-pointer technique work?
The correctness relies on the sorted order. When arr[left] + arr[right] is too large, pairing arr[right] with anything to the left of the current left would be even smaller, but pairing it with anything to the right of the current left would not help because we already know the sum is too big with the current largest right. So right can never be part of the answer with this or any larger left, and we safely discard it. The same reasoning applies symmetrically when the sum is too small.
package com.bank.core;
public class TwoPointerReasoning {
public static void main(String[] args) {
int[] arr = {100, 200, 300, 400, 500};
int target = 600;
int left = 0, right = 4;
// sum = 100 + 500 = 600 → found!
System.out.println("left=" + left + " right=" + right
+ " sum=" + (arr[left] + arr[right]));
// If sum were 700 (too big), right=4 (500) paired with anything
// to the right of left would still be >= 600, so right is safely discarded
}
}
left=0 right=4 sum=600
How is two-pointer different from a HashMap approach?
The HashMap approach stores each element's required complement and runs in O(n) time even on unsorted arrays, but uses O(n) space. The two-pointer approach uses O(1) space but requires the array to be sorted. If the data arrives already sorted, two-pointer is strictly better on space.
| Aspect | Two-pointer | HashMap |
|---|---|---|
| Precondition | Array sorted | None |
| Time | O(n) | O(n) |
| Space | O(1) | O(n) |
| Returns original indices? | Yes (if sorted in place) | Yes |
| Works on unsorted? | No | Yes |
package com.bank.core;
import java.util.HashMap;
import java.util.Map;
public class HashMapApproach {
public static int[] findPairHashMap(int[] arr, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
int complement = target - arr[i];
if (seen.containsKey(complement)) {
return new int[]{seen.get(complement), i};
}
seen.put(arr[i], i);
}
return new int[]{-1, -1};
}
public static void main(String[] args) {
int[] unsorted = {700, 150, 950, 300, 450};
int target = 750;
int[] result = findPairHashMap(unsorted, target);
System.out.println("HashMap indices: [" + result[0] + ", " + result[1] + "]");
}
}
HashMap indices: [1, 3]
What about returning one-based indices?
LeetCode Two Sum II returns one-based indices. Simply add one to each zero-based result.
package com.bank.core;
public class OneBasedIndices {
public static int[] findPairOneBased(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) return new int[]{left + 1, right + 1};
else if (sum > target) right--;
else left++;
}
return new int[]{-1, -1};
}
public static void main(String[] args) {
int[] arr = {150, 300, 450, 700, 950};
int[] result = findPairOneBased(arr, 750);
System.out.println("One-based: [" + result[0] + ", " + result[1] + "]");
}
}
One-based: [2, 3]
What are the edge cases?
Edge cases include no valid pair, a two-element array, negative numbers, and duplicate values.
package com.bank.core;
import java.util.Arrays;
public class PairEdgeCases {
public static int[] findPair(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) return new int[]{left, right};
else if (sum > target) right--;
else left++;
}
return new int[]{-1, -1};
}
public static void main(String[] args) {
System.out.println("No pair: " + Arrays.toString(findPair(new int[]{1, 2, 3}, 10)));
System.out.println("Two elem: " + Arrays.toString(findPair(new int[]{3, 7}, 10)));
System.out.println("Negatives: " + Arrays.toString(findPair(new int[]{-5, -2, 1, 4, 8}, 2)));
System.out.println("Duplicates: " + Arrays.toString(findPair(new int[]{3, 3, 4, 5}, 6)));
}
}
No pair: [-1, -1]
Two elem: [0, 1]
Negatives: [1, 3]
Duplicates: [0, 1]
How does this generalize to three-sum and four-sum?
The pair-with-target-sum is the building block for three-sum and four-sum problems. For three-sum, fix one element and run the two-pointer technique on the rest. For four-sum, fix two elements and run the two-pointer technique.
package com.bank.core;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum {
public static List<List<Integer>> threeSum(int[] arr, int target) {
Arrays.sort(arr);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < arr.length - 2; i++) {
if (i > 0 && arr[i] == arr[i - 1]) continue;
int left = i + 1, right = arr.length - 1;
while (left < right) {
int sum = arr[i] + arr[left] + arr[right];
if (sum == target) {
result.add(Arrays.asList(arr[i], arr[left], arr[right]));
while (left < right && arr[left] == arr[left + 1]) left++;
while (left < right && arr[right] == arr[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {-500, -200, 0, 100, 200, 300, 500};
System.out.println("Triplets summing to 0: " + threeSum(arr, 0));
}
}
Triplets summing to 0: [[-500, 0, 500], [-500, 200, 300], [-200, 0, 200]]
What about using BigDecimal for financial amounts?
In banking applications, financial amounts must use BigDecimal to avoid floating-point rounding errors. The two-pointer logic is the same, but comparisons use compareTo instead of arithmetic operators.
package com.bank.core;
import java.math.BigDecimal;
public class PairBigDecimal {
public static int[] findPair(BigDecimal[] arr, BigDecimal target) {
int left = 0, right = arr.length - 1;
while (left < right) {
BigDecimal sum = arr[left].add(arr[right]);
int cmp = sum.compareTo(target);
if (cmp == 0) return new int[]{left, right};
else if (cmp > 0) right--;
else left++;
}
return new int[]{-1, -1};
}
public static void main(String[] args) {
BigDecimal[] settlements = {
new BigDecimal("1500.50"),
new BigDecimal("3000.75"),
new BigDecimal("4500.25"),
new BigDecimal("7000.00")
};
BigDecimal target = new BigDecimal("7501.00");
int[] result = findPair(settlements, target);
System.out.println("Pair: [" + result[0] + ", " + result[1] + "]");
System.out.println("Values: " + settlements[result[0]] + " + "
+ settlements[result[1]] + " = " + target);
}
}
Pair: [1, 2]
Values: 3000.75 + 4500.25 = 7501.00
What should a senior engineer know?
A senior engineer should know three things. First, the two-pointer method depends on the array being sorted; if it is not, sorting first costs O(n log n), and a hash-map approach might be better. Second, this technique generalizes to closest-sum, three-sum, and four-sum problems by nesting the two-pointer sweep inside one or two outer loops. Third, in production banking code, all monetary amounts should use BigDecimal to avoid floating-point rounding errors that could cause audit discrepancies.
Visual Overview
Array: [150, 300, 450, 700, 950] Target: 750
Step 1: left=0 (150) right=4 (950)
sum = 150 + 950 = 1100 > 750 → right--
Step 2: left=0 (150) right=3 (700)
sum = 150 + 700 = 850 > 750 → right--
Step 3: left=0 (150) right=2 (450)
sum = 150 + 450 = 600 < 750 → left++
Step 4: left=1 (300) right=2 (450)
sum = 300 + 450 = 750 == 750 → FOUND [1, 2]
┌─────────────────────────────────────┐
│ left ──→ ←── right │
│ [150, 300, 450, 700, 950] │
│ ↑ ↑ │
│ Squeeze inward until sum matches │
└─────────────────────────────────────┘
Key Takeaway
The pair-with-target-sum problem asks you to find two elements in a sorted array whose values add up to a given target, and the clean solution is the two-pointer technique that runs in O(n) time and O(1) space. You place one pointer at the start and one at the end, compute the sum of the two values they point to, and move the pointers inward based on whether the sum is too large or too small.
The core insight is the sorted order. When the current sum exceeds the target, the only way to make it smaller is to move the right pointer inward to a smaller value, and you can safely discard the old right element because pairing it with anything to the left would only make the sum larger. When the sum falls short, you move the left pointer for the same reason in reverse. Each step permanently eliminates one element, so every element is touched at most once.
In Rajesh's work at the National Bank of India, the clearing system returns outstanding settlement amounts in sorted order, and the regulator sometimes requires showing that a specific target obligation can be cleared by combining exactly two transactions. A brute-force pair check over hundreds of thousands of transactions would miss the settlement window, so the two-pointer sweep gives the answer in a single linear pass.
The senior-level point is about preconditions. The two-pointer method depends on the array being sorted. If the input is not sorted, you either sort it first at O(n log n) cost or switch to a hash-map approach that runs in O(n) without sorting. Choosing between those depends on whether the data arrives sorted and whether you need the original indices, and being explicit about that tradeoff separates someone who memorized a trick from someone who understands when to use it.
Remember one sentence: start with pointers at both ends of a sorted array and squeeze inward, moving the pointer that makes the sum closer to the target each step.
---