Hey everyone! I'm diving into the Longest Increasing Subsequence (LIS) challenge from Leetcode, where we need to find the length of the longest strictly increasing subsequence in an array of integers. I think I've come up with an O(n) solution, but Leetcode points out that the optimal approach is O(n * log n). My code is passing various test cases, but I'm starting to wonder if there's something critical I'm overlooking. Here's the essence of the problem: Given an array like nums = [10,9,2,5,3,7,101,18], the expected output should be 4 since the longest increasing subsequence is [2,3,7,101].
Here's what my code does: it simply counts the length of the input array and decreases that count whenever there's an adjacent pair that isn't in increasing order. I feel like I hit a wall with this and I'd appreciate any insights on where I might be going wrong. Could this method actually fail with some edge cases? I'd love to know if anyone can clarify how the optimal O(n * log n) solution works! Thanks so much for any help! This is my first time posting, so I apologize for any formatting mistakes.
4 Answers
You altered the first example input to `10,9,2,8,1,7,101,18`, and there isn't an increasing subsequence of length 4 here. Check out different combinations where some elements can be decreasing. Your solution fails to account for cases with varying patterns—like if you had a sequence of many increasing but then decreasing numbers. It’s a good catch that shows your code passed some weak test cases!
It sounds like your approach is overlooking key structures in the sequence. For example, your code would give '3' for the array [3, 4, 1, 2], which actually should return '2' as the longest increasing subsequence is just [1, 2]. Your method counts elements linearly but doesn't consider the actual increasing subsequences where elements might skip around. You might want to test with more varied cases and see if your approach holds up in all situations!
Gotcha, thank you so much! If I may ask, what is my solution missing? Where did I mess up?
If your solution passed all hidden test cases, I'm curious about what your question is! If it missed some, you'd need to identify those edge cases that caused it to fail. There are always tricky scenarios in these problems, and having an efficient algorithm is key since it's not just about getting correct outputs in simple cases. Make sure you’re validating against a thorough range of inputs!
It sounds like you should report your findings to Leetcode. Your solution might be returning correct results due to weak test cases that don't cover all scenarios. Yours doesn't really hit the mark for complex patterns, like sequences that descend after a little win. For example, in a sequence like X, X+1, X-2, your method would give a significantly incorrect length. It’s impressive that you noticed that there might be flaws in both your solution and possibly the problem statement itself!
That makes sense, thank you so much! If I may ask, what is my solution missing? Where did I mess up?