[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.
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.
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?
…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.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.