Sorted array में pair sum O(n) time और O(1) space में कैसे निकालोगे?

दो किनारे. एक सही pair. Let’s make it click.

Sorted line के दोनों ends पर दोस्त खड़े हैं. सबसे छोटा left पर, सबसे बड़ा right पर. Target sum बनाना है. हर possible pair try करने की जगह sum बताने दो कि कौन आगे बढ़ेगा.

Sum बड़ा? Right घटाओ. छोटा? Left बढ़ाओ.

[1, 2, 4, 6, 8, 11], target = 10. पहले 1 + 11 = 12. बड़ा है, तो 11 के साथ बाकी कोई larger-left value sum को और बढ़ाएगी. इसलिए right को safely discard करो. अब 1 + 8 = 9, छोटा है — left बढ़ाओ. 2 + 8 = 10, मिल गया.

Pointer move करने का reason sorting है. अगर input unsorted है, यही movement valid नहीं. तब HashMap O(n) expected time / O(n) space, या sort + pointers O(n log n), लेकिन original indices संभालने होंगे.

एक loop, पर proof दो pointers का

Brute force में n(n−1)/2 pairs: O(n²). Two pointers में हर iteration कम से कम एक pointer अंदर जाता है. Gap शुरू में n−1 है और फिर घटता रहता है. Total pointer moves n−1 से ज्यादा नहीं, इसलिए O(n).

Extra state सिर्फ left, right और sum है: O(1) space. Sorting पहले करनी पड़ी तो उसकी time/space अलग count करो. Java/C++ में addition overflow से बचने के लिए sum को long / long long में रख सकते हैं.

3Sum और water container — same family, अलग reason

3Sum में एक number fix करो और बचे sorted suffix पर pair sum. Outer loop O(n), inner pointers O(n), total O(n²). Duplicate answers से बचने के लिए equal fixed values और matched pointer values skip करो.

Container With Most Water में order sorted नहीं है. यहाँ shorter wall को move करते हैं, क्योंकि width घटने पर उसी shorter wall के रहते area बढ़ नहीं सकता. Pointer pattern same दिखता है, लेकिन correctness proof अलग है.

INTERVIEW में बोलो · तुम्हारा ANSWER

“Sorted array में left smallest पर और right largest पर रखूँगा. Sum target से छोटा है तो left++, बड़ा है तो right--. Sorting की वजह से discarded endpoint अब किसी valid pair में काम नहीं आएगा. हर pointer केवल अंदर बढ़ता है, इसलिए O(n) time और O(1) extra space.”

Read it once. फिर अपने words में बोल के देखो.

SPOT IT BEFORE YOU CODE IT

Pattern पहचानो.

Problem में ये दिखे	तब ये use करो	यहाँ नहीं
Sorted array, pair sum	Opposite-end two pointers	Unsorted input and original indices needed without extra handling
Triplets sum to zero	Sort + fix one + two pointers	Calling the whole algorithm O(n)
Max container area	Move shorter wall	Moving a pointer without an elimination argument

SAME LOGIC. YOUR LANGUAGE.

अब code लिखते हैं.

Two Sum II · LC 167

Returns 1-based indices, as required by the problem. O(n) time, O(1) space.

def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]
        if total < target:
            left += 1
        else:
            right -= 1
    return []

assert two_sum_sorted([1, 2, 4, 6, 8, 11], 10) == [2, 5]