Given an array { 1, 7, 7, 2,3, 7, 6,-20}. Find the longest nondecreasing contiguous sequence with substitution. we can substitute any array element with any integer such as all occurences of 7 replaced with 1. In this way new array would be { 1,1,1,2,3,1,6,-20}. Only one substitution is allowed.
What can be the optimal solution for this?
Can someone help me with the approach?
Approach- 1. Pre compute Longest Non-Decreasing Subsequence Without Substitution. 2. Store Element Positions. 3. Store Element Positions. 4. Single Pass Substitution and Check.
I think this should do the job — https://onecompiler.com/cpp/42qdrdbzd
Thanks!
I believe T.C. — Will be O(N^3) in your case which seems like a brute force. I was wondering if there is any better solution.
Any of those steps could be streamlined into $$$\mathcal{O}(n)$$$. Implementation (especially for step 4) is a pain in the a**, however.
Can you please tell me. How will you reduce TC for [4. Single Pass Substitution and check] to O(n) ?
I haven't tried, but the key idea is that a non-decreasing subarray (I'll call it NDS from here) can be merged with an adjacent subarray having one single element value. So each subarray only needs a check to its left and right.
Sometimes the merged subarray also links with the next NDS, but to merge that one as well, the previous NDS' end must not be higher than the next NDS' start (so that it keeps being monotonic).
Yes, a whole bunch of conditioning. I think someone could streamline this better than me, but at least I could say it's possible.