Блог пользователя jankit366

Longest contiguous subarray with one substitution
Автор jankit366, история, 3 недели назад, По-английски

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?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          3 недели назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить