LeetCode | Best Time to Buy and Sell Stock

Selamlar🖖🏼

Bu yazının konusu bir Leetcode sorusu olacak. Competitive Algorithm konusuna ayrıca bir önem ve özen göstermeye çalışıyorum. Ne kadar çok proje yapmış ya da ne kadar tecrübeli olsanız da, bu alan sürekli pratik istiyor. Ben de imkan buldukça her gün bir soru çözüp, kendimi olabildiğince diri ve antrenmanlı tutmaya çalışıyorum. Blogumda da çözdüğüm ve hoşuma giden güzel soruların çözüm yollarını ve kodunu açıklamaya çalışacağım.  

Bugünkü sorumuz Best Time to Buy and Sell Stock. Google‘ın mülakat sorularından ve kolay kategorisinde olduğu belirtilmiş.

Yavaştan soruya geçelim.

Soruyu Anlayalım🤔

Soruda bize, fiyat bilgilerinin bulunduğu bir integer array dizisi prices veriliyor ve bu dizinin indisi i günü (1. gün, 3.gün gibi…) prices[i] de o günün fiyatını belirtiyor . Sorunun bizden istediği, fiyatın en düşük olduğu günde alım yapıp, kârımızı maksimum yapabileceğimiz günde satış yapmak ve böylece ulaşılabilecek maksimum kâra ulaşmamız.

Örnek 1

Input  : prices = [7,1,5,3,6,4]
Output : 5

Aslında burada yapılan işlem 2.günde 1 birimden alış yapıp(indisin 1'den başladığını düşünüyoruz, sıfırıncı gün yok) 5.günde 6 birimden satıp, 6 - 1 = 5, 5 birimlik kâr elde etmek.

Örnek 2

Input  : prices = [2,8,3,1,12,5]
Output : 11

Burada da 4.gün alıp 5.gün satarsak eğer maks. 11 birimlik kâr elde ederiz.

Örnek 3

Input  : prices = [7,6,4,3,1]
Output : 0

Mesela burada da bir türlü kâra geçirecek bir pozisyon bulunmadığı için alım-satım yapılamıyor dolayısıyla sıfır döndürülüyor.

Soruya Girişelim🥊

Aslında yapmamız gereken şey temelde basit, alım yaptığın günün fiyatı, satış yaptığın günün fiyatından küçük olsun ki herhangi bir kârdan bahsedebilelim. Yani kontrol etmemiz gereken durumlardan ilki, kâr ediyor muyuz? Tamam, diyelim ki kâr ediyoruz. Fakat bize her kâr lazım değil, maksimum olanı gerekli.

Ve bu kontrolleri de, son güne kadar gerçekleştirmek. Ardından maksimum kârı bulup bunu döndürebiliriz.

Şimdi bu düşündüklerimizi pseudo-code olarak yazalım.

1. maxProfit ve localProfit integer değişkenleri oluşturulup sıfıra atanır.

2. buyDay ve sellDay integer değişkenleri 0 ve 1 olarak atanır.

3. sellDay, prices dizisinin uzunluğundan küçük olduğu sürece bir döngü başlatılır.

    4. Eğer prices[buyDay] < prices[sellDay] ise:
        5. localProfit değişkenine prices[sellDay] - prices[buyDay] atanır.

        6. maxProfit, localProfit ve maxProfit arasındaki maksimum değere atanır.

    7. Aksi takdirde, buyDay değişkenine sellDay değeri atanır.

    8.sellDay değişkeni bir artırılır.

9. Döngü tamamlandığında, maxProfit değişkeni döndürülür.

Şimdi buradaki mantığı açıklamaya çalışayım.

• İlk olarak maxProfit ve localProfit adında iki değişken oluşturup, bunlara sıfır atadım. maxProfit bizim asıl sonucumuz olacak, localProfit de kâr ihtimallerini tutan değişkenimiz olacak.
• Sonrasında buyDay ve sellDay adında 0 ve 1 atanmış iki değişkenimiz ile günler üzerinde gezineceğimiz pointer’larımızı tanımladık, yani bir nevi i ve j. sellDay‘i 1 olarak tanımladık çünkü satış günü hep bir sonraki gün olacak.
• Ardından prices dizisinin içinde bir while döngüsü başlatıyoruz. sellDay yani satış gününü temsil eden değişkenimiz son güne ulaşınca döngüyü tamamlamış oluyoruz.
• Döngüye girdiğimizde her iterasyonda prices[sellDay] - prices[buyDay] ile kâr ihtimalimiz var mı kontrol ediyoruz, eğer böyle bir durum varsa da bunu hesaplayıp localProfit‘e atıyoruz. Ardından elimizdeki maxProfit ile karşılaştırıyoruz, hangisi daha büyük? Büyük olanı maxProfit‘e tekrar atıyoruz.
• Eğer kâr ihtimalimiz yok ise buyDay‘i, sellDay‘in olduğu noktaya getiriyoruz. Çünkü kâr ihtimali yok ise oradan alış yapmamıza gerek yok, bu yüzden o değişkeni ileri çekmiş oluyoruz.
• Son olarak da artık sellday‘i bir ileri alıyoruz yeni bir iterasyona geçiş ve yeni kâr hesaplaması için.

Buraya kadar sorun yoksa asıl koda geçebiliriz.

Coding💻

public int maxProfit(int[] prices) {
    int maxProfit = 0;
    int localProfit = 0;

    int buyDay = 0;
    int sellDay = 1;

    while (sellDay < prices.length) {
        if (prices[buyDay] < prices[sellDay]) {
            localProfit = prices[sellDay] - prices[buyDay];
            maxProfit = Math.max(maxProfit, localProfit);
        }
        else 
            buyDay = sellDay;
        sellDay++;
    }
    return maxProfit;
}

Kodun Time Complexity’sine bakacak olursak da, burada bir while döngüsü kullanarak prices array’inin elemanlarını yani tüm input’u dolaştığımız için BigO notasyonumuzun O(n) olduğunu görürüz. Yani yapılan işlem sayısı input’un boyutu n ile doğru orantılıdır diyebiliriz.

Tabii ki bu problemin birden farklı ve daha efektif çözüm yolları olabilir, benim çözüm yolum bu şekildeydi ve bunu açıklayıcı bir şekilde anlatmak istedim.

Buraya kadar zaman ayırıp okuduğunuz için teşekkürler,

Happy Coding🎉