jankit366's blog

Longest contiguous subarray with one substitution
By jankit366, history, 2 weeks ago, In English

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?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Any of those steps could be streamlined into $$$\mathcal{O}(n)$$$. Implementation (especially for step 4) is a pain in the a**, however.

      → Reply
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please tell me. How will you reduce TC for [4. Single Pass Substitution and check] to O(n) ?

        → Reply
        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply