Hello Interview | Data Structures and Algorithms

Limited Time Offer:30% off Hello Interview Premium 🎉

30% off Hello Interview Premium 🎉

Main

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Practice

Learn

System Design

ML System Design

DSA

Behavioral

Salary Negotiation

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Discord

Refer a Friend

Pricing

Become a Coach

Pricing Become a Coach

Get Premium

Solution


def fruit_into_baskets(fruits):
  start = 0
  state = {}
  max_fruit = 0

  for end in range(len(fruits)):
    state[fruits[end]] = state.get(fruits[end], 0) + 1

    while len(state) > 2:
      state[fruits[start]] -= 1
      if state[fruits[start]] == 0:
        del state[fruits[start]]
      start += 1

    max_fruit = max(max_fruit, end - start + 1)

  return max_fruit

start

fruit into baskets

0 / 21

Explanation

We're going to walkthrough how the sliding window determines that the maximum number of fruits we can collect when fruits = [3, 3, 2, 1, 2, 1, 0]. We'll start with a general understanding of how the window slides through the input, and then we'll cover how to implement it.

The Sliding Window

The current window represents a subarray we are considering to contain the maximum number of fruits we can collect. It starts with the first fruit in the array, and expands and contracts according to two rules:

If the current window is valid - i.e. if it contains at most 2 distinct fruits - we expand the window to include the next fruit in the array.
If the current window is not valid, we contract the window by repeatedly removing the leftmost fruit in the window until it is valid again.

Here's what that looks like:

Each green subarray above is a valid sequence of fruit we can collect, and we return the longest of those sequences at the end. The sliding window is an efficient algorithm because we can move from one valid sequence to the next by incrementally building upon the previous one.

Initialization

A pointer start, initialized to 0, representing the starting index of the current window, which is currently empty.
A empty dictionary state, representing the state of the current window by mapping each fruit in the window to the number of times it appears.
A variable max_fruit, initialized to 0, representing the maximum amount of fruit we can collect.


def fruit_into_baskets(fruits):
  start = 0
  state = {}
  max_fruit = 0

  for end in range(len(fruits)):
    state[fruits[end]] = state.get(fruits[end], 0) + 1

    while len(state) > 2:
      state[fruits[start]] -= 1
      if state[fruits[start]] == 0:
        del state[fruits[start]]
      start += 1

    max_fruit = max(max_fruit, end - start + 1)

  return max_fruit

start

fruit into baskets

0 / 1

Iteration: Expanding the Window

Next, we enter the iteration phase of the algorithm where we repeatedly extend the current window to include the next element in the array. We do so by incrementing a pointer end that represents the end index of the current window in a for-loop.

The first step of each iteration is to add the fruit at end to state by incrementing its count in the dictionary. This updates the contents of the current window in O(1) time by incrementally building upon the previous window, rather than having to compute its contents entirely from scratch.

After expanding the current window, we then need to immediately check if our current window is still valid, which we can do in O(1) time by checking if state has 2 keys or less.

In this case, our window is still valid since it only contains 1 type of fruit, so we update max_fruit to be the length of the current window. The next iterations continue in the same fashion until reaching the first invalid window.


def fruit_into_baskets(fruits):
  start = 0
  state = {}
  max_fruit = 0

  for end in range(len(fruits)):
    state[fruits[end]] = state.get(fruits[end], 0) + 1

    while len(state) > 2:
      state[fruits[start]] -= 1
      if state[fruits[start]] == 0:
        del state[fruits[start]]
      start += 1

    max_fruit = max(max_fruit, end - start + 1)

  return max_fruit

start: 0 | end: -

initialize variables

0 / 7

Contracting the Window

At this point, our window is invalid for the first time because it contains 3 distinct fruits, so we need to contract the window until it is valid again.

We do so by first decrementing the count of the fruit at start in state. If the count of the fruit at start is 0, we need to delete that key from state to preserve the correctness of our valid condition. Finally, we increment start to contract the window.

Since we don't know how many times we need to contract the window, we do this all in a while loop.


def fruit_into_baskets(fruits):
  start = 0
  state = {}
  max_fruit = 0

  for end in range(len(fruits)):
    state[fruits[end]] = state.get(fruits[end], 0) + 1

    while len(state) > 2:
      state[fruits[start]] -= 1
      if state[fruits[start]] == 0:
        del state[fruits[start]]
      start += 1

    max_fruit = max(max_fruit, end - start + 1)

  return max_fruit

start: 0 | end: 3

expand window

0 / 2

Termination

Now, our window is ready to expand again, so we continue iterating until we reach the end of the array, at which point we return max_fruit.


def fruit_into_baskets(fruits):
  start = 0
  state = {}
  max_fruit = 0

  for end in range(len(fruits)):
    state[fruits[end]] = state.get(fruits[end], 0) + 1

    while len(state) > 2:
      state[fruits[start]] -= 1
      if state[fruits[start]] == 0:
        del state[fruits[start]]
      start += 1

    max_fruit = max(max_fruit, end - start + 1)

  return max_fruit

start: 2 | end: 3

no change to max_fruit

0 / 10

Complexity

The time complexity of this algorithm is O(n), where n is the length of the input array. end iterates through the array once, and start iterates through the array at most once. Each time either moves, they do O(1) work.
The space complexity of this algorithm is O(1), since we only use a constant amount of space to store the current window and its state (the dictionary never contains more than 3 keys).

Next: Overview

Your account is free and you can post anonymously if you choose.

Sort By

Solution

Explanation

The Sliding Window

Initialization

Iteration: Expanding the Window

Contracting the Window

Termination

Complexity

Questions

Learn

Links

Legal

Contact