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

Can Anyone solve it in O(n) time.
Автор RJO4, история, 2 года назад, По-английски

Given an array of n elements and an integer K, the task is to find the subarray with minimum value of ||a[i] + a[i + 1] + ……. a[j]| – K|. Array may contain negative values. N<=1e5.

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

»
2 года назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

May solve it in $$$O(NlogN)$$$ time. Record all prefix sums in a sorted array. When scanning $$$j$$$, using binary search to find the max prefix sum $$$\leq \sum\limits_{t=1}^j a_t- K$$$ and min prefix sum $$$\geq \sum\limits_{t=1}^j a_t- K$$$. After a binary search, put $$$j$$$ into the sorted array.

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

    Your formula be wrong it should be +K instead of -K

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

      Fix j and scan i, how is it +K? My formula is correct.

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

        Your formula implies you are searching i for j on the right side i.e i <= j. Then for all possible subarray [j >= i] You deduct prefix[j] — prefix[i — 1] to get the actual subarray values and after that search in that array, we want to find two indexes for j, one is $$$j_{lowerBound}$$$ and another is $$$j_{upperBound}$$$, the definitions for lower bound and upper bound as per binary search,

        $$$prefix[j_{lowerBound}] - prefix[i - 1] <= K$$$, which is $$$prefix[j_{lowerBound}] <= K + prefix[i - 1]$$$

        $$$prefix[j_{upperBound}] - prefix[i - 1] > K$$$, which is

        $$$prefix[j_{upperBound}] > K + prefix[i - 1]$$$

        Overall we have, two indices for j that we can use

        $$$prefix[j_{lowerBound}] <= K + prefix[i - 1] < prefix[j_{upperBound}]$$$

        i.e. in a nutshell, loop over all i, find the best possible j on the right side of i, there can be 4 at max, then use them to optimize the answer.

        Note, there is another case where we have to flip the K when the subarray sums are negative, these is only for subarrays that are positive, for the negative we transform K into $$$prefix[i - 1] - K$$$. We have to handle negative subarrays and positive subarrays differently as there is also absolute inside the sub array.

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

    I think just finding the max and min prefix sums (ignoring the further condition you mentioned) would work (for a fixed $$$j$$$), lets say value of max prefix sum is $$$M$$$ and for min is $$$m$$$. Then, just calculate $$$max( |M-K| , |m-K| )$$$, and update the answer.

    This works because the optimal prefix sum must be either max or min for every $$$j$$$.

    → Ответить
»
2 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

From where you take this problem? I want to attack it give me link please.

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

    It's an Interview question! He also gave O(nlogn) solution per query but the interviewer insisited on optimising to O(n).

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

      @KartikArya, lol I wonder how much salary they offer, they ask these questions as if they are going to be crunching number day in day out and giving them thousands of dollars of salary. I bet they slack / gossip 80% of the time in their job. Those interviewers should be locked in jail that are torturing youngsters with hard questions that have no solution for.e.g no O(n) solution as someone mentioned.

      That's why I keep dreaming of the day when these interviewers are made jobless by Artificial Intelligence.

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

    Brother, cool down the violence, the problem did nothing wrong

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

      no, i am going to destroy any problem that tries to attack me, i utterly demolish anything that challenge me. :)

      → Ответить
»
2 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

For $$$O(n)$$$, you might use the sliding window trick. Maintain $$$2$$$ pointers: left pointer $$$l$$$ and right pointer $$$r$$$. If sum $$$\geq K$$$, $$$++l$$$, otherwise $$$++r$$$.

→ Ответить
»
2 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

UPD this reason does not work as it was pointed out by Ina in comments

It is not possible in $$$O(n)$$$. Proof by reduction from Element distinctness problem. Consider an instance of Element distinctness problem array b[1..n+1]. Construct array a[1..n] in a following way: a[1] = b[2] - b[1], a[2] = b[3] - b[2], a[3] = b[4] - b[3], ..., a[n] = b[n + 1] - b[n]. Notice that due to terms cancellation, pair of indices i <= j such that a[i] + ... + a[j] == 0 exist if and only if b[i] == b[j + 1].

Now consider a[1..n] as constructed before and K := |a[1]| + |a[2]| + ... + |a[n]| + 1. Then it is not hard to see that ||a[i] + ... + a[j]| - K| minimized when subarray sum is close to zero as possible. So by checking whether answer is K, we can answer yes/no to the instance b[1..n+1] of the Element distinctness problem.

Credit to Lewin's answer in this post

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

    This is intelligent, transforming a problem into another problem that has no better solution. Just like all NP-hard problems being compatible with each other.

    → Ответить
  • »
    »
    2 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    The element distinctness problem only applies for comparison sorts. Edit- Actually, this reduces to 2SUM and you can use a hash table to do this.

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

      Agree. Indeed Element Distinctness problem in case of integers could be easily solved by creating lookup table of size N and marking numbers we already met.

      Still finding closest to zero subarray sum would be useful for this problem

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

        Actually I kinda misread the problem, this reduces to 2SUM and you can use a hash table to do this.

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

          Can you elaborate your approach sir that would be useful.

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

            There is no normal computer algorithm for this problem as some red coder mentioned that if we solve this O(N) we also solve another problem in O(N) which has been proved impossible(hash is not O(1)).

            Since there are quantum algorithms for https://en.wikipedia.org/wiki/Element_distinctness_problem,

            may be there is a quantum computer algorithm as wikipedia says. So, its time for some quantum competitive programming my boi.

            Its time to make the leap from these boring for loops and play with superpositions in quantum space.

            :)

            → Ответить