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

Автор calmdown_69, история, 4 года назад, По-английски

Hello everyone.

Reference: here

problem statement:

An array is good if all subarrays have atleast 1 element in them whose frequency is 1.

Good : 1,2,1
Good: 1,2,5,2,4,3,4
Bad: 1,2,3,1,2,3

O(N^2) solution is easy but can anyone share a better approach for this question.
Thank you.

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

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

Wrong Approach ! Thanks @ScoobyDoobyDoo

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

By good subarray I mean that it contains at least one unique element. The whole array needs to be good, so it has to contain an unique element. Find this element, now each subarray containing it is good, so we can just recursively repeat our algorithm for the elements to the left and to the right. This is pretty easy to do in $$$O(n \log n)$$$ complexity.

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

    but won't be it quadratic if unique element is not in the middle like quick select worst case is O(n^2) if good pivot is not chosen

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -26 Проголосовать: не нравится

      I think that it would not be possible to get guranteed time complexity of NlogN. And also in that reference link there is clearly said that expected time complexity so may be this could referred to time complex.. of randomized algorithms. Still I didn't have think too much about it so it can possible to get guranteed lower bound of NlogN.
      So for time being this quick sort type solution would do better.

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

      Yes, but there is quite well known trick to search simultaneously from the left border and the right border, so we make O(smaller part) so it will sum up to $$$O(n \log n)$$$.

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

        Hi Anadi, We can maintain a min array and a right bound array (Lets say mn[n] , R[n]) While checking the ith index, we find its previous element with same value and next with same value (Lets say Prev[i] , Next[i] in O(nlog(n))) Then we update all elements in the range — [Prev[i], i] with max(R[j],Next[i] — 1) for each j in the range. In the min array we maintain the left most index with R[j] = i => mn[i] = j So, while checking the ith element, Prev[i] should be less than or equal to mn[i — 1] otherwise subarray — [mn[i — 1] , i] would not have any unique element. We can iteratively do the process in O(nlog(n)) time. I would love for you to check this approach.

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

          I am not sure, probably don’t understand your approach. I cannot see why your approach wouldn’t fail on some easy test like $$$2$$$, $$$3$$$, $$$2$$$, $$$3$$$.

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

      Not sure, but it seems a good implementation can guaranteed O(n logn) solution .

      If there exist multiple unique elements, select one which is closest to middle index.

      Otherwise, let suppose if there is only 1 unique element which is at leftmost index, then it is obvious that we get result just after one recursion as we can't find any unique element in next recursive call.

      In general we can guaranteed, that if such unique element is find at kth index, recursion depth will not exceed k. so if k < logn, then complexity is obviously O(nlogn).

      I know this seems quite abstract, but may be there is some mathematical proof of it.

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

        Here's a counterexample where the recursion depth is $$$n/2$$$:

        2 1 3 2 4 3 5 4 6 5 7 6 7

        After each step, there's a unique value at the second index.

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

      Expanding a little bit more on the following statement:

      Yes, but there is quite well known trick to search simultaneously from the left border and the right border, so we make O(smaller part) so it will sum up to $$$O(n \log n)$$$.

      Argument:

      You start looking for a unique element from both ends simultaneously: $$$1, n, 2, n - 1, 3, n - 2...$$$.

      Suppose you spot the unique element at position $$$i$$$. At this step you did $$$2 \cdot min(i, n - i)$$$ operations to check for each element if it is unique on this interval or not.

      Then you run the algorithm recursively to the left and to the right. Notice that: $$$ min(i, n - i) \leq min(|left|, |right|)$$$ so basically the cost of each step is proportional to the smallest resulting interval.

      Now to compute the complexity, suppose that every time you inspect an element you add a coin on it if it belongs to the minimal interval in that iteration. The number of check operations you will do in the end is proportional to the number of coins (in particular close to twice the number of coins).

      Each time a coin is added on top of an element, it means the interval where this element was located was merged with a bigger interval, then its size increased in at least twice. So the number of coins $$$k$$$ must satisfy that $$$2^k \leq n$$$, then $$$k \leq \log_2 n$$$. Then in total the number of coins is $$$O(n \cdot \log n)$$$ which is indeed the complexity of this algorithm.

      Notice that this analysis is pretty much the same as the technique of merging smaller to larger (usually on trees), just backwards.

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

        Suppose you spot the unique element at position i. At this step you did 2⋅min(i,n−i) operations to check for each element if it is unique on this interval or not.

        Can somebody explain this part? Till now what I have understood (maybe wrong) is we are searching from the left border and right border i.e checking first i elements and last i elements, but how can we check element at position i is unique in complete array if we have only traversed first i and last i elements.

        Can somebody please clear my doubt?

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

          You can for instance precompute for each element the indices of its previous and next identical elements. Then to check that an element is unique in a subrange, it suffices to check that the precomputed indices fall outside of that subrange.

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

        Not getting this!

        "So the number of coins k must satisfy that 2^k ≤ n, then k ≤ log2n."

        Shouldn't it be:

        every time a coin is added, we have atleast 1 mirror element in larger interval

        then k coins imply 2*k <= n, which is k <= n/2

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

          Your reasoning is not wrong, but doesn't provide a good upper bound. You can do better.

          Suppose an element has $$$k$$$ coins. It means it belonged $$$k$$$ times to the smallest side. The last time you added a coin to it the length of the interval containing it was $$$a_k$$$ and the length of the other side was $$$b_k \geq a_k$$$, but then it implies that in the previous step all $$$a_k + b_k$$$ elements were in one side, so when we add the previous coin the size of the interval was $$$a_{k -1} \geq a_k + b_k \geq 2\cdot a_k$$$. So we know the size of the intervals when we add a coin as we move backwards at least increased twice. This argument is enough to proof that the maximum number of coins added to an element is $$$O(\log_2 n)$$$

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

What's the constraint on Array elements? I mean what is the range of A[i]?

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

    Whatever they may be but we can use coordinate compression and bring them in the range [1, n].

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

      No that's not my point. I mean suppose N is in order of 10^5 and A[I] is in the range [1,100], then we can get some idea about how many elements are repeated and all.

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

might be useful: cs stackexchange answer
similar to one of the mentioned solutions.

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

Create an array of next occurrence of each element then using segment tree descent we can find first unique element in l-r in logn. Now recurrence will be T(n)=T(n-1)+O(logn) which will be O(nlogn)

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

Can there be any O(N) solutions?

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

    Checking for the existence of a unique element itself would probably take $$$O(n \log n)$$$, or at least $$$\omega(n)$$$ time (deterministically), so if you want to avoid randomized solutions (including hash tables), the answer is probably no.

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

      Yeah I'm having a problem similar to this, I tried the O(NlogN) way but it turns out to be TLE

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

        link to question
        Very well explained editorial

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

        You might be finding the frequency each time (for checking if an element is unique), which would give TLE, since you do $$$O(n)$$$ work instead of $$$O(\min(i, n - i))$$$ work. As pointed out in one of the above comments, you'll need to maintain the indices of the previous equal element and the next equal element.

        It might also be the case that you're not performing constant factor optimizations (or inadvertently doing too many unnecessary memory accesses — for instance, while using map).

        Code