rumman_sust's blog

12697 — Minimal Subarray Length
By rumman_sust, 11 years ago, In English

I am trying to solve this problem so many times but I can't figure out how to solve this within 2.00 second(Time limit). I really need help cause I am being frustrated about this problem.

Problem summary : Given an array find the smallest sub-array whose summation is greater or equal than X and output the length of the smallest sub-array.

1 <= Array size <= 500000, -10^9 <= A[i] <= 10^9 and -10^9 <= X <= 10^9.

Can any one give me some hints about how to solve this type of problem less than O(n^2) complexity and within 2.00 second(Time limit).

problem link

Thanks in advance. :)

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

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

we build the array S with S[i] = sum(A[1], A[2], .. A[i]) then we have S[i] — S[j] = sum(A[j + 1], .., A[i])

then with each S[i], we find the maximum number j such as S[i] — S[j] >= x (j must be maximal so that the sequence length can be minimal)

S[i] — S[j] >= x <-> S[i] — x >= S[j]

here we have the left side can be calculated in O(1), the rest is to find j, O(n ^ 2) is the most simple way but it'd get TLE so u must use some data-structure like fenwick tree, segment tree, etc to do the job :p

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

    "then with each S[i], we find the maximum number j such as S[i] — S[j] >= x (j must be maximal so that the sequence length can be minimal)"

    I guess since A[i] can be negative this step is wrong.

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

      You just need to find some j such that S[j] <= S[i] — X.

      One way of doing this is using a segment tree (where each node keeps the minimum value of the interval), initially with all nodes equal to INF, and when you are at position i: if value at root is bigger than S[i] — X, then you know that there's no segment (j + 1)..i whose sum is >= X. otherwise you go to the rightmost node where the value of the node is <= S[i] — X, and there you find j.

      After processing which position i, you update that position in the segment tree.

      If you want, you can check my solution: http://pastebin.com/95uZG0se

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

        How this solution can be passed??? Try This input; 1 3 4 1 2 1

        output should be 3 but your code is giving -1

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

          Apparently the testcases were weak and didn't test some corner cases. To correct that bug just need to add the code below checking if ans == INF :

              int px = n - 1, tt = a[n];
    while(px >= 1 && tt < x)
      tt += a[px--];
    if(tt >= x)
      ans = min(ans, n - px);
          → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you all for your reply. :)

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

can anyone check what is wrong with this idea: I am getting WA. code Thanks.

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

    Check this test case.

    1

    10 15

    1 4 -1 -2 6 3 -8 14 -1 1 -1

    Answer should be 4 but your code shows 7.

    6+3+(-8)+14 = 15

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

Use a priority queue on accumulative sums. First let's build an accumulative array ACC where ACC[i] = ACC[i-1] + arr[i]. Now we want to know for each position i, what's the closest position to it's right j such that ACC[j] — ACC[i] >= X, this can be done with a priority queue.

For a hint on how to implement this you can check my AC solution here http://ideone.com/ELweLn

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

Simple implementation using java TreeMap

 int T = in.nextInt();
        while (T-- > 0) {
            int n = in.nextInt();
            long x = in.nextInt();
            long[] sum = new long[n];
            sum[0] = in.nextInt();
            for (int i = 1; i < n; i++)
                sum[i] = sum[i - 1] + (long) in.nextInt();
            int min = n + 3;
            TreeMap<Long, Integer> tm = new TreeMap<Long, Integer>();
            tm.put(0L, -1);
            for (int i = 0; i < n; i++) {
                long w = sum[i] - x;
                if (tm.floorKey(w) != null)
                    min = Math.min(min, i - tm.get(tm.floorKey(w)));
                while (!tm.isEmpty() && tm.lastKey() >= sum[i])
                    tm.remove(tm.lastKey());
                tm.put(sum[i], i);
            }
            if (min > n) out.println(-1);
            else out.println(min);}
→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    FierteDeCeylan, could you please explain what is the purpose of removing keys in the TreeMap greater than sum[i] as done by the above code. Ideally as 'put' method replaces previous value and floorKey returns maximum key <= sum[i], i couldn't make out the reason behind this. Other than that the code seems pretty awesome to me :)

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

    thanks man your code helped me in implementing the logic

    https://discuss.codechef.com/questions/119992/minsubar-editorial

    but this has a problem. when floorKey is null then we check for if sum[i] is our desired value.

    Consider
    5 9
    1 2 3 1 2

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

      Remember we artificially do tm.put(0L, -1); at the beginning. So this will take care of the case you are talking about. If the sum[i] is the desired value (sum[i] — x) = 0, and -1 will show up as the floorKey. Hence the answer would be current 0 based index -(-1), which is (index + 1).

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

I believe there is a simple and intuitive solution using binary search that solves in O(N lg N) time.

To answer to query "Does there exist a sub-array of length k which sums to at least X" takes O(N) time with accumulative/prefix sums.

Thus, we can binary search for the smallest value of k, which will take O(lg N) time.

This leads to a total complexity of O(N lg N).

EDIT: Oops.

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

    Are you sure that we can use binary search here? Because function is not monotonous.

    Array 

    -1 1 -1

    has subarray of size 1 with sum >=1, but none of it subarrays of size 2 or 3 have sum >=1.

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

    this is only true if the array elements are non-negative. but OP says  - 109 ≤ Ai ≤ 109 and  - 109 ≤ X ≤ 109.
    PS: I_love_Tanya_Romanova has provided a case which breaks your idea.

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

Problem is easy to solve in O(n) using modification of deque to find minimum element in it.

Code

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

    same problem but your code gives wrong answer. I have solved that problem differently using segment tree.

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

    adamant, I think your solution got AC because of weak tests on UVa, because your same code got WA on the same problem on codechef MINSUBAR

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

Can someone explain why I am getting WA for this solution My approach is dropping the previous sum if it is less than or equal to 0

→ Reply