avatarGanesh Prasad

Free AI web copilot to create summaries, insights and extended knowledge, download it at here

3048

Abstract

article on a very similar problem: <a href="https://readmedium.com/52e36fd79b96"><b>Longest Substring with K Distinct Characters</b></a>, which does the same thing we want but uses K buckets. There we wanted the longest substring that can hold k different types of characters, and here we wanted the longest substring with K=2.</p><p id="70f3">Let’s see an example:</p><figure id="e9e1"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*AFnoy0Jqh6KBCDTS.png"><figcaption>Figure 1. Start with an empty window.</figcaption></figure><figure id="5b4b"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*iyXlKa3k5G9G7Pgr.png"><figcaption>Figure 2. Add the first character β€˜a’ to the window.</figcaption></figure><figure id="2b27"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*NRk7dfZjRtjvUykm.png"><figcaption>Figure 3. Add β€˜b’ to the window.</figcaption></figure><figure id="530d"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*Ql2VkE2MdPekXZGv.png"><figcaption>Figure 4. Add β€˜a’ to the window.</figcaption></figure><figure id="fcfa"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*dQiDxBxe3cm6aDri.png"><figcaption>Figure 5. Add b to the window.</figcaption></figure><figure id="a9f4"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*n1XDxzbfi7dDryBa.png"><figcaption>Figure 6. Add β€˜c’ to the window.</figcaption></figure><figure id="127c"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*dWfvnBMqKLyYHC4w.png"><figcaption>Figure 7. Shrink from the left side.</figcaption></figure><figure id="b906"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*Wj0G4JvgXtWz-lxo.png"><figcaption>Figure 8. Shrink from the left side.</figcaption></figure><figure id="6941"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*QxFRzSxBxIyGcNQC.png"><figcaption>Figure 9. Shrink from the left side</figcaption></figure><figure id="8e15"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*I17WM_ACZVPJjOwG.png"><figcaption>Figure 10. Add β€˜b’ to the window.</figcaption></figure><figure id="0e13"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*5Kp1idMBzy9TQF9u.png"><figcaption>Figure 11. Add β€˜c’ to the window</figcaption></figure><figure id="30ea"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*gCo3C5RB27waNwn7.png"><figcaption>Figure 12. Add β€˜c’ to the window.</figcaption></figure><figure id="b058"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/0*bdpHLO3mecwFhAWX.png"><figcaption>Figure 13. Add β€˜a’ to the window.</figcaption></figure><h2 id="bb04">So the algorithm for Maximum Fruits πŸ‰ into Baskets can be:</h2><ul><li>Create a hash table to store a mapping between characters and their frequency.</li><li>Insert new characters from the string until we have 2 distinct characters in the window. Remember the window size as the answer (longest we have seen so far).</li><li>Then start expanding the window from the right or, in other words s

Options

liding the window by adding new elements.</li><li>If at any time the number of distinct characters in the window reaches more than K, we will shrink the window from the right side and reduce the frequency of the character moving out until we have only K distinct characters.</li><li>Whenever the character frequency in the hash table reaches 0, we will remove the character.</li><li>After every expansion and shrinking, we will check if the current window has the largest size we have seen and if so, we will remember it.</li></ul><h1 id="bcb4">Code</h1><p id="41e1">I have written the python code and if you want the c++ code, <a href="https://ganeshpr227.medium.com/just-c-code-for-all-the-problems-i-have-practiced-58bfeeedd006#c231">read here</a>.</p> <figure id="7a35"> <div> <div>

            <iframe class="gist-iframe" src="/gist/PrasadGanesh/e47aace5761c0a2a8e1502bda597779d.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><h1 id="d42e">Time &amp; Space Complexity</h1><p id="4237"><b>Time</b>: The window adds each character once and removes them only once if it holds more than 2 types of characters at any time; hence the time complexity is linear, O(n), where n is the number of trees.</p><p id="3479"><b>Space</b>: We can see that at any time, we are not using more than 3 cells of our dictionary or hash table; hence the space complexity is constant, O(1).</p><p id="d72b">Thank you for reading!</p><p id="fb3a"><i>P.S.: If you like this uninterrupted reading experience on this beautiful platform of Medium.com, consider supporting the writers of this community by signing up for a membership <a href="https://ganeshpr227.medium.com/membership">HERE</a>. It only costs $5 per month and helps all the writers.</i></p><p id="1397"><i>If you liked what you just read, a clap would be highly appreciated. You can be generous in clapping; it shows me how much you enjoyed this story. And if you didn’t like it? Please do comment</i>πŸ˜‹<i>!</i></p><p id="a226">You can also follow me <a href="https://ganeshpr227.medium.com/">HERE</a> to get updates on the stories that I write.</p><div id="c731" class="link-block">
      <a href="https://ganeshpr227.medium.com/key-concepts-and-terms-of-system-design-interview-notes-9bf882cf3730">
        <div>
          <div>
            <h2>System Design β€” Key Concepts and Terms [Interview Notes] πŸ”₯</h2>
            <div><h3>This is a list of 20+ key terms and concepts in System Design, along with brief explanations for each.</h3></div>
            <div><p>ganeshpr227.medium.com</p></div>
          </div>
          <div>
            <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*ZIVC5DhwYoAY8qg_y3QNyQ.jpeg)"></div>
          </div>
        </div>
      </a>
    </div><p id="f0f0">This is a leetcode problem (904).</p></article></body>

Maximum Fruits πŸ‘πŸ’πŸ“πŸ₯­ Into Baskets 🧺| Coding Interview | Sliding Window Pattern

I heard from many sources that this problem is a notorious one, that many big companies ask this question, its different aspects or slightly modified versions. This article will discuss how this problem is a specific version of the more general problem that we have already discussed, Longest Substring with K Distinct Characters.

Maximum fruits into baskets

πŸ˜‚πŸ€© so many companies have asked this one question!

This problem is part of the 30 days preparation plan.

Description

We are at a farm with a row of trees 🌳🌲🌴 arranged from left to right. The trees are represented by different characters in an array of fruits and where fruits[i] is the type of fruit ith tree holds. We can only pick one fruit from a tree.

The goal is to collect as many fruits as possible but only two baskets. We can start from any tree but once started; we cannot skip a tree.

So we have to find the maximum number of fruits we can collect from the farm using just two baskets.

Example 1:
Input: fruits = [a, b, b, a, c]
Output: 4
Explanation: We will get fruits from the first 4 trees using 2 baskets.
Example 2:
Input: fruits = [a, b, c, e, f, f, g]
Output: 3
Explanation: Start picking fruits from 4th tree and do it till 6th.

Let’s see how we can solve this problem using a sliding window pattern, making it extremely 🐣 easy to solve.

Solution

I have written an article on a very similar problem: Longest Substring with K Distinct Characters, which does the same thing we want but uses K buckets. There we wanted the longest substring that can hold k different types of characters, and here we wanted the longest substring with K=2.

Let’s see an example:

Figure 1. Start with an empty window.
Figure 2. Add the first character β€˜a’ to the window.
Figure 3. Add β€˜b’ to the window.
Figure 4. Add β€˜a’ to the window.
Figure 5. Add b to the window.
Figure 6. Add β€˜c’ to the window.
Figure 7. Shrink from the left side.
Figure 8. Shrink from the left side.
Figure 9. Shrink from the left side
Figure 10. Add β€˜b’ to the window.
Figure 11. Add β€˜c’ to the window
Figure 12. Add β€˜c’ to the window.
Figure 13. Add β€˜a’ to the window.

So the algorithm for Maximum Fruits πŸ‰ into Baskets can be:

  • Create a hash table to store a mapping between characters and their frequency.
  • Insert new characters from the string until we have 2 distinct characters in the window. Remember the window size as the answer (longest we have seen so far).
  • Then start expanding the window from the right or, in other words sliding the window by adding new elements.
  • If at any time the number of distinct characters in the window reaches more than K, we will shrink the window from the right side and reduce the frequency of the character moving out until we have only K distinct characters.
  • Whenever the character frequency in the hash table reaches 0, we will remove the character.
  • After every expansion and shrinking, we will check if the current window has the largest size we have seen and if so, we will remember it.

Code

I have written the python code and if you want the c++ code, read here.

Time & Space Complexity

Time: The window adds each character once and removes them only once if it holds more than 2 types of characters at any time; hence the time complexity is linear, O(n), where n is the number of trees.

Space: We can see that at any time, we are not using more than 3 cells of our dictionary or hash table; hence the space complexity is constant, O(1).

Thank you for reading!

P.S.: If you like this uninterrupted reading experience on this beautiful platform of Medium.com, consider supporting the writers of this community by signing up for a membership HERE. It only costs $5 per month and helps all the writers.

If you liked what you just read, a clap would be highly appreciated. You can be generous in clapping; it shows me how much you enjoyed this story. And if you didn’t like it? Please do commentπŸ˜‹!

You can also follow me HERE to get updates on the stories that I write.

This is a leetcode problem (904).

Programming
Interview
Coding
Arrays
Software Development
Recommended from ReadMedium