Two Pointers Technique

3 min readMar 6

LeetCode algoritma challange yaparken, ilk defa gördüğüm bir teknik.

GeeksForGeeks’in sitesinde çok açıklayıcı bir şekilde “sıralanmış arraylerde pair araması yapmak için kullanılan bir tekniktir.” diyor.

Yaklaşım çok basit. Elinizde bir array var. (Bu bir dataset olabilir, bir list olabilir.) Ve bu array’i baştan ve sondan dolaşmaya başlıyorsunuz, istediğiniz sonuca ulaşıyorsunuz.

NOT: Javada pointer kavramı yok. İşaretçi olarak bahsettiğim yapılar aslında yer işareti, indis tutan yerler olarak düşünülebilir.

Örn soru şu şekilde olsun.

Verilen dizide, verilen target değerini sağlayan 2 tane eleman var mı.?

Yani elimizde bir dizi var. Bir de target var. Bu dizinin elemanlarından eğer ikisinin toplamı target değerini veriyorsa, cevap “evet var” şeklinde olabilir.

int[] arr = int arr[] = { 10, 7, 3, 5, 8, 4, 6};
int target = 16;

Algoritma çok basit.

Diziyi baştan sona ve sondan başa dolaşacak 2 tane işaretçi seçiyoruz. Amaç, bu iki işaretçi elemanları dolaşacak.

Eğer herhangi iki elemanın toplamı target değerini sağlarsa 1, yoksa 0 döndürebiliriz.

Görüldüğü üzere, algoritmanın implementasyonu gerçekten kolay.

Önce arrayi sıraladık, ardından baştan ve sondan iki tane işaretçi belirledik. Birinci işaretçi baştan başlayıp sona doğru gitti, ikinci işaretçi sondan başlayıp başa doğru geldi.

While koşulu false verene kadar döngü devam etti.

Bu teknik gerçekten çok hızlı.

Soru şu şekilde,

Sıralanmış bir array’i, karelerini alıp döndüren methodu yazmaya çalışalım. Ama, her indisin karesi alındıktan sonra da dizinin sıralı olması beklenmekte olsun.

Yani;

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Soruyu 3 farklı şekilde çözüp aralarındaki farkları incelemeye çalışalım.

-> Çözüm 1

Akla ilk gelen yöntem, bruth force yaklaşımı olacaktır.

    public static int[] sortedSquares(int[] nums) {

        int[] arr = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            arr[i] = nums[i] * nums[i];
        }

        Arrays.sort(arr);
        return arr;

    }

Runtime’daki çalışma hızı 5 MS
Beats 50.33 %

-> Çözüm 2

Soruyu Stream API ile tek satırda çözebiliriz.

    public static int[] sortedSquaresWithStream(int[] nums) {

        return Arrays
                .stream(nums)
                .map(item -> item * item)
                .sorted()
                .toArray();

    }

Runtime’daki çalışma hızı 10 MS
Beats 14.26 %

-> Çözüm 3

Soruyu, Two Pointers Technique ile çözmeye çalışırsak,

    public int[] sortedSquaresWithTwoPointersTechnique(int[] nums) {

        int[] array = new int[nums.length];

        int i = 0;

        int j = nums.length-1;
        int k = nums.length-1;

        while(i<=j){

            int val1 = nums[i] * nums[i];
            int val2 = nums[j] * nums[j];

            if(val1 > val2){
                array[k] = val1;
                i++;
            }else{
                array[k] = val2;
                j--;
            }
            k--;
        }

        return array;

    }

Yaklaşım oldukça kolay.

Dolaşmaya elimizdeki dizinin sağından ve solundan başlıyoruz.

i ve j değerleri dizinin elemanlarının karesini tutarken, k değeri ise dizinin indislerinin tutmak için tanımlandı.

kodu çalıştırdığımızda

Runtime’daki çalışma hızı 1MS
Beats 100 %

Son olarak, bu teknik için aslında dizinin sıralanmış olması bası durumlar için elzem olmuyor.

Örn;

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]

Verilen k değerine göre diziyi rotate eden methodu Two Pointers Technique ile çözmeye çalışalım.

    public static void rotate(int[] nums, int k) {

        /**
         * Verilen k değeri dizimizin uzunluğundan büyükse
         * diye k değerini güncelliyoruz
         */
        k = k % nums.length;

        /**
         * k değeri aslında dizi için rotate edilecek nokta.
         * Bu yüzden rotate methoduna 2 kere k değeri gönderilir.
         * Birinci method, diziyi orta noktaya göre rotate eder.
         * İkinci method, 0 - k aralgını düzenler.
         * Üçüncü method, k - length aralığını düzenler.
         */
        rotate(nums,0,nums.length-1);

        rotate(nums,0,k-1);

        rotate(nums,k,nums.length-1);

    }

    private static void rotate(int[] nums, int low, int high){

        while(low<high){

            int temp = nums[low];
            nums[low] = nums[high];
            nums[high] = temp;
            low++;
            high--;

        }

    }