Arrays and Strings

6.1 Write a function that takes an array A and an index i into A, and rearranges the elements such that all elements less than A[i] appear first, followed by elements equal to A[iJ, followed by elements greater than A[i]. Your algorithm should have 0(1) space complexity and O(|A|) time complexity.

• My first attempt is to implement a simplified version of the problem where the pivot is assumed to be at the end of the array.

• The idea:

  • Have front and end pointers, where the partition is the absolute end of array

  • If the front is >= the pivot and the second pointer is less than the pivot, preform a swap, and move closer together.

  • otherwise, if the first pointer is smaller than the pivot, increment it and move on. The second pointer remains where it is.

  • If the first pointer is greater than the pivot, and the second pointer is also greater than the pivot, the second pointers value belongs where it should be, so we decrement the second pointer until it is smaller than the pivot

template<size_t size>
void partition(std::array<int, size> &ar) {
    // assuming pivot at end
    auto p = ar.end() - 1;
    auto i = ar.begin();
    auto j = ar.end() - 2;

    for (i; i != ar.end() - 1; i++) {
        if (i == j) goto FINISH;;
        if (*i >= *p && *j < *p) {
            iter_swap(i, j);
            continue;
        }
        else if (*i < *p) continue;
        else {
            // find something smaller
            while (*j >= *p) {
                j--;
                if (i == j) goto FINISH;
            }
            iter_swap(i, j);
        }
    }

    FINISH:
    iter_swap(i, p);
}

int main()
{
    std::array<int, 8> ar = { 7,2,1,8,6,3,5,4 };
    partition(ar);
    print_array(ar);

    std::array<int, 17> ar2 = { 7,2,1,8,6,3,5,4,2,1,2,1,1,1,2,2,1 };
    partition(ar2);
    print_array(ar2);

    std::array<int, 11> ar3 = { 7,2,1,8,6,3,5,4,9,2,5 };
    partition(ar3);
    print_array(ar3);
}

• To generalize this idea, I've simplify swaped the pivot index with the end, and then just prefromed the same alg.

template<size_t size>
void partition(std::array<int, size> &ar, int pivot_i) {
    // swap pivot index with element at end
    iter_swap(ar.begin() + pivot_i, ar.end() - 1);

    //...
}

Problem 6.6: Design and implement an algorithm that takes as input an array A of n elements, and returns the beginning and ending indices of a longest increasing sub-array of A.

• The idea here is to maintain a max that considers the length of the previous distance. When max gets updated, so the does returned pair.

• O(N) time, O(1) space

pair<int, int> largest_subarray(vector<int> &ar) {
    if (ar.empty()) return make_pair(INT_MIN, INT_MIN);

    int max = -1;
    pair<int, int> temp;
    pair<int, int> ret;
    for (int i = 1; i < ar.size(); i++) {
        if (ar.at(i - 1) <= ar.at(i)) {
            temp.first = i - 1;
            while (i < ar.size() && ar.at(i - 1) <= ar.at(i)) i++;
            temp.second = i - 1;
            if (temp.second - temp.first > max) {
                ret = temp;
                max = temp.second - temp.first;
            }
        }
    }
    return ret;
}


int main()
{
    //               0  1 2 3 4 5 6 7 8  9
    vector<int> v = {1,12,1,1,1,3,4,5,6,-1};
    pair<int, int> index = largest_subarray(v);
    cout << index.first << " " << index.second << endl;
    pause();

    //                  0 1 2 3 4 5   6   7   8    9    10    11     12
    vector<int> v2 = { -1,3,3,3,3,4,-10, 10,100,1000, 1001, 1991, 19299 };
    pair<int, int> index2 = largest_subarray(v2);
    cout << index2.first << " " << index2.second << endl;
    pause();
}

Problem 6.8: Let a be a sequence of length n whose elements are drawn from Z n = { 0, 1, 2, ... , n -1}. No element is repeated, which implies that each integer in Zn appears exactly once, i.e., a is a permutation. We read the elements of a one at a time, storing them in a set S, starting with the first element. We extract the minimum element from S after {i_o, i_1, i_2, ..., i_n} elements have been read.

Suppose you know the permutation a and the extract sequence {io, i1, ... , im-1) in advance. How would you efficiently compute the order in which the m elements are removed from S?

• My interpretation of the problem: extract every min from array after ith element as efficiently as possible.

• Idea: Maintain a min element while iterating through v. If the element becomes a min, push back the previous min into set S. Otherwise, push back into set S. My goal was to avoid using vector erase or insert, which takes take linear time in the middle of the array per operation.

• O(n) space, O(n) time

vector<int> extract_min(vector<int> &main, vector<int> &ith) {
    if (main.empty()) {
        throw std::invalid_argument("Vector was Empty");
    }
    vector<int> S;
    int min = main.at(0);
    int i;
    int back = 1;
    for (int j = 0; j < ith.size(); j++) {
        int cum_sum = std::accumulate(ith.begin(), ith.begin() + 1 + j, 0);
        for (i = back; i <  main.size() && i < cum_sum; i++) {
            if (main.at(i) < min) {
                S.push_back(min);
                min = main.at(i);
            }
            else S.push_back(main.at(i));
        }
        min = main.at(i);
        back = ++i;
    }
    return S;
}


int main() {
    vector<int> v = {3,-2,10,11,3,2,5};
    vector<int> i = {3, 2, 1};
    print(extract_min(v, i));

    vector<int> v2 = { 3,-2,10,11,3,2,5,19, 29,39,-19,19,2,3,103,192 };
    vector<int> i2 = { 3, 2, 1,2,3,1 };
    print(extract_min(v2, i2));
}