Short Problem Definition:

Compute number of distinct values in an array.

Link

Distinct

Complexity:

expected worst-case time complexity is O(N * log(N));

expected worst-case space complexity is O(N)

Execution:

Sorting in both C++ and Python takes N log N time. We know that for this particular problem sorting the array will be the dominant runtime complexity. This is the case for the second python solution. What about the other ones?

The first solution is a neat pythonic way of solving a distinct entries problem. The set is implemented as a hash table so it is possible that it will degrade to a linked list. Therefore the actual worst case would be N^2.

This is not the case with C++ (as code 3 shows). The std set is a Red-Black Tree and therefore has insertion complexity of log N. (overall N log N)

Solution:

def solution(A):
    return len(set(A))

---

def solution(A):
    if len(A) == 0:
        return 0

    A.sort()

    nr_values = 1
    last_value = A[0]

    for idx in xrange(1, len(A)):
        if A[idx] != last_value:
            nr_values += 1
            last_value = A[idx]

    return nr_values

---

#include <set>
int solution(const vector<int> &A) {
    std::set<int> theSet;

    for(int idx = 0; idx < A.size(); idx++){
        theSet.insert(A[idx]);
    }

    return theSet.size();
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Short Problem Definition:

Minimize the value |(A[0] + … + A[P-1]) – (A[P] + … + A[N-1])|.

Link

TapeEquilibrium

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

Execution:

In the first run I compute the left part up to the point i and the overall sum last. Then I compute the minimal difference between 0..i and i+1..n.

Solution:

import sys

def solution(A):
    #1st pass
    parts = [0] * len(A)
    parts[0] = A[0]
 
    for idx in xrange(1, len(A)):
        parts[idx] = A[idx] + parts[idx-1]
 
    #2nd pass
    solution = sys.maxint
    for idx in xrange(0, len(parts)-1):
        solution = min(solution,abs(parts[-1] - 2 * parts[idx]));  
 
    return solution

---

#include <algorithm>
#include <climits>

int solution(vector<int> &A) {
    unsigned int size = A.size();

    vector<long long> parts;
    parts.reserve(size+1);

    long long last = 0;

    for (unsigned int i=0; i<size-1; i++){
        if (i == 0){
            parts.push_back(A[i]);
        } else {
            parts.push_back(A[i]+parts[i-1]);
        }
        if (i==size-2){
            last = parts[i]+ A[i+1];
        }
    }

    long long solution = LLONG_MAX;

    for(unsigned int i=0; i<parts.size(); i++){
        solution = min(solution,abs(last - 2 * parts[i]));
    }

    return solution;
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Short Problem Definition:

Check whether array N is a permutation.

Link

PermCheck

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

Execution:

Mark elements as seen in a boolean array. Elements seen twice or out of bounds of the size indicate that the list is no permutation. The check if the boolean array only contains true elements is not required. This solution only works with permutations starting from 1.

Solution:

def solution(A):
    seen = [False] * len(A)

    for value in A:
        if 0 <= value > len(A):
            return 0
        if seen[value-1] == True:
            return 0
        seen[value-1] = True

    return 1

---

int solution(vector<int> &A) {
    // the use of a auto_ptr would be better, but it does not work with arrays
    // use of boost::scoped_array seems like an overkill
    bool * seen = new bool[A.size()];
    
    for (unsigned int i=0; i< A.size(); i++){
        seen[i] = false;
    }    
    
    for (unsigned int i=0; i< A.size(); i++){
        if (!(0 < A[i] && A[i] <=A.size() && seen[A[i]-1] == false)){
            delete[] seen;
            return 0;
        } else {
            seen[A[i]-1] = true;
        }
    }
    
    delete[] seen;
    return 1;
}

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.