jankit366's blog

Longest contiguous subarray with one substitution
By jankit366, history, 3 hours 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

»
37 minutes 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
  • »
    »
    26 minutes 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
    • »
      »
      »
      25 minutes ago, # ^ |
        Vote: I like it +1 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