Two Pointer तकनीक

Two pointers दो दोस्तों के books की एक line के साथ एक-दूसरे की ओर चलने जैसा है, यह decide करने के लिए अपनी positions उपयोग करते हुए कि अगला कौन step ले।

In this page:

Two Pointer Idea
Pair Sum
Remove Duplicates
Partitioning
Two Pointer Practice

Syntax

markup

left, right = 0, len(arr) - 1
while left < right:
    if condition(arr[left], arr[right]):
        return result
    elif need_larger:
        left += 1
    else:
        right -= 1

Two Pointer Idea

Two-pointer technique दो index variables उपयोग करती है जो किसी array में चलते हैं, अक्सर opposite ends से या अलग speeds पर, एक brute-force approach को चाहिए nested loops के बजाय एक pass में problem solve करने के लिए।

उदाहरण: Two Pointer Idea

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int left = 0, right = 4;
    while (left < right) { // two indices moving through the array in one pass
        cout << arr[left] << "+" << arr[right] << " ";
        left++; right--;
    }
    cout << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int left = 0, right = 4;
        while (left < right) {
            System.out.print(arr[left] + "+" + arr[right] + " ");
            left++; right--;
        }
        System.out.println();
    }
}

arr = [1, 2, 3, 4, 5]
left, right = 0, 4
while left < right:  # two indices moving through the array in one pass
    print(f"{arr[left]}+{arr[right]}", end=" ")
    left += 1
    right -= 1
print()

#include <stdio.h>
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int left = 0, right = 4;
    while (left < right) {
        printf("%d+%d ", arr[left], arr[right]);
        left++; right--;
    }
    printf("\n");
    return 0;
}

Pair Sum

एक sorted array पर, एक pointer शुरुआत में और एक आखिर में रखना आपको O(n) में एक target value तक sum होने वाला एक pair ढूंढने देता है: अगर current sum बहुत छोटा है, left pointer को right move करें; अगर बहुत बड़ा है, right pointer को left move करें।

उदाहरण: Pair Sum

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = 5, target = 12;
    int left = 0, right = n - 1;
    while (left < right) {
        int s = arr[left] + arr[right];
        if (s == target) { cout << arr[left] << " + " << arr[right] << " = " << target << endl; break; }
        else if (s < target) left++;
        else right--;
    }
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 12, left = 0, right = arr.length - 1;
        while (left < right) {
            int s = arr[left] + arr[right];
            if (s == target) { System.out.println(arr[left] + " + " + arr[right] + " = " + target); break; }
            else if (s < target) left++;
            else right--;
        }
    }
}

arr = [1, 3, 5, 7, 9]
target = 12
left, right = 0, len(arr) - 1
while left < right:
    s = arr[left] + arr[right]
    if s == target:
        print(f"{arr[left]} + {arr[right]} = {target}")
        break
    elif s < target:
        left += 1
    else:
        right -= 1

#include <stdio.h>
int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = 5, target = 12, left = 0, right = n - 1;
    while (left < right) {
        int s = arr[left] + arr[right];
        if (s == target) { printf("%d + %d = %d\n", arr[left], arr[right], target); break; }
        else if (s < target) left++;
        else right--;
    }
    return 0;
}

Remove Duplicates

एक sorted array से जगह पर duplicates हटाने के लिए, एक pointer अब तक लिखी आखिरी unique value track करता है जबकि एक दूसरा pointer अगली distinct value ढूंढने के लिए आगे scan करता है, सभी unique elements को front में compact करते हुए।

उदाहरण: Remove Duplicates

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1, 1, 2, 2, 3, 4, 4};
    int n = 7;
    int slow = 0;
    for (int fast = 1; fast < n; fast++) {
        if (arr[fast] != arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }
    cout << "Unique count: " << slow + 1 << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 2, 3, 4, 4};
        int slow = 0;
        for (int fast = 1; fast < arr.length; fast++) {
            if (arr[fast] != arr[slow]) {
                slow++;
                arr[slow] = arr[fast];
            }
        }
        System.out.println("Unique count: " + (slow + 1));
    }
}

arr = [1, 1, 2, 2, 3, 4, 4]
slow = 0
for fast in range(1, len(arr)):
    if arr[fast] != arr[slow]:
        slow += 1
        arr[slow] = arr[fast]
print("Unique count:", slow + 1)

#include <stdio.h>
int main() {
    int arr[] = {1, 1, 2, 2, 3, 4, 4};
    int n = 7, slow = 0;
    for (int fast = 1; fast < n; fast++) {
        if (arr[fast] != arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }
    printf("Unique count: %d\n", slow + 1);
    return 0;
}

Partitioning

Partitioning के लिए, एक pointer track करता है कि अगला wanted element कहां जाना चाहिए जबकि दूसरा array scan करता है, elements swap करते हुए ताकि किसी condition को satisfy करने वाली values एक side पर group हो जाएं, quicksort के partition के एक step जैसा।

उदाहरण: Partitioning

#include <iostream>
using namespace std;
int main() {
    int arr[] = {5, 2, 8, 1, 9, 3};
    int n = 6, pivot = 5;
    int wanted = 0; // where the next 'less than pivot' element should go
    for (int i = 0; i < n; i++) {
        if (arr[i] < pivot) {
            swap(arr[i], arr[wanted]);
            wanted++;
        }
    }
    cout << "First element >= pivot at index: " << wanted << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9, 3};
        int pivot = 5, wanted = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < pivot) {
                int tmp = arr[i]; arr[i] = arr[wanted]; arr[wanted] = tmp;
                wanted++;
            }
        }
        System.out.println("First element >= pivot at index: " + wanted);
    }
}

arr = [5, 2, 8, 1, 9, 3]
pivot = 5
wanted = 0  # where the next 'less than pivot' element should go
for i in range(len(arr)):
    if arr[i] < pivot:
        arr[i], arr[wanted] = arr[wanted], arr[i]
        wanted += 1
print("First element >= pivot at index:", wanted)

#include <stdio.h>
int main() {
    int arr[] = {5, 2, 8, 1, 9, 3};
    int n = 6, pivot = 5, wanted = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] < pivot) {
            int tmp = arr[i]; arr[i] = arr[wanted]; arr[wanted] = tmp;
            wanted++;
        }
    }
    printf("First element >= pivot at index: %d\n", wanted);
    return 0;
}

Two Pointer Practice

Two pointers विशेष रूप से तब अच्छी तरह काम करते हैं जब array sorted हो या जब आप दोनों ends से अंदर की ओर scan कर रहे हों, जो एक O(n²) brute-force search को एक O(n) linear-time solution में बदल देता है।

उदाहरण: Two Pointer Practice

#include <iostream>
using namespace std;
int main() {
    // Sorted array: two pointers turn an O(n^2) brute-force pair search into O(n).
    int arr[] = {2, 4, 6, 8, 10};
    int target = 14, left = 0, right = 4;
    while (left < right) {
        int s = arr[left] + arr[right];
        if (s == target) { cout << "Found: " << arr[left] << "," << arr[right] << endl; break; }
        s < target ? left++ : right--;
    }
    return 0;
}

public class Main {
    public static void main(String[] args) {
        // Sorted array: two pointers turn O(n^2) brute-force into O(n).
        int[] arr = {2, 4, 6, 8, 10};
        int target = 14, left = 0, right = 4;
        while (left < right) {
            int s = arr[left] + arr[right];
            if (s == target) { System.out.println("Found: " + arr[left] + "," + arr[right]); break; }
            if (s < target) left++; else right--;
        }
    }
}

# Sorted array: two pointers turn an O(n^2) brute-force search into O(n).
arr = [2, 4, 6, 8, 10]
target = 14
left, right = 0, 4
while left < right:
    s = arr[left] + arr[right]
    if s == target:
        print(f"Found: {arr[left]},{arr[right]}")
        break
    if s < target:
        left += 1
    else:
        right -= 1

#include <stdio.h>
int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int target = 14, left = 0, right = 4;
    while (left < right) {
        int s = arr[left] + arr[right];
        if (s == target) { printf("Found: %d,%d\n", arr[left], arr[right]); break; }
        if (s < target) left++; else right--;
    }
    return 0;
}

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Sliding Window Technique Next Lesson → Prefix Sum