RJO4's blog

Can Anyone solve it in O(n) time.
By RJO4, history, 2 years ago, In English

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.

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

Comments Comments (21)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

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

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

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

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

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        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.

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

    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$$$.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Bro, we are finding minimum value, why you take max

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Oh sorry, I didn't read the question properly.

        → Reply
»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

      @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.

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

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

      → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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$$$.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    That won't work because the array could have negative values

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

    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.

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    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.

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

      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

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

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

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

          Can you elaborate your approach sir that would be useful.

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

            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.

            :)

            → Reply