This week, I’m going to talk about the longest increasing subarray problem. You can find more posts like this at Uber Interview Questions.
Also, this question is similar to Subarray With Given Sum. If you have read our previous post, I hope you can solve this problem easily.
In this post, I’m going to cover topics like “sliding window”, dynamic programming, time/space complexity and so on.
Longest Increasing Subarray
Given an array, return the length of the longest increasing subarray.
For example, if the input is [1, 3, 2, 3, 4, 8, 7, 9], the output should be 5 because the longest increasing array is [1, 2, 3, 4, 8].
This question has been asked by Uber, Facebook recently (as the time of writing this post). Another reason I’d like to discuss this problem is that many techniques used in this question can be re-used in other places.
It should be obvious that the most naive approach is to check all subarrays and return the longest increasing subarray. Although this approach doesn’t require extra memory, the time complexity would be O(n^2) where n is the length of the array.
This apparently is not what interviewers want, but it’s usually recommended to mention this approach briefly and also clarify that you know this is not optimal.
Let’s see how we can make it faster.
Think about this: if we want to make it faster than O(n^2), common scenarios are O(nlogn), O(n) and O(1). O(1) seems impossible because we should iterate over the array at least once. So O(n) would be the lower bound.
If we want to aim at O(nlogn), usually it means we should do something like sort, binary search, and so on. Since we don’t want to change the order of the array, sort is not useful. Binary search also seems irrelevant.
As a result, O(n) is our target.
If you try to solve this problem manually, you may realize that not all subarrays need to be checked. For example, suppose input is [1, 2, 3, 2, 4, 5, 6], you start with increasing subarray [1, 2, 3]. However, the next one (2) is smaller than the previous number. In fact, you can ignore everything before 2 and just check from the subarray [2, 4, 5, 6].
If you have read our previous post Longest Substring Without Repeating Characters, the sliding window approach should be quite obvious. In fact, it’s one of the most common techniques to process an array in linear time.
So we can have the following algorithm:
- We keep two pointers start and end to denote the subarray arr[start: end]
- If the current array is increasing, which means arr[end] > arr[end – 1], we can increase the current array by add 1 to end
- Otherwise, we can ignore everything before pointer end. So just set start = end
- In the end, just return the longest subarray
It’s worth to note that checking corner cases in the beginning is very necessary. Although the code is quite concise, it’s easy to make mistakes about boundaries.
Let’s change the question a little bit. Instead of getting the longest increasing subarray, how to return the length of longest increasing subsequence?
For subsequence, numbers are not necessarily contiguous. If the input is [1, 3, 2, 3, 4, 8, 7, 9], the output should be 5 because the longest increasing subsequence is [2, 3, 4, 8, 9].
I’d like leave this question as a homework. But here are some hints:
- Some people might want to do a brute force, however, you’ll soon notice that you won’t be able to list all possibilities. In this case, usually we should rely on a recursive solution.
- The key to the recursive solution is to come up with the recursion formula.
- Memorization can significantly improve the speed, though requires more memory.
- Check Subarray With Given Sum if you still can’t figure this out
Array questions are quite common in interviews as it doesn’t require any prior knowledge and it’s one of the best ways to test candidate’s basic coding skills.
I don’t think this question is hard to think, but writing bug-free code is not trivial, especially with a time constraint. I would say everyone should try to write down the solution even if you’ve already read this post.
By the way, if you want to have more guidance from experienced interviewers, you can check Gainlo that allows you to have mock interview with engineers from Google, Facebook etc..