tskrgulja1
BAN USERthis is not O(n), it is O(nlogn). At each level you do for loop. There are logn levels, and at each level, you have k loops that are n/k in size. Similar to merge sort.
 tskrgulja1 March 21, 2019This is my O(n) time solution. It is recursive so uses O(logn) stack space.
It first computed tree height etc. and then does inorder recursion till it reaches tree height, creating nodes in order (smallest value node first and so on).
Other solutions that I see here, that use recursion by first creating root node (using slow and fast pointers), are O(nlogn) time.
//binary tree node
struct BTNode{
int value;
BTNode* left = nullptr;
BTNode* right = nullptr;
};
//linked list node
struct LLNode{
int value;
LLNode* next = nullptr;
};
//recursive function
BTNode* sortedLinkedListToCompleteBinaryTree(LLNode** current_llnode, int depth, int* current_height, int num_extra_leaves, int* num_extra_leaves_visited){
//recurse left if we are not at the leaf node
BTNode* left_child = nullptr;
if(depth < *current_height){
left_child = sortedLinkedListToCompleteBinaryTree(current_llnode, depth + 1, current_height, num_extra_leaves, num_extra_leaves_visited);
}
//create tree node with value of the current linked list node and progress current linked list node
BTNode *node = new BTNode();
node>left = left_child;
node>value = (*current_llnode)>value;
*current_llnode = (*current_llnode)>next;
//check if we filled in all the extra leaf nodes
if(*num_extra_leaves_visited < num_extra_leaves){
if(depth == *current_height){
++(*num_extra_leaves_visited);
//if we right now filled all the extra leaves we now have to fill rest of the tree that is one less in height
if(*num_extra_leaves_visited == num_extra_leaves){
(*current_height);
}
}
}
//recurse right if we are not at the leaf node
if(depth < *current_height){
node>right = sortedLinkedListToCompleteBinaryTree(current_llnode, depth + 1, current_height, num_extra_leaves, num_extra_leaves_visited);
}
return node;
}
BTNode* sortedLinkedListToCompleteBinaryTree(LLNode* head){
LLNode* tail = head;
//get total number of nodes
int num_nodes = 1;
while(tail>next != nullptr){
tail = tail>next;
++num_nodes;
}
//get number of digits in binary to get size of perfect tree (greatest power of 21 <= total nodes)
int num_binary_digits = 0;
int num_nodes_copy = num_nodes;
do{
num_nodes_copy >>= 1;
++num_binary_digits;
}while(num_nodes_copy != 0);
int num_nodes_perfect = (1<<num_binary_digits)1;
//num digits in binary equals to tree height for perfect tree
int num_digits_perfect = num_binary_digits;
if(num_nodes_perfect > num_nodes){
num_nodes_perfect >>= 1;
num_digits_perfect;
}
int perfect_height = num_digits_perfect;
//number of extra leaves in bottom level (that make tree not perfect)
int num_extra_leaves = num_nodes  num_nodes_perfect;
//height of the whole tree
int max_height = perfect_height;
if(num_extra_leaves > 0){
++max_height;
}
//this variable tracks current maximum depth to which we recurse (should get decreased by 1 when we fill all the extra leaves)
int current_height = max_height;
int num_extra_leaves_visited = 0;
//we do inorder recursion (because our linked list it ordered) and track current linked list node
LLNode* current_llnode = head;
BTNode* root = sortedLinkedListToCompleteBinaryTree(¤t_llnode, 1, ¤t_height, num_extra_leaves, &num_extra_leaves_visited);
return root;
}

tskrgulja1
March 21, 2019 Recursion with memoization.
O(N^2) time, O(N^2) space complexity (N is number of cuts)
#include <vector>
#include <limits.h>
int minPriceWoodCutting(int wood_start, int wood_end, const std::vector<int>& cuts, int cuts_start, int cuts_end, std::vector<std::vector<int>>& memo){
if(cuts_start > cuts_end  wood_end == wood_start){
return 0;
}
if(memo[cuts_start][cuts_end] != 1){
return memo[cuts_start][cuts_end];
}
int wood_length = wood_end  wood_start;
int min_price = INT_MAX;
for(int i = cuts_start;i<=cuts_end;++i){
int price_left = minPriceWoodCutting(wood_start, cuts[i], cuts, cuts_start, i  1, memo);
int price_right = minPriceWoodCutting(cuts[i], wood_end, cuts, i + 1, cuts_end, memo);
if(price_left + price_right < min_price){
min_price = price_left + price_right;
}
}
int total_price = wood_length + min_price;
memo[cuts_start][cuts_end] = total_price;
return total_price;
}
int minPriceWoodCutting(int length, const std::vector<int>& cuts){
std::vector<std::vector<int>> memo;
memo.resize(cuts.size());
for(int i=0;i<cuts.size();++i){
memo[i].resize(cuts.size(), 1);
}
return minPriceWoodCutting(0, length, cuts, 0, cuts.size()1, memo);
}
int main()
{
std::vector<int> cuts = {2,4,7};
int length = 10;
int min_price = minPriceWoodCutting(length, cuts);
std::cout<<"Min price: "<<min_price<<std::endl;
return 0;
}

tskrgulja1
March 19, 2019 This is my O(n^2), O(1) space solution.
Iterates over all possible intervals, and increases number of subsets by 1 (if valid).
If new number is reached (if we are furthest we have ever been), we multiple number of subsets by 2 because we now have subsets + subsets combined with new number.
Union of 2 valid subsets is a valid subset.
int countSubsets(vector<int> numbers, int k) {
int num_valid_subsets = 0;
int max_interval_ending = 0;
for (int i = 0; i < numbers.size(); ++i) {
int max = numbers[i];
int min = numbers[i];
for (int j = i; j < numbers.size(); ++j) {
if (numbers[j] > max) {
max = numbers[j];
}
if (numbers[j] < min) {
min = numbers[j];
}
if (max + min <= k) {
if(j > max_interval_ending) {
max_interval_ending = j;
//all intervals that we already counted can be in combination with or without this new number
num_valid_subsets *= 2;
}
else {
++num_valid_subsets;
}
}
else {
break;
}
}
}
return num_valid_subsets;
}

tskrgulja1
February 24, 2019 Open Chat in New Window
O(width*height) time, O(height) space
Goes column by column computing number of paths based on the previous column
 tskrgulja1 March 21, 2019