(C and Python)Modify the array to do it in O(n) time and O(1) space


  • 8
    K

    If there are queries after each insert operation, disjoint-set is able to answer each query in O(log(alpha(n))) time and O(max(element in the array)) space, but for this problem, only one query after all the insertion finished, the time complexity should be O(n) and O(1) space, some simple method is in need.

    Even though it is not a good idea to modify the value of the origin array, this is the only space that is available, which means it must be made used of. Then if it is possible to sort the element which is between 1...n, then just loop over the sorted array, the job is done.

    Comparison sort is O(n logn), it is too slow. So the bucket sort is the only way. As only the elements between 1...n are useful, each element w should be put into the w th position of the array. As it is possible there is some other element v in the w th position, take the v out before overwriting and then iteratively use the same logic on v and go on.

    def firstMissingPositive(self, A):
      n = len(A)
      for index in xrange(n):
        element = A[index]
        while True:
          if element <= 0 or element > n or element == A[element - 1]:
            break
          A[element - 1], element = element, A[element - 1]
      for index in xrange(n):
        if A[index] != index + 1:
          return index + 1
      return n + 1
    

    Time complexity: each element is looped 2 times and swapped 1 time, so the whole time compexity is O(n)

    Space: O(1) apparently


    A pure recursive C solution, which has the same time and space complexity.

    void rotate(int A[], int n, int start){
      if(start <= 0 || start > n){
        return;
      }
      if(A[start - 1] == start){
        return;
      }
      int nxt = A[start - 1];
      A[start - 1] = start;
      rotate(A, n, nxt);
    }
    
    int firstMissingPositive(int A[], int n) {
      int i;
      for(i = 0; i < n; ++i){
        rotate(A, n, A[i]);
      }
      for(i = 0; i < n; ++i){
        if(A[i] != i + 1){
          return i + 1;
        }
      }
      return n + 1;
    }
    

  • 0
    Y

    Here is my C++ solution passed the test:

    class Solution {
    public:
        int firstMissingPositive(int A[], int n) {
            // Counts the number of positive integers, and set negative ones to zero (maybe uncessary)
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (A[i] < 0)
                    A[i] = 0;
                count++;
            }
            
            // Empty list, 1 is missing
            if (count == 0) {
                return 1;
            }
            
            // Moves all positive numbers to the right place, for instance 1 at 0, 2 at 1, etc.
            for (int i = 0; i < n; i++) {
                // What the current number should be located
                int expectedIdx = A[i] - 1;
                // If it's not a good number, or it's too big, or it's in the right place, check the next one.
                if (A[i] == 0 || expectedIdx == i || expectedIdx >= n) {
                    continue;
                }
                
                // Takes the current number and leaves it empty
                int current = A[i];
                A[i] = 0;
                
                do {
                    // No need to move more numbers (cycle)
                    if (A[expectedIdx] == expectedIdx + 1) {
                        break;
                    }
                    
                    // Backup the previous number and puts in the current
                    int temp = A[expectedIdx];
                    A[expectedIdx] = current;
                    
                    // If the previous number being just taken out is not in the range
                    if (temp == 0 || temp - 1 >= n) {
                        break;
                    }
                    
                    // Otherwise continue the loop and finds a home for this valid number
                    expectedIdx = temp - 1;
                    current = temp;
                } while (true);
            }
            
            // Scans from begining and the first inconsistent one will be the solution
            int k;
            for (k = 1; k < 1 + n; k++) {
                if (A[k - 1] != k)
                    break;
            }
            
            return k;
        }
    };

  • 0
    F

    Time complexity: each element is looped 2 times and swapped 1 time, so the whole time compexity is O(n)

    really?


Log in to reply
 

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