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 in-order 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 2-1 <= 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 in-order 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;
}
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;
}
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;
}
O(width*height) time, O(height) space
Goes column by column computing number of paths based on the previous column
- tskrgulja1 March 21, 2019