Two PointersEasyO(n) time · O(1) space

Pair with Target Sum

Mahabharata — The Gambling Hall of Hastinapura

द्वौ पक्षौ समन्वेतौ लक्ष्यं प्राप्नुतः सदा। नान्यथा सिद्धिरस्ति च द्वयोः सङ्गमे विना॥

*Two wings united always reach the goal; there is no success without the meeting of two.*

The Story

The dice clattered across the sabha floor as Shakuni's crooked smile widened. The game was rigged, and everyone knew it—except Yudhishthira, lost in his dharmic fog, betting away kingdoms and brothers with the mechanical precision of a sleepwalker.

But in the shadows of that gambling hall, a different game was being played. Vidura, the wise minister, watched with calculating eyes. He had been given an impossible task by Bhishma: find two courtiers whose combined influence could sway the Kaurava elders to stop this madness before Draupadi was wagered.

"The target is clear," Bhishma had whispered. "We need exactly 108 units of political weight—the sacred number. Less won't move them. More will alert Duryodhana."

Vidura surveyed the assembly. The courtiers sat in order of their political influence, from the least powerful near the doors to the most powerful near the throne. Their values were known: 2, 7, 11, 15, 19, 26, 35, 42, 56, 67, 82, 91...

A young scribe beside Vidura suggested the obvious approach. "Minister, let me calculate every possible pair. I shall take Courtier A, then check his sum with Courtier B, then C, then D... then take Courtier B and sum with C, D, E..."

Vidura raised his hand. "And how many calculations would that require?"

The scribe's stylus moved rapidly. "For 100 courtiers... nearly 5,000 checks. But Minister, I can work fast—"

"By then, Draupadi will be dragged to this hall by her hair," Vidura said grimly. "We have minutes, not hours."

He studied the seated courtiers again. Ordered by influence. The least powerful on the left, the most on the right. Something stirred in his mind—an ancient technique taught by his father Vyasa.

"Watch," Vidura murmured to the scribe. "I will check only once per courtier, not once per pair."

He placed his left hand toward the least influential courtier—Sanjaya's young assistant, worth merely 11 units. His right hand pointed to the most powerful neutral party—old Kritavarma, worth 97 units.

"11 plus 97 gives 108," Vidura calculated instantly. "Found."

The scribe gaped. "But... how did you know where to start?"

"I didn't know," Vidura replied. "But I knew what to do if I was wrong. Had the sum exceeded 108, I would have moved my right hand leftward to a lesser influence. Had it fallen short, I would have moved my left hand rightward to a greater one. The ordering of the courtiers—this is the key. When values are sorted, two boundaries can search faster than one roving eye."

The scribe protested: "But what if you had needed 50? Sanjaya's assistant plus Kritavarma is already 108!"

"Then I would step," Vidura said. "11 + 97 = 108, too high for 50. Move right hand left: 11 + 82 = 93, still too high. Continue: 11 + 67 = 78. Still high. 11 + 56 = 67. 11 + 42 = 53. 11 + 35 = 46, too low now! So move left hand right: 15 + 35 = 50. Found."

"But this only works because they sit in order of influence!"

"Precisely," Vidura smiled. "And that is why the wise arrange their resources before searching them. Chaos serves the gambler; order serves the seeker."

The scribe watched in awe as Vidura signaled across the hall. Within moments, the two courtiers—worth exactly 108 combined—rose to speak. Their intervention delayed the game just long enough for Krishna's message to arrive.

Draupadi was saved that hour, though darker days awaited. But in that moment, Vidura had demonstrated a truth older than the Vedas: when elements are ordered and the target is known, two pointers converging from the extremes will find their meeting point faster than any exhaustive search.

"Remember this," Vidura told the scribe as chaos erupted around them. "When you seek a pair that sums to a target, let the boundaries speak to each other. Too high? Lower the ceiling. Too low? Raise the floor. They will meet at the answer, or reveal that no answer exists."

This is the Two Pointer technique for finding a pair with target sum.

The Scribe's First Instinct

The young scribe would check every possible pair—O(n²) comparisons. For each courtier, he sums with every other courtier to find the target.

java

public int[] findPairBruteForce(int[] influences, int target) {
    // The scribe checks every pair exhaustively
    for (int i = 0; i < influences.length; i++) {
        for (int j = i + 1; j < influences.length; j++) {
            // "Let me sum courtier i with courtier j..."
            if (influences[i] + influences[j] == target) {
                return new int[]{i + 1, j + 1}; // 1-indexed positions
            }
        }
    }
    // "No pair found after checking all combinations"
    return new int[]{};
}

Vidura's Wisdom

Vidura's insight: in a sorted array, start with pointers at both ends. If the sum is too high, the right pointer must decrease (move left). If too low, the left pointer must increase (move right). They converge toward the answer in O(n) time. The `left` pointer represents the least influential courtier being considered. The `right` pointer represents the most influential. Together, they narrow the search space with each comparison.

java

public int[] twoSum(int[] nums, int target) {
    // Vidura's left hand: least influential courtier
    int left = 0;
    // Vidura's right hand: most influential courtier
    int right = nums.length - 1;
    
    while (left < right) {
        int sum = nums[left] + nums[right];
        
        if (sum == target) {
            // "Found! These two courtiers together make 108"
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            // "Too low—we need more influence, move left hand right"
            left++;
        } else {
            // "Too high—we need less influence, move right hand left"
            right--;
        }
    }
    
    // "No valid pair exists"
    return new int[]{};
}

// Test with the courtiers' influence values
public static void main(String[] args) {
    int[] influences = {2, 7, 11, 15};
    int target = 9;
    int[] result = new Solution().twoSum(influences, target);
    System.out.println("Courtiers at positions: " + result[0] + " and " + result[1]);
    // Output: Courtiers at positions: 1 and 2 (values 2+7=9)
}

Step-by-Step Walkthrough

Array: [2, 7, 11, 15]  Target: 9

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 1: left=0 (value=2), right=3 (value=15)
        Sum = 2 + 15 = 17
        17 > 9 → Too high! Move right pointer left
        [2, 7, 11, 15]
         L          R→

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 2: left=0 (value=2), right=2 (value=11)
        Sum = 2 + 11 = 13
        13 > 9 → Still too high! Move right pointer left
        [2, 7, 11, 15]
         L      R→

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 3: left=0 (value=2), right=1 (value=7)
        Sum = 2 + 7 = 9
        9 == 9 → ✅ Found! Return [1, 2]
        [2, 7, 11, 15]
         L  R

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Result: Positions [1, 2] → Values 2 + 7 = 9

Deep Insight

**Why does this work?**

The invariant maintained: at any point, if a valid pair exists, it lies within the range [left, right]. When we move a pointer, we eliminate all pairs involving the excluded element—but these pairs were all guaranteed to be invalid.

**The mathematical guarantee:** - If `arr[left] + arr[right] > target`: Since the array is sorted, `arr[left] + arr[right-1] < arr[left] + arr[right]`. The current right element paired with ANY element gives a sum ≥ current sum. So `arr[right]` cannot be part of the answer pair, and we can safely exclude it. - If `arr[left] + arr[right] < target`: By similar logic, `arr[left]` cannot be part of the answer.

**Edge cases:** - Empty array or single element: Return empty (can't form a pair) - No valid pair exists: Pointers will cross (left ≥ right) - Multiple valid pairs: This approach finds one valid pair, not all

**When does it fail?** - Unsorted arrays: The technique requires sorted input - If you need ALL pairs: This finds one; use different approach for all

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²)	O(1)	For n=10,000 courtiers: 50,000,000 pair checks
Optimal	O(n)	O(1)	For n=10,000 courtiers: at most 10,000 operations

Pattern Recognition

✅ Array is sorted (or can be sorted)
✅ Looking for a pair/tuple with specific sum property
✅ Need to search from both ends simultaneously
✅ O(1) space constraint mentioned

**LeetCode Trigger Phrases:**
→ "sorted array... find two numbers that add up to"
→ "two indices... sum equals target"
→ "pair with given sum"

Bhagavad Gita 5.12

युक्तः कर्मफलं त्यक्त्वा शान्तिमाप्नोति नैष्ठिकीम्। अयुक्तः कामकारेण फले सक्तो निबध्यते॥

The balanced one, abandoning attachment to results, attains lasting peace. The unbalanced one, acting from desire, becomes bound by attachment to outcomes.

Connection: Like the two pointers that must work in balanced harmony—one moving only when appropriate, neither greedy nor hesitant—the algorithm achieves its goal through disciplined action. The left pointer doesn't jump forward eagerly; the right doesn't retreat rashly. Each moves only when the sum dictates, detached from premature conclusions, converging inevitably toward truth.