O(N) solution without set or map?


  • 1
    R

    Does this problem have an O(N) solution without hash set or hash map? For, I think using hash set or hash map has wired aim of this problem. Why not using map-reduce? It is complexity is length of max sequence.

    I come up with a solution, its complexity is approximate O(n) (I have not proved.) based on following naive idea: If we can partition a big problem with equal two small problem, drop first and process the second. we get a O(n) solution, for (n + n/2 + n/(22) + n/(23) + ... ) ~ 2n.

    So, my solution is:

    1. input is {100, 1, 2, 101, 102, 3, 103, 2}

    2. its min value is 1, we use pivort = 1 + len(seq) = 1 + 8 = 9 to partition the sequence.

         we get {1, 2, 2, 3, 100, 101, 102, 103}

    3. the first part is easy to process if we use a vector {1, 2, 3, nan, nan, nan, nan, nan}

         to sample the sequence when partition.

    4. the second part is just small problem of origin.

    5. Take care, when we partition a long sequence in two half.

         I just partition again using pivort = 1 + (len(seq) + 1) / 2.


      So, My Code is following, considering strange test cases. It is not elegant and I cannot prove is O(N). It is just maybe, but very fast.

      int longestConsecutive(vector<int> &num) {
      if (num.size() <= 1) return num.size();

      vector<int> temp(num.size());

      int curMax = 0;
      int starts = 0, ends = num.size();

      //fast cut off
      while (starts < ends && curMax < ends - starts)
      {
      int curMin = *(min_element(num.begin() + starts,
      num.begin() + ends));
      int pivort = curMin + (ends - starts);

       //fill sample vector with invalid data -- pivort.
       for (int t = 0; t < ends - starts; t++) temp[t] = pivort;
      
       int i = starts, j = ends;
       while (i < j)
       {
           if (num[i] < pivort)
           {
               temp[num[i] - curMin] = num[i];
               i++; continue;
           }
           if (num[j - 1] >= pivort)
           {
               j--; continue;
           }
           swap(num[i], num[j - 1]);
           temp[num[i] - curMin] = num[i];
           i++; //no j--; to keep invality.
       }
       //here must i == j and [starts, i) has been sampled.
       
       //now we find curMax;
       int k = 0;
       int curPos = 0;
       do {
           while (k < ends - starts && temp[k] == pivort) k++;
           curPos = k;
           while (k < ends - starts && temp[k] != pivort) k++;
           if (curMax < k - curPos) curMax = k - curPos;
       } while (k < ends - starts);
      
       //here we should repartition, for our pivort
       //maybe cut off a sequence.
       if (temp[ends - starts - 1] != pivort)
       {
           //now we should repartition.
           i = starts; j = ends;
           pivort = curMin + (ends - starts + 1) / 2;
           while (i < j)
           {
               if (num[i] < pivort)
               {
                   i++; continue;
               }
               if (num[j - 1] >= pivort)
               {
                   j--; continue;
               }
               swap(num[i], num[j - 1]);
               i++;      //no j--; to keep invality.
           }
      
       }
       starts = i;
      

      }
      return curMax;
      }

    Some test cases are following:

        vector<int> vec = {100, 1, 101, 102, 2};
    EXPECT_EQ(longestConsecutive(vec), 3);
    vec = {100, 1, 101, 2, 102, 3};
    EXPECT_EQ(longestConsecutive(vec), 3);
    vec = {100, 1, 101, 2, 102, 3, 999, 4, 1000, 100, 1001, 101, 1003, 101, 1004, 3, 1002};
    EXPECT_EQ(longestConsecutive(vec), 6);
    vec = {5,-8,1,-7,-4,-1,3,7,5,6,-3,-9,-6,-6,7,4};
    EXPECT_EQ(longestConsecutive(vec), 5);

  • 1
    S

    Nice thought. However, its worst case complexity would be O(N2), since there could be as few as only one element on one side of the pivot after each partition process. Your test cases are all designed in such a way that pivot occurs somewhere in the middle. You may want to try the following sequence:

    1, 1002, 2002, 3001, 4000, 4999, ... (1000 numbers in the sequence). In this case, only the first element would be selected out in each partition.


  • 0
    R

    Yes, you are right. It is very bad, worse than "quick sort and check method". While, maybe we could find a O(n) method, name it as f(V) to check whether it is a bad sequence, here V is the given sequence. If f(V) has a not bad definition, then we get a algorithm having an average complexity better than O(nlogn).
    I don't like such rescue method, it must have not reveal truth of this problem. Hope somebody can come up with a better method.


  • 0
    R

    Hi, amazing idea compared to the hash map solution, can you prove that your algorithm has the recursive function like this:
    T(n) = T(n/2) + O(n)
    Then, if this is true the complexity is O(n). I think the hardest part is how to ensure equal partition.


  • 0
    V
    This post is deleted!

  • 0
    V
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    V

    Hi. Posting the link for my solution. No set or map, linked list. Should be O(n)
    https://oj.leetcode.com/discuss/12225/is-my-solution-o-n-time-space-with-linked-list


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.