Algoritma Analizi - O (n) Linear - Diziyi Sağdan ve Soldan Başlayarak Dolaşma Two Pointers Technique

Giriş

Örnek

Soru şöyle

Problem Statement : Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.alo

Input: arr = [1, 2, 3, 4, 6], target=6

Output: [1, 3]

Explanation: The numbers at indices 1 and 3 add up to 6: 2+4=6

Açıklaması şöyle. Burada dizinin sıralı olması önemli

We will start with one pointer pointing to the beginning of the array and another pointing at the end. At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do, we have found our pair; otherwise, we will do one of two things:

1. If the sum of the two numbers pointed by the two pointers is greater than the target sum, this means that we need a pair with a smaller sum. So, to try more pairs, we can decrement the end-pointer.

2. If the sum of the two numbers pointed by the two pointers is smaller than the target sum, this means that we need a pair with a larger sum. So, to try more pairs, we can increment the start-pointer.

Bir diğer çözüm şöyle. Burada array üzerinde dolaşılıyor ve array sıralı olmak zorunda değil

Instead of using a two-pointer, we can utilize a HashTable to search for the required pair. We can iterate through the array one number at a time. Let’s say during our iteration we are at number ‘X’, so we need to find ‘Y’ such that “X + Y = Target”. We will do two things here:

1. Search for ‘Y’ (which is equivalent to “Target - X”) in the HashTable. If it is there, we have found the required pair.

2. Otherwise, insert “X” in the HashTable, so that we can search it for the later numbers.

Örnek

Soru şöyle. Burada ilk cevap 10 ve 14 arasındaki direklerin kaldırılması. İkinci cevap ise 16 ve 18 arasındaki direklerin kaldırılması

Given an integer array which represents the heights of adjacent vertical bars standing on the ground.

The width of each bar is 1. Now you have to pick two bars and remove the bars between them such that when rain falls the water collected between two bars is maximum. Note that the distance between bars remains the same after removing the remaining bars.

eg:
1. [10,5,6,12,14] ans: 30 (10*3)
2. [3 16 10 5 6 12 20 18] ans: 80 (16*(number of integers between 16 and 18)).

Çözüm şöyle

result := 0
left := 0
right := n - 1
while(left < right):
    result := max(result, (right - left - 1) * min(arr[left], arr[right]))
    if(arr[left] <= arr[right]):
        left := left + 1
    else:
        right := right - 1
    endif
end

Burada arr[left] <= arr [right] ise daha yüksek bir dirsek bulmak için solda indeks bir ilerletilir. Eğer sağ taraf kısa ise sağ taraf ilerletilir.