[Solution]Problem 40: Length of the longest subarray where all its elements are distinct. (Google)

Arrays, Logics, Permutations, Greedy

Problem

This problem was asked by Google.

Given an array of elements, return the length of the longest subarray where all its elements are distinct.

For example, given the array[5, 1, 3, 5, 2, 3, 4, 1], return 5 as the longest subarray of distinct elements is [5, 2, 3, 4, 1].

[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:

Venmo: https://account.venmo.com/u/FNU-Devansh

Paypal: paypal.me/ISeeThings

Or you can sign up for a Free Trial Below. Thanks to the guaranteed refund policy, there is no risk to you -

Step 1: Brute Force

As with many array-based questions, the setup for this problem is relatively simple. No secret setups or transitions like we might have with graphs.

To tackle those pesky graph theory problems, check out a premium sub. z

There are possible O(n^2) subarrays. The brute force will iterate over each subarray (which go from 1 up to n in length). It would test every possible subarray for distinctness and keep track of the longest. This takes O(n^3) time and O(n) space.

Step 2: Optimizing

As we often cover in this newsletter, we can find the optimal solution by evaluating our brute force and removing the redundancy. This won’t work always (some questions require extra insight that makes the optimal soln very different from the brute force), but building from the brute force is a very high percentage play. Especially, when the brute force is straightforward, like here. So let’s attempt that first.

The step-by-step breakdown will allow you to score a lot of points in your interview. Take that instead of trying to be fancy and blitz things.

Clearly, we don’t need to go through every possible sub array to check for the distinct subarray. That is not useful. If we know that the maximum subarray has a length of k, then checking all subarrays of length <= k-1 is useless. We could slide a window of length k across the array till we come across distinct subarray. But we don’t have this k. So this sounds like a lovely next step.

Step 3: Mathematical Insight for Finding K

Before we proceed with discovering an algorithm for finding k and solving this problem, I want to share with you a very important mathematical insight. This insight is so profound that I will have to put a health advisory notification here: Make sure you’re wearing a tight helmet. Your brain will explode with how profound this is. Ready?

Make sure you have a high-quality helmet on. Photo by Vander Films on Unsplash

…Are you sure?

You’re a smart person. I can trust your judgment, right?

Imagine we have a number p. We know the following fact

p+1-1= p .

This holds true for all numbers. Pretty cool huh? Impressed by the brilliance of this newsletter?

Since the idea of adding a highlights section to this newsletter came from a premium sub named Rosi, we will call this Rosi’s rule. To have rules named after you, make sure you share your feedback with me as well. And give her a big thank you for her amazing contributions to making this newsletter even better.

To those of you that missed the solution, consider this a hint for solving the problem. Try again to make the solution work.

Don’t miss out on the benefits of getting a premium subscription. Think of all the potential income you’re losing.

Step 4: Finding K

Think back to how we would intuitively build up a solution for such a problem. We could start from the very beginning with a subarray of one. And if we encounter a new value, we add it to our subarray. This greedy approach automatically and quickly filters through the subarrays whose length is much lower than the solution.

The snag occurs when we hit a character that we have already seen. Let’s elaborate using the example given to us earlier. To remind you, we are given the array- [5, 1, 3, 5, 2, 3, 4, 1]

1. The first time we hit a snag is when we have the subarray [5,1,3,5]. Here the first character is the same as the last one we added. We can simply delete the first and keep the last occurrence. By Rosi’s Rule, we know the length will be unchanged. However, keeping the last occurrence will have the potential to grow further, so we want to keep it.

2. In the case [1,3, 5, 2, 3] the repeating character being added conflicts with a character in the middle. In such a case, we will have to drop all the nums preceding to the first occurence of our repeating num (and obviously the repeating num). That will turn our subarray [5,2,3] which we will continue with.

Clearly, we want to keep track of the maximum length we encounter. Now let’s code up the solution.

Step 5: Coding it up

Clearly, we care about discovering when a number shows up. So we want a data structure to track that. Since we will be constantly inserting new numbers into our DS, and checking if a num exists there, we should use a dictionary/hashmap.

We track the index of the last occurring elements as well as the running longest distinct subarray. Thus, when we look at the element at the next index, there are two cases for the longest distinct subarray ending at that index

def distinct_subarray(arr):
    d = {} # most recent occurrences of each element

    result = 0
    longest_distinct_subarray_start_index = 0
    for i, e in enumerate(arr):
        if e in d:
            # If d[e] appears in the middle of the current longest distinct subarray
            if d[e] >= longest_distinct_subarray_start_index:
                result = max(result, i - longest_distinct_subarray_start_index)
                longest_distinct_subarray_start_index = d[e] + 1
        d[e] = i

    return max(result, len(arr) - longest_distinct_subarray_start_index)

Notice something great about the approach of building things one at a time. In case of repeating nums, we are always guaranteed that one of the offenders is the num we encountered last. This simplifies our approach a lot.

Time Complexity- O(N)

Space Complexity- O(1)

Make sure you share your thoughts on this question/solution/any interesting questions/developments in the comments or through my links.

Happy Prep. I’ll see you at your dream job.

Go kill all you Topnotch Technician,

Devansh <3

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75