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­čÄë