#include <iostream>
#include <stdio.h>
#include <vector>
#include <stdlib.h>

using namespace std;

class Solution {
public:
    void swap(int &x, int &y){
        int temp = x;
        x = y;
        y = temp;
    }

    int findIdx(vector<int>& nums, int root, int idx){

    int i = -1, j = nums.size();

        while (true){

        do{
            ++i;
        }while(nums[i] < root);

        do{
            --j;
        }while(nums[j] > root);

        if (i < j){
            swap(nums[i], nums[j]);
        }else return j;
    }

        return 0;
    }

    int findKthLargest(vector<int>& nums, int k) {
    cout << "******";
        for (int i = 0; i< nums.size(); i++)
        cout << nums[i] << "\n";
    cout << "******\n";
    if (nums.size() == 1){
        cout << nums[0] << "\n";
        return nums[0];
    }

        int idx = rand() % nums.size();
        int root = nums[idx];
        cout << root << " At " << idx << "\n";
        int new_idx = findIdx(nums, root, idx);
        //int new_idx = nums.size() - idx;
        cout << root << " At " << idx << " " << new_idx << "\n";

        if (k-1 < new_idx){
            vector<int> temp (nums.begin(), nums.begin() + new_idx + 1);
            return findKthLargest(temp, k);
        }
        else if (k-1 > new_idx) {
            vector<int> temp (nums.begin() + new_idx + 1, nums.end());
            return findKthLargest(temp, k - new_idx - 1);
        } else {
            return nums[new_idx];
        }
    }
};

int main(){
    Solution *sol = new Solution;
    int num[] = {99, 99};
    vector<int> nums(num, num + sizeof(num)/sizeof(int));
    std::cout << sol->findKthLargest(nums, 1);
}